Abstract
Games are an interesting field of study in field of artificial intelligence. Minimax search is a game theory applied to game playing and it has proved to be successful for many games but not all. One of them is the Game of Go. Go is an ancient Chinese Game usually played on 19x19 board. It is a 2-player game where the objective is to capture the opponent’s stones and control as many territories as possible to win the game. Go has its own set of challenges that makes it difficult for Minimax to be efficient. Some of the challenges of Computer Go involve huge branching factor and difficulty to come up with an optimal evaluation function for the leaf nodes. The objective of this project is to implement a system that combines the Selective Minimax search and the Neural Network to evolve the Computer Go player. The limitations of Minimax approach are addressed by using the concepts of Selective Minimax tree and Alpha Beta Pruning. Selective Minimax search provides focused search space and faster evaluation of the moves for the computer. The idea of Selective Minimax is to search and evaluate only those moves that look promising among the legal moves or empty intersections. The Neural Network is trained using supervised learning and Resilient Backpropagation is used for the learning process. The learning method of Resilient Backpropagation proves to be faster and more efficient than the standard Backpropagation for the game of Go. The trained Neural Network combined with an evaluation function is used to evaluate the leaf nodes of the Selective Minimax tree. For Minimax to suggest an optimal move for the computer, it would need to search at greater depths to look ahead which in result would be very costly. For Neural Network to suggest an optimal move, it would need many data and game records to recognize patterns from the board that might not be feasible. Using the hybrid method, the Neural Network helps Minimax to look ahead and the static evaluation function helps Neural Network to suggest a sensible move in case of unseen patterns. This hybrid method provides an advantage over Minimax search as the learning and the experience of Neural Network helps to look ahead without actually searching at greater depths and helps to avoid falling for local maxima. NNGo9x9 uses the hybrid method of Neural Network and Selective Minimax and proves to be an effective player which minimizes the drawbacks of each method.