4 ms·
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 a
by opportune 4y ago
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 checkmate the opponent, in which case the opponent also loses) that is zero-sum.
This makes it so chess has a one-shot sub game perfect equilibrium: https://en.m.wikipedia.org/wiki/Subgame_perfect_equilibrium https://en.m.wikipedia.org/wiki/Subgame_perfect_equilibrium. But, the dimensionality of the possible end states is very high, because there are many different configurations leading to a checkmate, so you can’t easily perform backward induction. But you can perform minimax (which is how Stockfish works): https://en.m.wikipedia.org/wiki/Minimax https://en.m.wikipedia.org/wiki/Minimax
From a game theory perspective chess is really not at all like an actual war, because the properties of the game are different in almost every conceivable way - not just because of perfect information. But, you can model more complex “games” like war in a way that makes them more similar to chess if you wish. Just be careful because ignoring very fundamental differences like the payoff model could greatly affect decision making - for war, you’d probably rather surrender or make minor concessions in most cases than win at the cost of 99% of your people and infrastructure getting destroyed.
- deleted 4y ago[deleted]
- blackpill0w 4y ago>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.chessprogramming.org https://www.chessprogramming.org
- opportune 4y agoThe 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.
- blackpill0w 4y agoAh, 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 :)
- opportune 4y agoNo, it was I that was too lazy to visit the link, or we both were. I got alphazero and stockfish’s implementations mixed up
- pedrocr 4y agoAlphaZero 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.
- opportune 4y agoOops! You are right, I got alphazero and stockfish mixed up.
- ctchocula 4y agoNitpick: MCTS is a heuristic search algorithm as well (just like minimax) that doesn't necessarily need a neural network to operate and the MCTS algorithm existed way before AlphaZero, coming from Reinforcement Learning literature. Deepmind's innovation was to replace two of the 4 classic steps of MCTS (selection step and simulation step) with neural network-based policy and evaluation network.
- hackernewds 4y ago[flagged]
- Our_Benefactors 4y agoPlease next time post your takeaways instead of a repetitive prompt sequence.