A Pattern-Oriented Approach to Move Ordering: The Chessmaps Heuristic

Article type: Research Article

Authors: Greer, K.R.C | Ojha, P.C. | Bell, D.A.^{; 1}

Affiliations: Jordanstown, N. Ireland

Note: [1] School of Information and Software Engineering, Faculty of Informatics, University of Ulster at Jordanstown, N. Ireland. Email: [email protected].

Abstract: A move-ordering method is presented that orders most moves by using a neural network in the form of the chessmaps heuristic. The neural network is trained to order sectors, or areas of the chessboard, depending on the territorial control of each side. Moves are then ordered depending on which sectors they influence. The complete move-ordering method takes account of immediate tactical threats, in the form of forced or capture moves, before the positional evaluation of the chessmaps heuristic is used. The chessmaps heuristic has extracted some intelligent chess information from the examples it has been trained on. In particular, it has learnt a very basic strategy. When White controls the whole chessboard, the chessmaps heuristic suggests attacking sectors for White. When Black controls the whole chessboard, the chessmaps heuristic suggests defensive sectors for White. When the amount of control is equal, the chessmaps heuristic suggests attacking sectors where defensive factors play a part. So, it looks like the program knows something about when to attack or defend. The heuristic has also learnt some notions of centralisation. Because this A1 approach is relatively simple, it is suitable when supported by a substantive brute-force search. Preliminary test runs comparing this move-ordering method with other heuristic combinations involving the killer and history heuristics are encouraging, since our move-ordering method searched fewer nodes.

DOI: 10.3233/ICG-1999-22103

Journal: ICGA Journal, vol. 22, no. 1, pp. 13-21, 1999