Note: [1] Universiteit Maastricht, Department of Computer Science, P.O. Box 616, 6200 MD Maastricht, The Netherlands. Email: {m.winands, uiterwijk, herik}@cs.unimaas.nl.
Abstract: Lines of Action (LOA) is a two-person zero-sum chess-like connection game with perfect information. The goal of each side is to connect its own pieces. The state-space complexity and game-tree complexity are comparable with those of Othello. A LOA evaluation function usually consists of a combination of the following components: threats, solid formations, (partial) blocking, centralisation, material advantage, and mobility. In this article we introduce the quad heuristic and disregard mobility. The quad heuristic is used in three qualities, viz. (1) to assess whether a position is non-terminal, (2) to contribute to the evaluation function, and (3) to support the quiescence search. The heuristic is based on quad counts and Euler numbers, and derived from the field of optical character recognition. We show that an evaluation function using the quad heuristic outperforms evaluation functions based on the centre-of-mass approach and on (partial) blocking, i.e., evaluation functions without the quad heuristic. Moreover, it turns out that a quiescence search, which only looks at capturing moves that destroy or create connections, is quite effective when using the quad heuristic. Finally, we provide three conclusions and suggest three ways of improving the use of the quad heuristic in LOA.
DOI: 10.3233/ICG-2001-24102
Journal: ICGA Journal, vol. 24, no. 1, pp. 3-15, 2001
