Which AI algorithm is best for chess?

Question

I'm working on my chess bot, and I would like to implement simple artificial intelligence for it. I'm new in it, so I'm unsure how to do it specifically on chess. I heard about Q-learning, Supervised/Unsupervised learning, Genetic algorithm, etc., which probably is not for chess. I wondered how AlphaZero was created? Probably Genetic algorithm, but chess is the game where "if A then B" might not work. It means that Q-learning is also bad for it, and so on.

Any suggestions what to use?

NOTE: I found dataset, though its also includes low-rated player games, so I'm unsure if it's ok to train bot with this

Answer 1

I'm not an expert in the field, but I want to draw your attention to reinforcement learning (which is also mentioned in the Wikipedia article on AlphaZero).

The book "Reinforcement Learning: An Introduction" (Richard S. Sutton and Andrew G. Barto) is a good starting point. Seems to be kind of "the bible" for starting with reinforcement learning.

There are simple implementations of games like "TicTacToe" (a lot of examples online), where you can get a good idea how to start. There also is an R package on TicTacToe.

I also noticed that there are chess projects on github (e.g. Python) which you might find interesting.

Answer 2

This is a massive question. There are two basic approaches, with the key difference being the search algorithm.

The first approach, currently used by the world's strongest engine Stockfish, involves minimax as the search algorithm. It then calls the NNUE to evaluate the position at the end of the search tree. The minimax algorithm involves a lot of human knowledge to prune off unnecessary branches, and is very complicated; it's not surprising that most people find Stockfish's search algorithm a black box.

The second approach, used by the second-strongest engine Leela Chess Zero, involves Monte Carlo Tree Search. There is again a neural network that takes the current position and outputs a list of candidate moves, with win percentages for each. The engine then divides its time among the most promising moves, calling the neural network at each node. Leela's neural network is trained from self-play with zero prior human knowledge - something that is very computationally intensive.

You can find a lot more details on the Chess Programming wiki, as well as several questions on the Chess.SE (such as this or this).

Answer 3

AlphaZero algorithm was implemented in Leela Chess Zero and was actually one of the leaders at least before Stockfish implemented its own NN assistant algorithm.

Here: https://en.wikipedia.org/wiki/Leela_Chess_Zero

NNs: https://training.lczero.org/networks/?show_all=0

Code: https://github.com/LeelaChessZero/lc0/releases

It has distributive learning on Nvidia GPUs using tensor cores of 20th and 30th Series, so is a state-of-the-art system, fully opensource including all (a lot of them) NNs weights.

Answer 4

I would recommend a classical AI approach.

I suggest you implement a Minimax with depth limiting or A* with depth limiting. In these scenarios, you basically rebuild the game tree and try all moves and observe what happens ("OK, if I move this here, I gain advantage, if I move this there, I gain more advantage, etc....")

If you are dead set on implementing a machine learning approach, Deep Q Learning is worth a shot. Here you attempt to teach a Deep Neural network on how to "rate" moves, so then you just rate all the moves and pick the best one.