Perfect Information Game: On Chess(hazlitt.net)
hazlitt.net
Perfect Information Game: On Chess
http://hazlitt.net/feature/perfect-information-game
7 comments
I don't mean to diminish the accomplishments or skill of backgammon players, but in my opinion being an imperfect information game makes backgammon, like poker, much less interesting.
It means that, in principle, it is simply a matter of running Minimax over all possible distributions on a sufficiently powerful computer, and the game can be solved. I do mean 'in principle': actually doing this is still well beyond the world's computational capabilities, though this doesn't stop computers playing stronger than any human.
It means that, in principle, it is simply a matter of running Minimax over all possible distributions on a sufficiently powerful computer, and the game can be solved. I do mean 'in principle': actually doing this is still well beyond the world's computational capabilities, though this doesn't stop computers playing stronger than any human.
I think that backgammon is more similar to chess than poker in this respect. Despite the exogenous element of chance it can still be considered a perfect information game.
Your statement does not hold for games truly characterised by imperfect information (e.g. poker), in theory or in practice.
Your statement does not hold for games truly characterised by imperfect information (e.g. poker), in theory or in practice.
I disagree with your premise. While it's true that in theory, we could run minimax on a sufficiently powerful computer to solve chess and go, we can't in reality solve chess and go with computers. And even if we could solve them with powerful computers, human brains still cannot.
You still have less than perfect information about the decision tree, and you have to pick what you think is the best move from all of the available moves. In that respect, games of perfect information are no different than games of imperfect information when the scale of the game is too large to be solved.
You still have less than perfect information about the decision tree, and you have to pick what you think is the best move from all of the available moves. In that respect, games of perfect information are no different than games of imperfect information when the scale of the game is too large to be solved.
> we can't in reality solve chess and go with computers
I don't think this is correct. Both could be solved by determining the perfect move for each board arrangement, leading to a very simple, but very data-heavy solution (see: https://en.wikipedia.org/wiki/Shannon_number - number of chess positions somewhere below 2^155 - and also need to track for each position whether can empassant for each pawn like X-FEN does, and http://tromp.github.io/go/legal.html - number of Go positions for 19x19 board ~2.081681994 * 10^170, though other-sized boards would each need their own set of solutions). In addition, both Chess and Go engines have beaten masters:
https://en.wikipedia.org/wiki/Human%E2%80%93computer_chess_m...
http://www.wired.com/2016/03/googles-ai-wins-fifth-final-gam...
You could be correct about the human brain being incapable of storing all of the Chess or Go solutions. While the brain could perhaps memorize enough strategies and board positions to substitute, the theoretical maximum of 2.5 PB may not be enough to hold all board positions and metadata.
http://www.scientificamerican.com/article/what-is-the-memory...
I don't think this is correct. Both could be solved by determining the perfect move for each board arrangement, leading to a very simple, but very data-heavy solution (see: https://en.wikipedia.org/wiki/Shannon_number - number of chess positions somewhere below 2^155 - and also need to track for each position whether can empassant for each pawn like X-FEN does, and http://tromp.github.io/go/legal.html - number of Go positions for 19x19 board ~2.081681994 * 10^170, though other-sized boards would each need their own set of solutions). In addition, both Chess and Go engines have beaten masters:
https://en.wikipedia.org/wiki/Human%E2%80%93computer_chess_m...
http://www.wired.com/2016/03/googles-ai-wins-fifth-final-gam...
You could be correct about the human brain being incapable of storing all of the Chess or Go solutions. While the brain could perhaps memorize enough strategies and board positions to substitute, the theoretical maximum of 2.5 PB may not be enough to hold all board positions and metadata.
http://www.scientificamerican.com/article/what-is-the-memory...
I don't think you realize how large of a number 2^155 is. The number of atoms comprising the entire planet earth is on the order of 10^49 or 2^162 [0]. Thus, to store all possible chess positions using only the material available on planet earth you'd have only 2^7 or 128 atoms available to store each one. All of this is ignoring the amount of energy you'd need to operate such a device, which is even more staggering.
[0] http://www.fnal.gov/pub/science/inquiring/questions/atoms.ht...
[0] http://www.fnal.gov/pub/science/inquiring/questions/atoms.ht...
A petabyte of storage would have been unthinkable 20 years ago. Think of the not too distant future.
Using the following dataset of year to max drive size in bytes per year [1a][1b]:
{1956,5.00E+06},{1979,5.71E+08},{1980,1.00E+09},{1991,1.00E+09},{1992,2.10E+09},{1997,1.68E+10},{2003,3.70E+10},{2005,4.00E+10},{2006,1.60E+11},{2006,7.50E+11},{2016,5.00E+12}
Linear regression provides the equation: year = 4.222874399 ln(numBytes) + 1896.534826
Assuming the average bits required to represent a board state is 160 [2], then: 2^155 positions x 160 bits = 9.13e47 bytes
4.222874399 ln(9.13e47) + 1896.534826 = 2362.87979
So, a projection shows that by year 2362, we could have a single storage drive holding every permutation of a board state, so it would be less than 2 drives to store the states along with the move to make for that board. Add more drives and you pull that date in.
References:
1a. http://www.pcworld.com/article/127105/article.html 1b. http://www.computerworld.com/article/2473980/data-storage-so... 2. http://codegolf.stackexchange.com/questions/19397/smallest-c...
Linear regression provides the equation: year = 4.222874399 ln(numBytes) + 1896.534826
Assuming the average bits required to represent a board state is 160 [2], then: 2^155 positions x 160 bits = 9.13e47 bytes
4.222874399 ln(9.13e47) + 1896.534826 = 2362.87979
So, a projection shows that by year 2362, we could have a single storage drive holding every permutation of a board state, so it would be less than 2 drives to store the states along with the move to make for that board. Add more drives and you pull that date in.
References:
1a. http://www.pcworld.com/article/127105/article.html 1b. http://www.computerworld.com/article/2473980/data-storage-so... 2. http://codegolf.stackexchange.com/questions/19397/smallest-c...
"In reality" means that the working set of memory and time complexity on solving Chess (let alone Go) is vastly too large for computers now and in the future. I don't get why you tacked on computers beating grandmasters/9-dans, since that has nothing to do with solving the game.
Oh you added something on the end. Well, augmenting a human brain doesn't change the search space of solving Chess and Go (especially Go). You may be underestimating how large those problems are.
Oh you added something on the end. Well, augmenting a human brain doesn't change the search space of solving Chess and Go (especially Go). You may be underestimating how large those problems are.
I told you how many solutions you'd have to store. I don't see how that is underestimating.
But isn't this true of all games? In games of imperfect information, there is still a perfect, computable solution. It just happens to be a mixed strategy. And if the argument is that games of imperfect information allow exploitative strategies to succeed against non-equilibrium strategies, well the same is true of chess: the very idea of a trap is usually making a suboptimal move to hopefully exploit an imperfect opponent's likely mistake.
When you have imperfect information, understanding the other player's strategy becomes part of the game. A perfect solution may be computable against any deterministic strategy, but its stops being a possibility when you don't know the other player's strategy.
No, tedsanders is right. If the game has imperfect information but is zero-sum (i.e. the goals of players are perfectly opposed), you can always compute the subgame-perfect Nash equilibrium in mixed strategies, and it will be the best way to play against all possible opponents, both deterministic and random.
Mind games (bargaining, precommitment, etc.) only become important in non-zero-sum games, where the goals of players align in some ways and oppose in others. For example, if chess had an additional possible outcome where both players lose, that could make it impossible to find a single best strategy.
Mind games (bargaining, precommitment, etc.) only become important in non-zero-sum games, where the goals of players align in some ways and oppose in others. For example, if chess had an additional possible outcome where both players lose, that could make it impossible to find a single best strategy.
Thanks, that's an interesting nuance.
Regarding your surprise about chess being played as a sort of wargame: actually when used as such, they did include "fog of war": https://en.m.wikipedia.org/wiki/Kriegsspiel_(wargame)
See also:
https://en.m.wikipedia.org/wiki/Kriegspiel_(chess)
Blind chess sounds like an extremely difficult game. I really want to play it.
Seems as though it's most easily played as a computer game.
Seems as though it's most easily played as a computer game.
You are absolutely right. Whoever has time for a long confirmation, can find it here: http://www.wsj.com/articles/bridgenot-chessis-the-ultimate-w...
For those who want something shorter I can say that based on your reasoning, bridge is much more interesting. This may be sound as a joke since in US bridge is mostly played by old people, but is true.
The most important reason is that bridge will never be perfectly solved by computers. Someone said in this thread "for imperfect information (games), there is still a perfect, computable solution". This can be true, but the interesting point is that this perfect computable move may be the wrong move by far.
In order to explain this I will say that in bridge there are many situations where you have to choose between two paths. Path one is a winner 65% of the time according to mathematical analysis. Path two is a winner 5% of the time according to the same analysis above. However path two is the winner, because the opponents have also incomplete information and even according to their BEST analysis (mathematical or psychological) they must follow up with a movement that will make you win 100%.
Unfortunately as the author said, this cannot be appreciated if you are not very familiar with the game.
Since you mentioned generals and the like, Eisenhower was a bridge fanatic. At present time it is enjoyed by the two richest men in Earth, Bill Gates and Warren Buffet.
For those who want something shorter I can say that based on your reasoning, bridge is much more interesting. This may be sound as a joke since in US bridge is mostly played by old people, but is true.
The most important reason is that bridge will never be perfectly solved by computers. Someone said in this thread "for imperfect information (games), there is still a perfect, computable solution". This can be true, but the interesting point is that this perfect computable move may be the wrong move by far.
In order to explain this I will say that in bridge there are many situations where you have to choose between two paths. Path one is a winner 65% of the time according to mathematical analysis. Path two is a winner 5% of the time according to the same analysis above. However path two is the winner, because the opponents have also incomplete information and even according to their BEST analysis (mathematical or psychological) they must follow up with a movement that will make you win 100%.
Unfortunately as the author said, this cannot be appreciated if you are not very familiar with the game.
Since you mentioned generals and the like, Eisenhower was a bridge fanatic. At present time it is enjoyed by the two richest men in Earth, Bill Gates and Warren Buffet.
Game designer Raph Koster suggests that "Learning is Fun". Human brains are wired to feel pleasure when they gain knowledge.
So while in principle, the best chess program is, yes, a computer program, humans enjoy learning systems and that's part of why Go & Chess has survived thousand(s?) of years.
www.amazon.com/Theory-Game-Design-Raph-Koster/dp/1449363210/
Additionally, humans seem to not learn by the "min-max" algorithm. Grandmaster Go & Chess players don't exhaustively search all options then compute the best. They use fundamentals (and perhaps intuition, maybe parallel processing?) to see a great move. We still know very little about how brains learn and strategy games are great opportunities to explore this.
So while in principle, the best chess program is, yes, a computer program, humans enjoy learning systems and that's part of why Go & Chess has survived thousand(s?) of years.
www.amazon.com/Theory-Game-Design-Raph-Koster/dp/1449363210/
Additionally, humans seem to not learn by the "min-max" algorithm. Grandmaster Go & Chess players don't exhaustively search all options then compute the best. They use fundamentals (and perhaps intuition, maybe parallel processing?) to see a great move. We still know very little about how brains learn and strategy games are great opportunities to explore this.
This is why I play speed chess exclusively. It combines the potential strategic purity of chess with the human craftiness involved in games like poker.
Limitation is the source of all creativity.
Limitation is the source of all creativity.
I agree. I tell people to play games like Poker and Starcraft instead. Poker because it teaches you how to spot and perform bluffs useful in real-world situations. Plus, keep your calm as money in pot grows. Starcraft because it combines board positions, fog of war, strategic thinking, real-time reactions, bluffs, and opponent bluffs. Nearly ideal type of strategy game except that it's so fast that hand-eye coordination becomes limit among pro's. Turn-based strategy with time limit per move could be best in theory but I know less great one's there outside Sid Meier's stuff. Just not knowledgeable.
Yet we got poker solved (kind of - https://en.wikipedia.org/wiki/Cepheus_(poker_bot) ) earlier than chess. If you asked me before I knew it, I'd say chess is easier to solve.
That is only for HU limit poker though. Limit is played very little these days. There are some decent bots for no limit but I'm not aware of one that plays well with deep stacks (200bb+).
There's http://www.computerpokercompetition.org/ and they usually provide a short writeup. However the best bots are likely not found in academia but at the table of online poker sites.
There's http://www.computerpokercompetition.org/ and they usually provide a short writeup. However the best bots are likely not found in academia but at the table of online poker sites.
You comment is excellent. Thank you! It made me realize that I've actually been regarding games like Sudoku and Reversi like this for decades already. Having written programs to play both I find the games "solved".
What games do you find interesting to either just think of or to play?
What games do you find interesting to either just think of or to play?
I'm having fun playing 3D tic tac toe and other games on a Shibumi set:
https://boardgamegeek.com/boardgamefamily/13434/shibumi
https://boardgamegeek.com/boardgamefamily/13434/shibumi
Mathematics also has perfect information, but people find plenty of aesthetic appeal in that. (Though in many respects, competitive chess is not at all like mathematics. An uncooperative opponent and time constraints are important additions to the possibility of beautiful moves.)
Gonzo style reporting of the chess scene.
>> My own personal conception of existential dread is, like my inability to visualize, idiosyncratic. Many people, I think, are troubled by their own insignificance, preferring not to think about being a tiny part of a vanishing species in what couldn’t even be called a corner of the universe. Not me—I’m fine with that. ... That’s all infinity does, or rather doesn’t do. It doesn’t scare me.
>> What does scare me—what provokes real horror in me—is excess reality. I see mental horror—The Void—in the tumbling numbers of securities trading, or the heaps of barely decipherable ancient papyrus dug up in the near Middle East, or the global weather patterns which have evaded, to this date, capture by any mathematical model. I am troubled by the world’s great throngs of data—by thickets of facts I might comprehend individually, but that together make a chaos capable of receding before me as long as I live—the miles of definition leading nowhere.
>> That’s what I felt, staring at the board in front of me. I felt like I couldn’t put my pieces anywhere, because I felt like I could put them everywhere, for all eternity. I basically blacked out.
These parts are well written and convey his experience on entering the zone. These are negative images coming from the inability to perceive order. There is also the positive part with the state of flow in being absorbed in this alternate world.
I like Hikaru No Go, which conveys a sense of being a go player, with the attractions of a game, the competitions, the disappointment in the backdrop of a fantasy story.
>> My own personal conception of existential dread is, like my inability to visualize, idiosyncratic. Many people, I think, are troubled by their own insignificance, preferring not to think about being a tiny part of a vanishing species in what couldn’t even be called a corner of the universe. Not me—I’m fine with that. ... That’s all infinity does, or rather doesn’t do. It doesn’t scare me.
>> What does scare me—what provokes real horror in me—is excess reality. I see mental horror—The Void—in the tumbling numbers of securities trading, or the heaps of barely decipherable ancient papyrus dug up in the near Middle East, or the global weather patterns which have evaded, to this date, capture by any mathematical model. I am troubled by the world’s great throngs of data—by thickets of facts I might comprehend individually, but that together make a chaos capable of receding before me as long as I live—the miles of definition leading nowhere.
>> That’s what I felt, staring at the board in front of me. I felt like I couldn’t put my pieces anywhere, because I felt like I could put them everywhere, for all eternity. I basically blacked out.
These parts are well written and convey his experience on entering the zone. These are negative images coming from the inability to perceive order. There is also the positive part with the state of flow in being absorbed in this alternate world.
I like Hikaru No Go, which conveys a sense of being a go player, with the attractions of a game, the competitions, the disappointment in the backdrop of a fantasy story.
IMHO chess is portrayed like this by people not really exposed to it.
For everyone interest in a very readable overview of chess history I suggest: http://www.amazon.com/s?search-alias=stripbooks&field-isbn=0...
I wanted to get into chess as an adult, with the aim of becoming a master. However, I found that even some people who had studied chess from an early age, and where chess still dominated their lives, they still didn't raise above IM or even master.
This put me off for a while, as I was the sort of person who needs to be the 'best' I can be and merely being good wasn't enough, especially with all the study that comes with it.
This brings back memories. I played chess from years 8-12 at national level and then I just dropped all interest in it. Wish I'd kept with it really
That story took an unexpected turn
This was a fantastic read!
Agree. Very will written. I laughed out loud couple times:
- "chess is a deeply unnatural skill - it requires the full command of a bunch of neurons that the adult mind has already donated to the ability to navigate a grocery store lineup without screaming"
- "chess is a deeply unnatural skill - it requires the full command of a bunch of neurons that the adult mind has already donated to the ability to navigate a grocery store lineup without screaming"
It means that, in principle, it is simply a matter of running Minimax on a sufficiently powerful computer, and the game can be solved. I do mean 'in principle': actually doing this is still well beyond the world's computational capabilities, though this doesn't stop computers playing stronger than any human.
People find an abstract beauty in the purity of the game's structure, but I find that lack of information asymmetry makes the game less rich. One does not need to attempt to induce the other player's thoughts, their strategies or the location of the pieces, one merely has to look at the board. There are no feints, one cannot pretend to be following one strategy and actually be planning something else.
Some of these features do crop up, sort of: due to the size of the game's space and the imperfection of the players, players can be surprised by a particularly brilliant move. But this is an artifact of the players not being good enough, not a feature of the game itself.
I find it strange in this light that chess (and go) have historically been seen as a sort of wargame, a respectable pastime for generals and the like. Reasoning and planning in the presence of uncertain information (the "fog of war") is one of the most important aspects of military strategy and actually common to most human endeavours. The 'uncertainty' due to the combinatorial complexity of the game doesn't really capture that sort of probabilistic scenario very effectively. For example, many games lacking perfect information do not have a solution, rather the optimal 'solution' is a mixed strategy where a player randomly selects from a set of strategies weighted by probability. This also means that the other player can't simply know "my opponent is playing perfectly, therefore they will play strategy X", making the game in some sense much harder. This, of course, tends to generalise to imperfect players and real-world games as well as just the ideal.