Preventing Solvability in Games of Complete Information

How do you prevent solvability in games of complete information? I think there are two things that are necessary, but I'd like your thoughts on it as well. By complete information, I mean that you are presented with all the information in the game in a way where you can process it. That is, there's no fog of war, no randomly ordered deck, no hidden hands, moves are slow enough to be reacted to (or turn-based), etc.

Anyways, here are the two things I think are important:

1. Too much information to fully explore.

This means that it would be unrealistic for players to fully explore every relevant move or gamestate in the game. Just put so much into the game that players are always learning, even years or decades after the game is made.

2. Information is varied enough that different players can build different valuation.

I'm not sure how you would go about doing this—it might just happen naturally as a result of #1—but it seems important. You need different players to have different senses of valuation and not all come to the same conclusions. If two players both think that move A is the best move in a given situation, then suddenly the best move is actually B, which counters A. But then it's C, which counters B! Etc. This would be fine in a game that isn't complete information, as it give you a very simple RPS yomi, but in a game of complete information you get stuck in these whoever-goes-first-dies (Player A plays rock; being a game of complete information, player B knows this so he just plays paper and wins) or always-a-cats-game scenarios (see: Tic-tac-toe).

Anyways, thoughts?

I'm not a huge fan of designing abstract games so take my opinion with a grain of salt.

I think most games turn out not solvable if you ensure some other properties.

First of all the gamespace has to be to large to explore it completely. This can be done quite easily.

Second a large part of the gamespace has to be relevant. I'd argue there are more games in go that totally make no sense than games that make sense. Games as in moveorders from start to end. Still the amount of good games is large enough to not be explored either.
You could for example imagine a game with a huge gamespace but only a single viable path that leads to a draw. As soon as any player deviates from this path it is easy for his opponent to punish him and win the game.

Now to ensure the second property you can introduce intermediate goals (like capturing stones, securing good positions on some part of the board etc.) which can be traded. If in go the strongest move always was to reply locally the game would be far worse. Luckily I can trade a disadvantage somewhere for an advantage somewhere else.

Are you asking for a truly unsolvable game, or just one where it's not practically solvable by a human player?

Yeah thanks, that's pretty much what I was trying to confirm.

Can you also argue that making unclear payoffs will lead to variance in valuation? Like in chess it is not always clear what the payoff of castling is, and so people might value that differently.

Does RPS count as a game of complete information? You know everything there is to know about the game, with the caveat that you don't know what your opponent is going to do (which applies to Chess, Go, etc. as well). The only difference between the latter games and RPS is you take turns simultaneously in RPS.

So a short answer would be: Have the game be real-time/Simultaneous. Frozen Synapse (Light Mode) is a great example of this.

EDIT: I guess you do say that moves should be slow enough to be reacted to, but in something like RPS or FS you have plenty of time to 'react', it's just that turns happen at the same time. Either way I don't think that criteria (or a criteria to be turn based) is a required criteria of being a game of complete information. It's more like you're asking the question you asked + if your actions produce a deterministic result. But then I suppose that's just semantics in some ways.

In RPS players don't know the opponents choice when they make their own. Therefore it's not a game of complete information.

Here's one. If at every decision point in the game there are multiple options that are exactly equally balanced, then there is more than one thing that a player can do to attain the optimal outcome. I don't know if that would be considered "Solved, but with 1,000 optimal solutions" or "Unsolvable."

But any time a game is being played between humans, there is the hidden information of Player Intention. Many games don't take advantage of this, so all relevant information is evident in the game state (on the game board). For example, in Diplomacy, the state of the game is always 100% known to all players, with the exception of Player Intention. That's an extreme example, but I think it also applies in lesser way to games like Chess (or Go, or GIPF, or whatever). Is he moving this piece in order to attack with stacked Rooks down a file, or is he just trying to get his bishops free? (I'm not good enough at Chess to know how much Player Intention affects games, this was just an example)

I think the trouble with solvability comes in turn-based games where each turn the action of the player can be counteracted by the other player (like turn based RPS). If the turns are simultaneous, or if doing significant things in the game takes multiple turns to set up, then Player Intention becomes a huge shaping factor of how the game plays out.

So I think there are ways to make a Perfect Information game unsolvable. Either with perfect balance in many possible game states, or with increased reliance on the effect of Player Intention.

Yeah, Sirlin's right, there's no actual answer to this question. Perfect information games (which sounds like what the OP actually meant), just are solvable.

As for the two solutions proposed:
1) Make it too complex.
A: Don't rely on this. Your playerbase is larger and smarter than you are. It doesn't matter how "realistic" it is for someone to process all the data, they'll do it anyway.

2) Rely on valuation as a skill.
A: Again, can't be relied on. It doesn't really matter how much input you give a player to come up with their own valuations. Someone will just solve it with math, and post the solution.

Case Study: Go read up on Garcia1000's old Kongai posts. Best example I know of (and definitely easiest to research), of a player breaking a system that was supposed to involve yomi, but ended up providing enough information to players that someone found a set of mathematically optimal moves in a lot of endgame situations, and then the winner came down to RNG miss rates.

I don't see how Frozen Synapse light mode fits into Sirlin's categories. Yomi is complete information, but has decks of random order and what not so it seems very different from the amount of information you get in Frozen Synapse. Yet FS is simultaneous plays so it's not perfect information either.

In FS you know the game state when you make your move as well as all possible moves your opponent make. You can't rule out that the game is solvable either. It's entirely possible that a game board situation will be such that you can make a series of moves tailored based only on what your opponent HAS done and be sure to win (no different than chess in that case).

Are you asking whether Frozen Synapse is complete information or perfect information??? (I'm really not sure, your post is weird).

If so, the answer is it's complete information. It's a pretty wide category, so you don't need some other term to say "less random than yomi, but more random than chess"... it wouldn't add much to have such a term anyway. Having turns be double-blind, however, does mean the players don't have full information about the gamestate (because whatever hidden moves your opponent has queued up are part of the gamestate).

Doesn't unclear payoffs contribute to "solution is not yet known"? Cause that's what I was trying to get at. I also phrased it as a question because I am not sure, just suggesting an idea.

To clarify, when I say unsolvable, I do in fact mean, "impractical/unrealistic to solve." I don't really care if some space alien five thousand years from now designs a super computer that solves the game. And as Sirlin mentioned, by complete information, I mean perfect information. I couldn't remember the exact term when writing up the OP. I know it's just semantic, but I like the distinction.

I think that unclear pay-offs are central to making a game of complete information unsolvable, and will on their own lead to different players developing different senses of valuation. This leads to other questions. Is this all that's necessary? Can you put more than unclear pay-offs into a game to encourage players to develop different valuation? What are good ways to go about creating unclear pay-offs in games of perfect information? Etc.

One of the reasons I think different players having different senses of valuation is important is that it leads to... I don't know what to call it. It isn't really yomi (unless you mean it in the broadest possible sense) but it's something like it. Getting a feel for another player's valuation, and then abusing the weaknesses in it. You might play a "bad" move that is a good move against your opponent because you know that they will not evaluate your move correctly. This is similar to playing a "bad" move because it counters the move your opponent will play that is involved in yomi. This relies on players having not solved the game, of course.

If I'm understanding player intention correctly, then I'd say that it's relevant until the game is solved. Of course, once the game is solved, nothing matters except whether a given player knows the solution or not. That is why it is so important to make it difficult to solve.

Chess is not yet solved. Of course it might be solved one day, but frankly, if a game takes centuries to solve, I think that's pretty good.

I don't think it's fair to say, "This game was solved with math, therefore all games will be solved with math."

That's not how computers work. Once we can solve Chess... *we can also solve all games as complex as Chess*. The centuries that it took for us to get to this point are irrelevant. What's true is that *right now* solving games is very easy, and trying to create a game that's "hard to solve" is a pretty much a pointless endeavor.

I guess Arimaa shows that it can be done. But who do you know who plays Arimaa?

Actually... that's completely fair to say. I feel like you either don't understand games or math to be able to type that sentence in. Games are an abstract system of rules, and math provides us with a structured way to deal with abstract systems of rules.

Isn't "delaying the solution" relative to the size of your audience, though? Like, imagine if the guys who solved the Portal2 ARG, or that protein-folding game that was in the news recently somehow got pointed at Kongai? Not that it would ever happen, but I think a large enough, dedicated enough group could shrink years back down to weeks if they felt like it.

I agree with you that it can make a game better. But it seems like if the goal is to make a game "great", then a different approach is preferable.

Well, one thing is that complexity increases exponentially with the number of moving parts (if game is designed to allow this). So your task isn't as hard as it seems. Just adding one factor could increase the complexity by like, 10 times.

I think a distinction ought to be made between whether a game has been / can be solved by a computer, vs whether a human player cares that the computer has solved it.

To use chess as an example, you could (in theory) make a computer program that always wins at chess. All you have to do is run a min/max ai long enough to cover every possible game, from the first move to the last. Unless there happens to be some specific path a player can take that will always leave an opening for them to still win, no matter what their opponent does, that computer would be guaranteed to win every game. Granted, unless it's a super computer it will probably take about a day to make a move, but that is not the point.

I believe this is the sort of scenario we refer to as the game being solved. The thing is, just because some super computer has solved a game, doesn't mean that there's even one single human being who has the mental capacity and patience necessary to memorize that solution. So, unless there happens to be one specific path to guaranteed victory no matter your opponents moves, or the solution can be condensed into a relatively small set of simple(ish) rules, odds are it won't come up very often, if ever, when the people playing the game are all human.

Tic-Tac-Toe is one example of a perfect information game where this is not the case. Not only has it been solved, but the solution is so simple that anyone who cares can probably memorize it within a day, or quite likely an hour or less. Chess, in my opinion, is too complicated for that to be the case. I would also logically extend this to cover anything at least as complicated as chess. With potential exceptions for corner-cases caused by specific mechanical interactions.

I could be wrong of course. I'm not an expert on any of these topics. I hope I'm not though, as that would present a pretty bleak outlook on the future of perfect information games. Not that I've ever been a huge fan of those, but I would consider losing the validity of an entire broad game type to be a loss for gaming as a whole.

I think it is likely that the universe will end via heat death before a computer ever solves Chess.

Are you condemning every game as being no better than tic-tac-toe?

And math takes time to perform.

Anyways, let us hypothetically say that computers solves chess. What impact does this have on two players playing against each other? A human player cannot possibly juggle all the information in his head that a computer does. Assuming that the player does not simply have a computer play chess for him, of course (In which case the player is not really playing at all).

Let's say I make an invincible MK-walker style AI for Street Fighter that absolutely cannot lose. Am I now the best SF player ever? Have I "solved" the game? Not really.

Also, I know it's kind of dodging the question, but what about viewing games as sort of like puzzles? Through playing the game competitively, you are really co-operating in 'solving' the game? In a round-about way, this is sort of what PTW is about. You push your opponent to play better, they push you, and together you get closer to perfect play, or solving the game. Even if you never quite get there.

It's about what you're trying to improve. When you play SF, among the execution, you are improving your ability to read the RNG flaws and tendencies in your opponent. Each opponent is unique and a different situation and you can't be a good RNG generator yourself no matter how hard you try. In Chess your opponent is irrelevant because you can always win by making purely optimal moves (if your opponent makes 0 mistakes then it's whatever the result of the game is and you can't change that).

For me (and others?) just that mere fact, even if it's unobtainable, changes the joy in learning that type of thing. I feel like I'm not learning or improving some skill, but rather just memorizing game states (and admittedly some kinda cool stuff behind that about how to optimizing remembering game states).

I think that people often under-estimate the complexity of abstract games, especially ones on or past the edge of computer domination, like Chess. These games are large enough that even people who have dedicated their lives to studying just one game can have style. Situations in chess can be described by a great many factors, and even in the upper echelons people will be more familiar or comfortable with situations that can be grouped together by some category, and less familiar with situations that fall under some other category. This is even true in extremely well-understood, highly mathematical games like Sprouts.

This is why some grandmasters are noted for particularly sharp play, while others favor closed games. That is a fairly un-subtle manifestation of the phenomenon, but much of the strategy in abstract games revolves not around finding an optimal move so much as pushing the game into a state that your opponent is less familiar with, and does not understand as well as you do. Just like you cannot be a good RNG, you also cannot be a good alpha-beta searcher, no matter how hard you try. The existence of an optimal move is a theoretical curiosity, nothing more.

I should be clear that this is a property of great games, and there are many abstracts that just come down to being better at searching, or knowing more positions than your opponent. I believe that it is not actually particularly difficult to make a great game, if you know what you are doing and have good testers who also know what they are doing. The economics of abstract games is more of a hurdle than the actual design problems in creating a deep game.

I remember you saying something about RPS games being solve by mathematics. However, you also pointed out that players are usually bad at doing things at specific percentages. So can we say that there are perhaps two types of game solutions, the good one (doing things at a specific percentage) and the bad one (like in tic-tac-toe)? I think we should be able to see the diffrence in the effects of a game being solved.

I find the distinction of "perfect information" and "complete information" quite amusing. However, I still have some confusion with these two phrases.

You said that all complete information games are solvable, so since Yomi card game is a game with complete information, does it mean that it is solvable? How about games like Stratego?

And where does hidden information comes in?

Your post actually sounds like most board games (turn-based) are solvable.

He said that all games of perfect information are solvable, not complete information.

This reminds me of how I used to worry about if I ever got really good at fighting games, the game would degenerate since all pro fighting game players have trained their reflexes to perfection and can react to 1-frame moves flawlessly. This is something I actually believed. Not really making a point here, just thought I'd share.

I don't think I agree with this. You ultimately get the same thing—the known, always-optimal move. The difference is that one ends in a tie and the other is RNG. I'm not sure either is preferable over the other. Randomness is good if it prevents solvability, but if it just leads to a mixed strategy solution it hasn't really done anything. And from what I understand, mixed solutions only creep up if there is randomness. Also if there is yomi I guess, but I don't think that a mixed strategy is really a solution to yomi.

Stuff like this I am really interested in. It's what my 2nd point in the OP was about, though I may not have communicated it well. I am less interested in players getting better at the game by simply looking for more optimal moves (solvability) but would rather have there be interaction between players' valuation abilities. Where you are probing for and finding weaknesses in your opponent's valuation and playing to exploit that weakness. What I am very curious about is what kinds of qualities gives a game this property.

As far as I understand without randomness and with perfect information there is (possibly hard to find) optimal pure strategy. With randomness or imperfect information you get an optimal mixed strategy. I can't really remember if there are classes of games with no mixed nash-equilibrium - perhaps infinite games but this gets very theoretical. Therefore I think mathematically all relevant games at least have that.
Keep in mind that nash-equilibria are not always perfect as you don't play your opponent, but assuming a perfect opponent you will play an equilibrium.
Now my point is, I doubt randomness can prevent solvability at all. It can force mixed strategies and it can make it harder to find an optimal strategy but it can't prevent it entirely.

Now if you want to only consider practical solvability then you don't really need randomness either as there are plenty of games that proof that a large enough gamespace suffices. Therefore I'd only include random elements if you like the gameplay properties it causes. (Possible properties are a reduced emphasis on searching the game tree, necessity to juggle probabilities)

This sounds very interesting - and hard to achieve. In a game with diverse gamestates and decisions you need tons of moves to get a detailed picture of your opponents valuation, especially if your opponent is trying to hide it behind a mixed strategy. You could take a look at heads-up poker, it is a very simple game and ridiculously hard to play optimal.
Obviously it has hidden information making it harder to figure out your opponent. On the other hand your game has to be much more complex to allow a large variety of valuations while being a perfect information game.

Let's say, for instance, that Chess is a solved game. In this solution, we find that White always wins when the perfect game is played. White goes first, making the first move in the optimal solution. Black then goes, but since he knows he will lose if he plays the "optimal" game, he plays a suboptimal move. Now the game is not the "solved" version of the game.

The reason Tic-Tac-Toe is so easily solved is that there are few enough options that I can account for every option with every move I make, and moves very quickly become forced.

Because of how many turns it takes to start forcing moves on your opponent in Chess, the only way to play a perfect game is the be able to find the best move every turn. If you can't force your opponent's move next turn, then you have to be able to account for every possible action he is capable of doing.

And to calculate the best possible move, I reckon you'd have to take into account how many moves that opens up for you in the future, how many moves this allows your opponent, how much material gain you'd get, etc. Many of these things don't have specific values, especially considering that your calculations must include some amount of probability of what your opponent will do next.

Every solved game of Tic-Tac-Toe is the same game, but rotated 90 or 180 degrees. This cannot be the case with a game like Chess, because moves do not become forced as quickly. For Chess to be solved, there must be a move each turn that is strictly better than all other moves. That is not the case due to what I mentioned in the previous paragraphs.

A game is solved when for every deviation that black makes there is a known moveorder that gives white the same or a better result.

If for example it is known that white wins in a perfect game, then the solution might consist of the path through the gametree that gives white the latest possible win (most moves required). Then every deviation by black leads to an earlier loss by black.

Therefore if it is solved, than it is solved in all subgames as well. Someone already mentioned it is highly unlikely that this will be possible anytime in the forseeable future and even if it is possible no human can memorize this solution.

Yea as Leartes said the only difference between Tic-Tac-Toe and Chess is the complexity (I mean that's a big difference but yea). Regarding "For Chess to be solved, there must be a move each turn that is strictly better than all other moves.", note that you can easily tell this is false simply by looking at Tic-Tac-Toe which is solved and the latter is not the case.

Yeah, I talked it out over lunch, and I think that perfect information games are inherently solvable. It's weird for me because I tend to think along the lines of games that in this thread are being referred to as "complete information" games.

Hahahahahahaha. Yeah, we're done here. Do some frickin' research:
http://en.wikipedia.org/wiki/Solving_chess

And that article is just working with some pretty conservative viewpoints. Good estimates place it much sooner.

How "good" are good estimates? And 50 years ago they were sure that by now we'd long be running on fusion power.

Also I highly doubt computational power will increase exponentially for two hundred and forty years.

Just try to estimate the computational power you'd have by then. It'd be possible to count from 1 to the number of atoms in the universe by then ...
So I don't think there will be a brute force solution unless P=NP. There might be a more sophisticated proof but not via computational power.

I think most important is having many sub-goals that are mutually weakly opposed -- increasing your strength in one should come at the cost of being weaker in the others, but not to the exclusion of the others. One easy way of getting this is by making actions have a strong local effect and a weaker non-local effect. Influence in Go is an example of this, a move has more effect on the game right where it is made, and that influence tapers off as you move farther from the stone. Othello is an example of what not to do, moves effect too much of the board too strongly.

"Recycling" is another way of getting this kind of tapering effect, but temporally instead of spatially. If spaces are occupied and then vacated repeatedly, then short-term gains are fleeting, so focusing on the long-term effects is more important. Those long-term effects are harder to valuate, so there tends to be more variation in how people address them.

With recycling though, you need some guarantee the game will end. The easiest way to do that is to have some fundamental variable in the game that either only increases (to some limit) or only decreases. In Othello this is the number of pieces on the board, but many games (notably most of Mark Steere's games) have a nested set of these. In Hex Oust, the number of groups of stones increases every turn, and can only decrease if the size of the largest group increases. Some games have even more complicated ratchet factors.

There are other mathematical properties that are nice: high branching factor (>30) and long average game length (again >30) both increase the absolute size of the game tree, which is likely to increase the size of the relevant game-tree as well. Game temperature is very important and currently not well understood; you generally want to strike a balance between "hot" positions (where you would rather make a random move than pass) and "cold" positions (where you would rather pass than make the best move available to you). Some games like Go, Hex, and Connect6 manage very well even though they are completely hot, but they need some artificial mechanism for balance (komi, a swap option, or a restricted first move)

The game has to give the players more information than they can process, and it has to give players the means for taking short-cuts in processing the information, and those short-cuts must be imperfect. Branching factor, length, and temperature are all good indicators that the game will likely have this property, but only thorough testing can say for sure.

The abstract game design community is small, and there are still a lot of open questions that we are working on, but there is right now an effort to make abstract game design more scientific and controlled.

Thanks rozencrantz for the insightful post.

The notion of hot and cold gamestates is new to me. I always thought positions you define as cold are bad, boring and lead to stalemates. Never thought of using them to remove the first move advantage.

Also I think what you call high branching can be too much. I know many games have a branching beyond 30 move-options, but usually a large amount of those options is clearly not good. I think it wouldn't be a problem to have a game with a larger fraction of interesting moves. Like a game with 10-20 move-options where 50-90% are non-trivial. Not sure if you should aim for this property during design but you should definitely count the number of interesting branching moves. I mean high branching destroys naiv computer play but that is bad approach to solving the game anyway.

That is true, but it's extremely hard to control. There are necessarily no more viable paths than there are total paths, so increasing the number of branches tends (in a rough statistical sense) to increase the number of interesting paths. These games are so unpredictable that you have to take a shotgun approach much of the time.

Yeah, that was basically my point. The most powerful Chess software available today (the stuff since deep blue... deep fritz is one, I don't know if there's something even more recent?) doesn't rely on brute-force methods. The amount of processing power described in that link isn't necessary, if you have enough advantages in the effectiveness of the software to trim the move tree way down in the first place, which is effectively what's happening.

If you are generally interested in the topic, I highly, highly recommend this book:
http://en.wikipedia.org/wiki/The_Singularity_Is_Near

He spends quite a while in the beginning sections explaining both the current state of chess-playing computers, and why solving the game is inevitable (and the rest of the book is super interesting, too). I could probably not scratch the surface in a forum post.

For the record, history shows that would be one of the worst bets you could possibly make... (A topic also covered in detail in the book above)

Chess is almost certainly a draw imo. One problem with chess is that even if one player plays a little better then the opponent the game can still be a draw. So if Chess is solved as a draw the game really might just be over as far as top level play goes. I think chess is clearly on its deathbed, look at the percentage of gm draws.

There may be an exception for games which are infinitely scaleable, such as Go. Go on a 19 by 19 board is solvable (but not with today's computers), but provable much more computationally difficult to solve than Go on a 13 by 13 board. And while for any given N by N Go board, the game will be solvable, those may (or may not) be different solutions for each board size so there may not exist a generalized solution for Go played on an arbitrarily large board.

This is a thing, it's called Zermelo's theorem: Any finite game is theoretically solvable. For any given N, the game tree may be astronomical (as it is with n=19) but it is still finite (this is not strictly true, because there are infinite variants of Go, but they are not relevant. PM me if you want to know way too much about finiteness as it pertains to Go and the solvability of Go)

On a practical level though none of this matters, because even with today's technology we have game solutions outside the bounds of human comprehension. Chess is orders of magnitude more complex than those, and Go is orders of magnitude more complex than Chess.

To back up my knowledge I currently only have wikipedia at hand http://en.wikipedia.org/wiki/Computational_power#Ultimate_limits_of_the_law and the following paragraphs. Also there is currently research going on in direction of atom-scale transistors with some recent results in january this year (not included in the wiki article yet).

Additionally to the limitations of current technology which will end moores law in a few years if no other technology is developed in time, there is also the exponential increase in research cost and the dropping efficiency in massively distributed computing. For many problems there is a multiplicative gap between the necessary amount of operations on a single core system to a multi-threaded system. This is due to the increased amount of required operations for communicating partial problems and solutions inside the system. Finally for many problems there is a bound on the number of cores that give a increased performance, therefore even a hypothetical processor with an infinite amount of cores (and therefore infinite parallel operations) still has pretty hard bounds on the runtime of many problems.

Now I do believe there might be a faster technology out there but I doubt it will come soon and I believe the increase in development cost will persist. Leading to a singularity with infinite cost in labour and $$.

In conclusion I do think Kurzweil is wrong. His work is certainly interesting but very optimistic in my eyes.
Anyway I'm fine with you agreeing with him, just keep in mind that he is just one among many experts with vastly different opinions on the matter. (And no I'm no expert )

The only technology I can imagine that breaks all assumptions is one that allows for real valued bits. If something like that is ever developed it would crush most of the current theories of computer science.

Chess is just another optimization problem with exponential runtime. For many NP-complete optimization problems it is possible to show lower bounds on the runtime therefore I foresee a lower bound on the constant factor in the runtime of solving chess. Obviously the notion of runtime is strange since the input size is fixed still I think there are limits to how good your pruning can become because there are limits in many much easier problems as well.

Thanks again, another interesting read. I agree on practical levels it is not relevant today and unless the solution is easy enough for a human to understand there is no problem in playing a solved game anyway.

Also I doubt a game becomes better just because you scale it to a size where computers can't solve it. I watched some 399 go games on kgs. They take many hours and most of the time local results don't matter much. Certainly nothing I'd want to play on a regular basis.

http://en.wikipedia.org/wiki/Arimaa

As much as I'd love to find a better source than wikipedia, the Arimaa article is actually excellent and contains a huge section on the computationality of the game and the difficulties an AI would have to solve this game.

Anyway, the game is made by an AI programmer who wanted to "design a new game which could be played with a standard chess set, would be difficult for computers to play well, but would have rules simple enough for his then four-year-old son Aamir to understand." As such, it uses quite a few techniques to discourage brute force and delay solvability, the most important one probably being a very high branching factor (http://arimaa.janzert.com/bf_study/). Obviously, it does not claim to be unsolveable, but it does succeed in making it impossible to solve within current hardware constraints.

As such, even games on a small board can be insanely difficult to brute force.

PS: according to the arimma wikipedia article: "Top chess programs use brute-force searching coupled with static position evaluation dominated by material considerations. Chess programs examine many, many possible moves, but they are not good (compared to humans) at determining who is winning at the end of a series of moves unless one side has more pieces than the other." Sadly, no reference is given.

That chess quote is fairly out-of-date; positional evaluation has gotten a lot better, especially in programs like Rybka. They don't use brute-force searching, they use alpha-beta searching: they use the positional eval algorithm to eliminate less promising branches of the game-tree, search smarter not harder. Top chess programs all evaluate about the same number of nodes/second, the best programs examine the best nodes (or the fewest bad nodes). It is true that some things are easier to evaluate than others, and material is one of the easiest, but they are much more sophisticated than that.

The thing with solving a game is, valuation heuristics and alpha-beta pruning is not enough. You can never be sure you really got the optimal play, you only know you got the optimal play for the heuristic used. And every heuristic is limited.
To apply alpha-beta pruning in a program that not only plays really well but solves the game, you need to prove for your valuation heuristic that it strictly increases the chance to win for every possible gamestate. Which is a pretty hard thing to do ... Even proving that your program is actually close to optimal play is hard since you can't really analyse how close your valuation is to the optimal valuation. The only thing you can do is do experiments and play versus other ai or strong human players and find out how strong you are in relation to them. Solving is something entirely different.

Once again, let me just point out that people have predicted that every year for 30 years now and been wrong. So, again... very, very bad bet to make.

That said, you're overlooking a couple important points:

a) You really shouldn't be making statements about whether you believe Kurzweil is wrong or not without knowing what he said. He argues in favor of this concept (which is not the same as Moore's Law, and too often gets confused with it):
http://en.wikipedia.org/wiki/Accelerating_change

b) I wasn't actually referring to Moore's Law either, because there's much bigger stuff going on. What I mean, is that currently the massive advancements in computing are being made in hard drive space, and bus speeds. The standard example being Solid State Drives, and how awesome they are, and how widely available/affordable they're becoming. Processor speeds have stopped going up because it didn't matter... it ceased to be a bottleneck.

c) Quantum Computing (and the competing crazy ideas that I don't even remember the names of). I mean, it doesn't exist yet. But all the research out there seems to indicate it's possible, and could happen sooner than one might expect. If they do manage to create it, it will totally change the game.

Then let me frame it different. I think these theories are nothing more. They are on the same level as me saying there will be a thunderstorm in 364 days from now in London. Now I could start make some charts that look nice and support that possibility and you could believe me or not. I am 100% sure there will be no singularity in 2045. It is just ridiculous.
Have you ever worked in a scientific environment? Technological progress needs time to be understood and more time to be tested. Computer science will not suddenly evolve much more rapidly as it does now. Perhaps it will broaden up more so that there are more fields of study but in no single branch will be much more improvement as there is now apart from the rare random breakthrough.

Kurzweil argues around that barrier of human understanding with:

It is a nice (or not so nice) dream but not more believable than the cold fusion wonder. Even normal fusion power was said to become the norm already decades ago. We know how that went so far ...
I'm not saying machine intelligence will not evolve. It is not difficult to evolve since at the moment it is none existent. All we can do with computers at the moment is define a course of action we are to lazy to calculate by hand and input it into a machine that does all the boring steps for us. Even neural networks are not beyond that level yet. Not sure how you come from 0 machine intelligence to some breakthrough in 2045 since exponential grows from 0 remains 0.

Also stuff like

Sounds nice but is highly not scientific. I can't give something like that much credibility sorry.

He could stay on the safe side and claim "someday a singularity might occur" due to some reasons but this timeframes ...

Anyway if you want to continue discussion on this matter maybe open a new thread in the General Discussion section, it is highly offtopic in this thread

This is a point I'm not entirely clear on: would quantum computing do a complete end-run around P/NP, or would it just vastly reduce the root of the exponent?

As far as I understand quantum computing there is an exponential improvement in the number of qbits used.

It is quite some time since I did complexity theory in regard to quantum computing. Wiki states some weird properties indicating that there might be more than polynomial speedup for some hard problems but not for all. This contradicts with the general notion of the class NP-C. I'll have to read up on this :)