The Rise of Chess AI Part 2: A complex game requires a complex solution.

The game of chess is incredibly complex, with approximately 10^50 positions possible on the board (Dreżewski & Wątor, 2021). This is a huge amount of positions, and current computer resources are not powerful enough to find an explicit solution to a given board state but rather they utilize various statistical methods and/or machine learning models to estimate the strength of a given position (Dreżewski & Wątor, 2021) from this we can strongly display the intersection between the topic of computers solving problems and Statistics.

The most used statistical metric in chess to gauge the strength of a position is that of centipawn-loss (Dreżewski & Wątor, 2021; Babic, 2017; McIlroy-Young, Wang, Sen, Kleinberg & Anderson, 2021; Barnes & Hernandez-Castro, 2015). At its most basic level the formula for centipawn loss is: (x/100) where 100 represents the value of 1 pawn, and x represents the “loss” that particular move caused (Babic, 2017), good players and AI will have exceptionally low values for this metric and industry professionals will define the loss (x) in different ways. This metric is very intuitive and easy to understand as it has a high level of abstraction by representing the current position of the board for a current player in relation to a dimension (centipawns lost per move) (Babic, 2017), and therefore can be easily understood. In relation to AI, multiple top performing Engines measure the optimality of such moves using centipawn-loss such as Stockfish 14 which in conjunction with centipawn loss (Maharaj & Polson, 2021) uses other complicated evaluation functions and shallow networks for easy evaluation.

Centipawn loss as calculated by computers (McIlroy-Young, Wang, Sen, Kleinberg & Anderson, 2021) has often been used not only to evaluate their own positions but also that of human players. Specific processes have been created to rank a position or a players overall performance such as Guid and Bratko (2006) an Average Difference statistical model which can be defined as ∑| x−y/𝑛𝑀 where x is the best move evaluation, y is played moves evaluation while nM is the number of moves. An interesting outcome due to the creation of this metric was the ability for computers to track and display the blunder rate of human players in relation to the complexity of a given position.

Figure 1: Average Error at different levels of positional complexity in chess (Guid & Bratko, 2006)

The previously mentioned shallow networks which Stockfish 14 (Maharaj & Polson, 2021) and other effective Chess AI make use of utilize Alpha-Beta Pruning (Marckel, 2017; Putra & Heryawan, 2017) which is the technique of reviewing a limited number of future moves, evaluating the position and choosing the move which is most likely to result in a victory. This contrasts with Deep Blue which was unable to accurately rule out a specific branch. The specific type of tree commonly used in chess is an adversarial tree due to chess being a zero-sum, two player, perfect information game (Marckel, 2017). The two defining parts of a tree is the “Branching Factor”, which is the number of possible options which can be taken from a node and “Depth” which is the number of moves a specific branch or line follows (Marckel, 2017). Each node is evaluated according to a linear scoring polynomial, and the Alpha-Beta will make its choice based off of this.

V= c1 f1 + c2 f2 + ... + cn fn

With the node V being the sum of evaluations of different features (pieces, pawns), cn multiplied by a function giving it weight fn (Marckel, 2017). This is a process which uses elements of minimax evaluation but is more efficient in that it prunes away branches which could not possibly influence its final decision (Russell et al., 2021).

Figure 2: An example of a large Alpha-Beta pruned tree (Marckel, 2017)

All Artificial Intelligence which has been discussed so far in some way rely on statistical models, rules and also heuristics which are crafted by strong human players (Silver, Hubert, Schrittwieser & Hassabis, 2018). However since 2017 a new type of Chess engine entered the scene which uses Deep Neural Networks and general purpose algorithms (Silver, Hubert, Schrittwieser & Hassabis, 2018), the most famous of which is AlphaZero. AlphaZero would learn how to play chess completely independently of outside influence, using a process called reinforcement learning (Silver, Hubert, Schrittwieser & Hassabis, 2018) which is the process of learning through trial and error by playing itself. At first AlphaZero would play random moves but over time it would learn and become stronger at the game, after approximately 700’000 games AlphaZero managed to reach the same ELO rating as the current top performing AI Stockfish (Silver et al., 2018).

All Artificial Intelligence which has been discussed so far in some way rely on statistical models, rules and also heuristics which are crafted by strong human players (Silver, Hubert, Schrittwieser & Hassabis, 2018). However since 2017 a new type of Chess engine entered the scene which uses Deep Neural Networks and general purpose algorithms (Silver, Hubert, Schrittwieser & Hassabis, 2018), the most famous of which is AlphaZero. AlphaZero would learn how to play chess completely independently of outside influence, using a process called reinforcement learning (Silver, Hubert, Schrittwieser & Hassabis, 2018) which is the process of learning through trial and error by playing itself. At first AlphaZero would play random moves but over time it would learn and become stronger at the game, after approximately 700’000 games AlphaZero managed to reach the same ELO rating as the previoustop performing Chess AI: Stockfish (Silver et al., 2018).

Figure 3: Alpha Zeros Search Procedure after 10x simulations. (Silver, Hubert, Schrittwieser & Hassabis, 2018)

The above figure (Figure 3) displays AlphaZeros search procedure depending on the amount simulations. Eventually Alpha Zero will search very few branches to a high level of depth, these being the two dimensions discussed by Marckel (2017). This leads to AlphaZero’s search per decision to be more defined, leading to less overall decisions being considered (Silver, Hubert, Schrittwieser & Hassabis, 2018) while producing more rich analysis deeper into the game. As displayed in the below figure (figure 4), it can be seen that AlphaZero searched far less moves, however the analysis of these moves was more impactful and accurate. After defeating StockFish in 2017 with a score of 155 wins/ 839 draws and 6 losses (Silver et al., 2018) the approach which AlphaZero took, using a neural network was adopted by the industry as the most recent iterations of StockFish, Komodo and others employ a neural network.

Figure 4: Amount of Search Per Decision, Human GM, AlphaZero, Chess Engine (Silver, Hubert, Schrittwieser & Hassabis, 2018)

Chess is one of many incredibly complex games which are used to display the progress of AI. I have attempted to display a set of the many tools which AI use to evaluate any given position in chess; such as statistical models and alpha-beta pruning (Barnes & Hernandez-Castro, 2015; McIlroy-Young, Wang, Sen, Kleinberg & Anderson, 2021) as well as the recent developments in neural networks which enables AI to gain, without human input, the ability to play Chess and other games to a very high ability (Silver et al., 2018; Silver, Hubert, Schrittwieser & Hassabis, 2018). Therefore displaying both the use of statistical modelling, in ranking AI and playing Chess as well as the use of AI in “solving” the problem of chess.

Rerferences

AI impacts. (2018). Historic trends in chess AI. Retrieved 13 November 2021, from https://aiimpacts.org/historic-trends-in-chess-ai/

Babic, A. (2017). A rating model for individual player qualities based on team results, applied in football (PH.D). University of Twente.

Barnes, D., & Hernandez-Castro, J. (2015). On the limits of engine analysis for cheating detection in chess. Computers & Security, 48, 58-73. doi: 10.1016/j.cose.2014.10.002

Blanch, A., Aluja, A., & Badia, J. (2016). Evaluating the association of age with standard and blitz Elo chess ratings: Sex and country variability. Personality And Individual Differences, 101, 468. doi: 10.1016/j.paid.2016.05.093

Campbell, M., Hoane, A., & Hsu, F. (2002). Deep Blue. Artificial Intelligence, 134(1-2), 57-83. https://doi.org/10.1016/s0004-3702(01)00129-1

Dreżewski, R., & Wątor, G. (2021). Chess as Sequential Data in a Chess Match Outcome Prediction Using Deep Learning with Various Chessboard Representations. Procedia Computer Science, 192, 1760-1769. https://doi.org/10.1016/j.procs.2021.08.180

Ensmenger, N. (2011). Is chess the drosophila of artificial intelligence? A social history of an algorithm. Social Studies Of Science, 42(1), 5-30. doi: 10.1177/0306312711424596

Grabner, R. (2014). The role of intelligence for performance in the prototypical expertise domain of chess. Intelligence, 45, 26-33. doi: 10.1016/j.intell.2013.07.023

Guid, M., & Bratko, I. (2006). COMPUTER ANALYSIS OF WORLD CHESS CHAMPIONS. ICGA Journal, 29(2), 65-73. doi: 10.3233/icg-2006-29203

Korf, R. (1997). Does Deep Blue use Artificial Intelligence?1. ICGA Journal, 20(4), 243-245. https://doi.org/10.3233/icg-1997-20404

Levinson, R., Hsu, F., Marsland, T., Schaeffer, J., & Wilkins, D. (1991). The Role of Chess in Artificial Intelligence Research. International Joint Conferences on Artificial Intelligence Organization.

Levy, D. (2005). II People vs Computers World Chess Team Match. Chessbase. Retrieved 13 November 2021, from https://en.chessbase.com/post/bilbao-the-humans-strike-back.

Maharaj, S., & Polson, N. (2021). Karpov’s Queen Sacrifices and AI. The University of Chicago Booth School of Business.

Marckel, O. (2017). Alpha-beta Pruning in Chess Engines. University of Minnesota.

McIlroy-Young, R., Sen, S., Kleinberg, J., & Anderson, A. (2020). Aligning Superhuman AI with Human Behavior. Proceedings Of The 26Th ACM SIGKDD International Conference On Knowledge Discovery & Data Mining. https://doi.org/10.1145/3394486.3403219

McIlroy-Young, R., Wang, R., Sen, S., Kleinberg, J., & Anderson, A. (2021). Learning Personalized Models of Human Behavior in Chess. In Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research.

Ninan, S. (2021). To GM or not to GM: Inside calls for FIDE to change Grandmaster requirements. ESPN.

Putra, W., & Heryawan, L. (2017). APPLYING ALPHA-BETA ALGORITHM IN A CHESS ENGINE. Jurnal Teknosains, 6(1), 37. doi: 10.22146/teknosains.11380

Raedt, L., Kersting, K., Natarajan, S., & Poole, D. (2016). Statistical Relational Artificial Intelligence: Logic, Probability, and Computation. Synthesis Lectures On Artificial Intelligence And Machine Learning, 10(2), 1-189. doi: 10.2200/s00692ed1v01y201601aim032

Regan, K., & McC. Haworth, G. (2011). Intrinsic Chess Ratings. Association for the Advancement of Artificial Intelligence.

Russell, S., Norvig, P., Chang, M., Devlin, J., Dragan, A., & Forsyth, D. et al. (2021). Artificial intelligence. Hoboken, N.J: Pearson.

Silver, D., Hubert, T., Schrittwieser, J., & Hassabis, D. (2018). AlphaZero: Shedding new light on chess, shogi, and Go. DeepMind.

Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., & Guez, A. et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419), 1140-1144. doi: 10.1126/science.aar6404

Wilkenfeld, Y. (2019). Can Chess Survive Artificial Intelligence? The New Atlantis, 58, 37–45. https://www.jstor.org/stable/26609113