3 ms·
In both games, AIs find moves by way of a search tree that looks at the possible moves and looks for one leading to a win (see e.g. https://en.wikipedia.org/wik
by m12k 9y ago
In both games, AIs find moves by way of a search tree that looks at the possible moves and looks for one leading to a win (see e.g. https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Minimax ). Since testing all possible moves (i.e. an exhaustive search) is infeasible, to be practical they instead use heuristics to decide the value of a given state of the game, so they don't have to search all the way to a win or loss every time. So the core of this is a good heuristic function to evaluate board states to guide the search (although in addition, a lot of the work that was done on chess AIs previously was about pruning the search tree so bad lines of search could be abandoned more quickly). I'm not sure what the state of the art is for this in chess, but one of the innovations of AlphaGo was to train a deep convolution network with data from millions of games with their board states and those games' eventual outcomes and thus creating an evaluation function (the 'goodness' of a state is its likelihood to lead to an eventual win). This may or may not be able to also improve chess AIs, depending on how close to 'perfect' the current best-of-breed heuristic is - someone else would have to chime in on this.
The other big improvement from AlphaGo was using another deep convolution network trained on moves from all those games to create an 'expand' function. Unlike chess, the branching factor of that search tree in Go is ridiculously high, because you can place a stone pretty much anywhere on a big board, while in chess the set of legal moves at any given time is fairly limited. So that neural network they use as an expand function allows them to prioritize the order in which moves are considered. This innovation isn't necessary for chess as the branching factor is much lower - but it might still provide an input for the prioritizing the order in which moves are evaluated.
After learning how all this worked, I understand why Deepmind themselves seem more impressed with their Atari AI, as it actually learned how to play the game from first principles by just looking at the pixels and being told its score, whereas, the approach above, impressive as it is, still actually just plugs the neural networks into existing algorithms, rather than use them for the core decision making process too.