Using Intelligent Search Techniques to Play the Game Khet

This paper describes the analysis of the game Khet and the implementation of a game engine. Both the state-space complexity and the game-tree complexity of Khet are given. They turn out to be of the same order as those of chess. Based on these results, search techniques are selected that can be used to create an AI player which can play Khet as good as possible. These search techniques are improved to make them run more efficiently, so they can search more extensively and, thus, play stronger. From the experiments that are performed, we can conclude that Khet can best be played by the alphabeta search algorithm, enhanced by a transposition table, killer moves, and Qn-limited search, a variation on quiescence search. These three enhancements yield a significant improvement of the strength of the AI player. Using these search techniques we are able to create a computer program which can play Khet at a strong amateur level