Using Intelligent Search Techniques to Play the Game Khet

J. A M Nijssen, J. W H M Uiterwijk

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationBNAIC 2009. Proceedings of the 21st Benelux Conference on Artificial Intelligence
EditorsT. Calders, K. Tuyls, M. Pechenizkiy
Pages185-192
Number of pages8
Publication statusPublished - 2009

Cite this