ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Generalized Widening

Tristan Cazenave

We present a new threat based search algorithm that outperforms other threat based search algorithms and selective knowledge-based Alpha-beta for open life and death problem solving in the game of Go. It generalizes the Iterative Widening algorithm which consists in iteratively increasing the threat searched at the root. The main idea of Generalized Widening is to perform Iterative Widening at all max nodes of the search tree instead of performing it only at the root. Experimental results show it can be three times faster than selective knowledge-based Alpha-beta using the same knowledge, and eight times faster than simple Iterative Widening. The performance against Alpha-beta can possibly be greatly enhanced by adding more knowledge in the selection of moves during the verification of the threats.

Keywords: Game playing

Citation: Tristan Cazenave: Generalized Widening. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.156-160.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).