Evolving Neural Networks to Focus Minimax Search

Abstract

Neural networks were evolved through genetic algorithms to focus minimax search in the game of Othello. At each level of the search tree, the focus networks decide which moves are promising enough to be explored further. The networks effectively hide problem states from minimax based on the knowledge they have evolved about the limitations of minimax and the evaluation function. Focus networks were encoded in marker--based chromosomes and were evolved against a full--width minimax opponent that used the same evaluation function. The networks were able to guide the search away from poor information, resulting in stronger play while examining fewer states. When evolved with a highly sophisticated evaluation function of the Bill program, the system was able to match Bill's performance while only searching a subset of the moves. 1 Introduction Almost all current game programs rely on the minimax search algorithm (Shannon 1950) to return the best move. Because of time and space constraints...