Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Perfect Information Game: On Chess

hazlitt.net

Post reply on HN
Print view View original

21–30 of 34 posts

Re: Perfect Information Game: On Chess

#21

Post by DanWaterworth »

cousin_it wrote: post #10
DanWaterworth wrote: post #8

Earlier quoted context omitted.

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 p…

Thanks, that's an interesting nuance.

Re: Perfect Information Game: On Chess

#23

Post by kriro »

EvgeniyZh wrote: post #14
dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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.

Re: Perfect Information Game: On Chess

#24

Post by pacala »

dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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.

Re: Perfect Information Game: On Chess

#25

Post by Little_Peter »

rosstex wrote: post #3

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"

Re: Perfect Information Game: On Chess

#26

Post by pcmaffey »

dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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.

Re: Perfect Information Game: On Chess

#27

Post by citizen23 »

pacala wrote: post #24
dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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 th…

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.

Re: Perfect Information Game: On Chess

#28

Post by hellbanner »

dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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.

Re: Perfect Information Game: On Chess

#29

Post by hellbanner »

Flow wrote: post #5
dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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?

I'm having fun playing 3D tic tac toe and other games on a Shibumi set:

https://boardgamegeek.com/boardgamefamily/13434/shibumi

Re: Perfect Information Game: On Chess

#30

Post by nickpsecurity »

dkbrk wrote: post #4

I don't mean to diminish the accomplishments or skill of chess players, but in my opinion being a perfect information game makes chess, like go, much less interesting. 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 thi…

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.
Post reply on HN