Breadth over depth in evolving game strategies using genetic algorithms

Traditional search methods have always suffered from both spatial and temporal expansion, especially when exploring deeply in search trees. In this thesis, an optimization technique that reduces the search tree depth and at the same time maintains the same quality of search is proposed. This research examines the Genetic Algorithm methodology as a new technique for evolving optimal strategies by evolving the best weights for the evaluation function. Moreover, this research demonstrates the hypothesis of breadth over depth by showing how an increase in the number of features in an optimized evaluation function in a minimax tree can lead to a reduction in the required search depth. This thesis also investigates the performance of certain types of parallel processing techniques that can be used to reduce the processing time of the Genetic Algorithm.The Awari game is used as the testing model in this thesis. This game has captured the attention of many Artificial Intelligence researchers and computer scientists, due to the number of strategies and calculations involved.It was shown that by coming out with an appropriate representation using the Genetic Algorithm and the added number of features, the value of a deeper search can be overcome and thereby reduce the overall response time and the memory usage.The concept of breadth over depth as proposed in this thesis was found to be successful and would be very useful in areas that require the use of a search tree