Chess, unlike war, is a game of perfect information • Hacker News Board

Re: Chess, unlike war, is a game of perfect information

#21

Post by xh-dude » Sat, Apr 15, 2023, 12:35 AM UTC

Waterluvian wrote: post #15

I find it fascinating how Chess is, in a way, stateless. Other than whether some rules like castling are still valid, you don’t need to have played the previous moves to be able to play the next moves effectively. This got me thinking: is that common in games? If I take someone’s place at a Risk board, can I play well? But in both cases, there is perhaps still some state… At least if you’re playing a human. You might…

Time constraints are a bit of state that can influence how both humans and engines how search for moves. There was some contention over how to understand the training time of AlphaZero in relation to more conventional engines - even as just a physical process this seemed pretty interesting.

Re: Chess, unlike war, is a game of perfect information

#22

Post by CogitoCogito » Sat, Apr 15, 2023, 12:36 AM UTC

thom wrote: post #19

cmeacham98 wrote: post #11

Earlier quoted context omitted.

"Perfect information" is a term of art for games, it doesn't literally mean you are omnipotent.

Is it a particularly useful term here? It seems to mean you could theoretically play perfectly but in almost every real situation you can't, which is true of every human activity (including war). Information is hidden by complexity, but it's still utterly inaccessible.

You know the entire state of the chess board. You don’t know the entire state of your enemy forces. I’m both cases information could be said to be hidden by complexity, but in the case of war information is also just plain hidden.

Edit: it would be similar to your example of war if you e.g. couldn’t see their pieces or something that would cause information asymmetry. This would make the game very different so clearly the term of art _is_ useful and important.

Re: Chess, unlike war, is a game of perfect information

#23

Post by xiphias2 » Sat, Apr 15, 2023, 12:37 AM UTC

Waterluvian wrote: post #15

I find it fascinating how Chess is, in a way, stateless. Other than whether some rules like castling are still valid, you don’t need to have played the previous moves to be able to play the next moves effectively. This got me thinking: is that common in games? If I take someone’s place at a Risk board, can I play well? But in both cases, there is perhaps still some state… At least if you’re playing a human. You might…

I'm not sure about the plan (that takes time of course), but playing styles are quite different.

I as a beginner try not to give my bishops for horses, but more advanced players adjust it to the strategy they want to persue.

Some people have more experience in open, others closed games.

There are lots of other simplifications beginners have to make to be able to not get totally lost.

Re: Chess, unlike war, is a game of perfect information

#24

Post by opportune » Sat, Apr 15, 2023, 12:38 AM UTC

blackpill0w wrote: post #16

opportune wrote: post #12

Chess belongs to a class of games that are particularly interesting to study: it is a finite extensive form game which basically means the game can be modeled as a tree and requires only shared knowledge among participants, all the participants have complete shared knowledge, it’s sequential, has perfect recall (nothing prevents looking backwards at the game state), and a simple payoff function (you win if you checkm…

>But you can perform minimax (which is how AlphaZero works) AlphaZero uses Neural Networks, old engines used to use Alpha-Beta pruning if I am not mistaken but after 2017 (the year AlphaZero papers were released) they started using a combination of the two or just NN. Chess Programming Wiki [1] is an awesome website if you want to learn how Chess engines work in detail (or write one). [1]: https://www.chessprogrammin…

The neural networks are for the evaluation at each node, traversing the game tree is done by using the NN to evaluate how good the position is on the tree’s nodes; how it traverses the tree is minimax with a-b pruning.

In my original comment I didn’t mention pruning or other heuristics like estimating the value of intermediate states because it’s more of an optimization (a very important one!) that doesn’t affect the theory very much.

Re: Chess, unlike war, is a game of perfect information

#25

Post by andrewflnr » Sat, Apr 15, 2023, 12:42 AM UTC

Waterluvian wrote: post #15

I find it fascinating how Chess is, in a way, stateless. Other than whether some rules like castling are still valid, you don’t need to have played the previous moves to be able to play the next moves effectively. This got me thinking: is that common in games? If I take someone’s place at a Risk board, can I play well? But in both cases, there is perhaps still some state… At least if you’re playing a human. You might…

I don't remember the exact mechanics, but Risk has cards that each player holds. If nothing else you'd probably want to see how many of them each player holds to plan the next move.

Re: Chess, unlike war, is a game of perfect information

#26

Post by blackpill0w » Sat, Apr 15, 2023, 12:43 AM UTC

opportune wrote: post #24

blackpill0w wrote: post #16

Earlier quoted context omitted.

>But you can perform minimax (which is how AlphaZero works) AlphaZero uses Neural Networks, old engines used to use Alpha-Beta pruning if I am not mistaken but after 2017 (the year AlphaZero papers were released) they started using a combination of the two or just NN. Chess Programming Wiki [1] is an awesome website if you want to learn how Chess engines work in detail (or write one). [1]: https://www.chessprogrammin…

The neural networks are for the evaluation at each node, traversing the game tree is done by using the NN to evaluate how good the position is on the tree’s nodes; how it traverses the tree is minimax with a-b pruning. In my original comment I didn’t mention pruning or other heuristics like estimating the value of intermediate states because it’s more of an optimization (a very important one!) that doesn’t affect the…

Ah, ok, so Minmax/Alpha-Beta to traverse the game tree and NN to evaluate, my mistake (apparently I am the one who should visit the link I provided :)

Re: Chess, unlike war, is a game of perfect information

#27

Post by mcphage » Sat, Apr 15, 2023, 12:45 AM UTC

kjgkjhfkjf wrote: post #8

In practice, Chess is not a game of perfect information, since you generally don't know which lines your opponent has prepared beforehand.

> In practice, Chess is not a game of perfect information, since you generally don't know which lines your opponent has prepared beforehand

What do you mean when you say "game of perfect information"? What would be an example of one?

Re: Chess, unlike war, is a game of perfect information

#28

Post by charcircuit » Sat, Apr 15, 2023, 12:46 AM UTC

sithlord wrote: post #9

kjgkjhfkjf wrote: post #8

In practice, Chess is not a game of perfect information, since you generally don't know which lines your opponent has prepared beforehand.

that doesn't matter, you have every bit of information from the board to in theory know every possible outcome. It's not like the opponent can't sneak an extra piece in behind your line. Or randomly turn your rook into their queen...

>in theory know every possible outcome

Does your theory model the maximum possible compute of a player and the amount of time they have to spend computing these outcomes on a turn? People have a finite amount of time to make moves or they lose. Even computers can't explore the full search space.

Trivializing the combinatorial explosion of each move is not useful for a chess strategy.

Re: Chess, unlike war, is a game of perfect information

#29

Post by nanis » Sat, Apr 15, 2023, 12:47 AM UTC

cmeacham98 wrote: post #11

kjgkjhfkjf wrote: post #8

In practice, Chess is not a game of perfect information, since you generally don't know which lines your opponent has prepared beforehand.

"Perfect information" is a term of art for games, it doesn't literally mean you are omnipotent.

Exactly. In particular, "perfect information" means you know all the strategies available to your opponent. You also know that your opponent knows this. And you know that your opponent knows that you know that your opponent knows that you know all the strategies to your opponent ad infinitum symmetrically.

In this context, a strategy is a function that maps every history of moves by you and your opponent to an action. So, while chess is theoretically a game of perfect information, in practice it is less so.

Real war is not a game of perfect information, because you do not know all the strategies available to your opponent. In addition, you and your opponent's priors may have an intersection of zero measure which makes things very interesting.

War is what happens when a certain kind of people try to play the game of chicken which is usually not taught in the kind of fun programs like master's of international studies for members of the preferred party because it is too sophisticated due to the fact that it admits an infinite number of Nash equilibria ... instead, such programs prefer to focus on prisoners' dilemma which, having a dominant strategy equilibrium, is more suitable to ensure such students can go back to the bureaucracy after having passed their classes with perfect As and get us in to war.

Re: Chess, unlike war, is a game of perfect information

#30

Post by pedrocr » Sat, Apr 15, 2023, 12:50 AM UTC

opportune wrote: post #24

blackpill0w wrote: post #16

Earlier quoted context omitted.

>But you can perform minimax (which is how AlphaZero works) AlphaZero uses Neural Networks, old engines used to use Alpha-Beta pruning if I am not mistaken but after 2017 (the year AlphaZero papers were released) they started using a combination of the two or just NN. Chess Programming Wiki [1] is an awesome website if you want to learn how Chess engines work in detail (or write one). [1]: https://www.chessprogrammin…

The neural networks are for the evaluation at each node, traversing the game tree is done by using the NN to evaluate how good the position is on the tree’s nodes; how it traverses the tree is minimax with a-b pruning. In my original comment I didn’t mention pruning or other heuristics like estimating the value of intermediate states because it’s more of an optimization (a very important one!) that doesn’t affect the…

AlphaZero uses Monte Carlo Tree Search not MinMax. So it does use a neural network for the search. Modern Stockfish is the one that moved to having a neural network for position evaluation while keeping MinMax with AlphaBeta and heuristics for the search.