Here, 3 AI strategies or techniques have been researched and summarized which are used to develop solutions for the game of chess. The 3 Game Tree and Search algorithms are : Minimax Algorithm , Alpha – Beta Algorithm and Nega Scout Search Algorithm.
The game tree is the directed graph in chess. The positions and edges ( player’s moves ) are represented by node. A search tree is designed for all the moves possible. In chess, the search algorithms are used for finding the best moves out of the various moves by calculating position of all possible moves. In a game graph, the number of outcomes in a node is called the branching factor, the level in the game tree is known as ply and the moves and ply of the game tree are referred to as depth.
Minimax Algorithm :
It is used very widely. It is a recursive algorithm. It minimises the score of the opponent and maximises the score of the self in a game. It uses the depth – first search and evaluates the leaf nodes. The child node with the maximum value is then selected ( for moving white). The child node with a lower value is selected ( for moving black ). This algorithm has many number of paths possible as the branching factor is around 40.
Alpha – Beta Algorithm :
It is better than Minimax Search Algorithm. It uses the concept of branch and bound. It does not search the complete game tree. It decreases the max and min search space. If a good move is found after searching the alternatives, then 1 refutation is needed and not another one. The 2 values used are – Alpha ( the maximizing player is assured for this minimum score ) and Beta ( the minimizing player is assured for this maximum score ) The outcome is not improved but the search becomes faster. If Alpha > Beta and best play is assumed, then position does not occur. The evaluation of search tree is done from left to right. The greyed – out sub trees are ignored as they do not affect the score of node.
Nega Scout :
It is faster than the Alpha – Beta Algorithm in finding the minimax node and has 10 % better performance. It needs a good ordering. It is an iterative deepening technique. It searches with depth i , i + 1 , i + 2 and so on. It uses the concept of dynamic programming. Every iteration gives the best guessed move. Hence, it can be seen that AI is rising in case of chess.
References
chessprogramming, 2017. Alpha-Beta. [Online]
Available at: http://chessprogramming.wikispaces.com/Alpha-Beta
[Accessed 27 September 2017].
Djurhuus, R., 2012. Chess Algorithms. [Online]
Available at: https://www.uio.no/studier/emner/matnat/ifi/INF4130/h12/undervisningsmateriale/chess-algorithms-theory-and-practice-ver2012.pdf
[Accessed 26 September 2017].
Exchange, S., 2017. How does the NegaScout algorithm work?. [Online]
Available at: https://cs.stackexchange.com/questions/1134/how-does-the-negascout-algorithm-work
[Accessed 27 September 2017].
Mubeen, J., 2016. Charting the battle of man vs. machine in Education. [Online]
Available at: https://medium.com/@fjmubeen/charting-the-battle-of-man-vs-machine-in-education-6495ee755f6e
[Accessed 27 Septeber 2017].
Norvig, S. J. R. a. P., 2010. Artificial Intelligence A Modern Approach. [Online]
Available at: http://web.cecs.pdx.edu/~mperkows/CLASS_479/2017_ZZ_00/02__GOOD_Russel=Norvig=Artificial%20Intelligence%20A%20Modern%20Approach%20(3rd%20Edition).pdf
[Accessed 27 September 2017].
Okur, E., 2011. DEVELOPMENT OF AN ADAPTIVE. [Online]
Available at: https://www.cmpe.boun.edu.tr/~gungort/undergraduateprojects/Developing%20an%20Adaptive%20Chess%20Program.pdf
[Accessed 27 September 2017].
Peiravi, M., 2015. THE DESIGN AND IMPLEMENTATION OF AN ADAPTIVE CHESS GAME. [Online]
Available at: http://scholarworks.lib.csusb.edu/cgi/viewcontent.cgi?article=1255&context=etd
[Accessed 26 September 2017].
Stanford, 2013. Deep Blue. [Online]
Available at: http://stanford.edu/~cpiech/cs221/apps/deepBlue.html
[Accessed 25 September 2017].
