Chessmaps Heuristic
Home * Search * Move Ordering * Chessmaps Heuristic
Chessmaps Heuristic,
a move ordering heuristic proposed in 1999 by Kieran Greer et al. [2], which uses a board vector of 64 square controls {dominated by White (1), Black (-1), or neutral (0)}, the Chessmap, along with king locations, to determine an importance vector of square areas or sectors by probing a neural network. Quiet moves are then sorted by the number and ranking of areas, they influence.
Contents
Sectors
Following square sector definition with arbitrary enumeration had most promising results.
╔════╤════╤════╦════╤════╦════╤════╤════╗ 8 ║ │ │ ║ │ ║ │ │ ║ ╟────┼─11─┼────║────┼────║────┼─ 9 ┼────╢ 7 ║ │ │ ║ 7 ║ │ │ ║ ╠══════════════╣────┼────╠══════════════╣ 6 ║ │ │ ║ │ ║ │ │ ║ ╟────┼─10─┼────╠═════════╣────┼─ 8─┼────╢ 5 ║ │ │ ║ │ ║ │ │ ║ ╠══════════════╣─── 6 ───╠══════════════╣ 4 ║ │ │ ║ │ ║ │ │ ║ ╟────┼─ 2─┼────╠═════════╣────┼─ 4─┼────╢ 3 ║ │ │ ║ │ ║ │ │ ║ ╠══════════════╣────┼────╠══════════════╣ 2 ║ │ │ ║ 5 ║ │ │ ║ ╟────┼─ 1─┼────║────┼────║────┼─ 3─┼────╢ 1 ║ │ │ ║ │ ║ │ │ ║ ╚════╧════╧════╩════╧════╩════╧════╧════╝ A B C D E F G H
Neural Network
Topology
The input layer has 70 neurons, 64 for each square of the chessmap, and six for the relative king positions concerning sectors. Each of the 12 output neurons correspondents to one sector. Testing suggested that a 3-layer architecture with 16 hidden nodes being a good number [3].
Training
The supervised learning backpropagation algorithm on a 10000 position training set, generated from complete and randomly chosen chess games taken from master and grandmaster play, was used to train the neural network. For each position in the set, the Chessmap was calculated, and the desired output was a vector quantifying the sector influences of the move played in that position, that is for each sector whether the move increased (+1), decreased (-1) the control, or was neutral (0). All positions were considered from the White side, so when it was Black to move the position was color flipped.
Backpropagation algorithm for a 3-layer network [4]:
initialize the weights in the network (often small random values) do for each example e in the training set O = neural-net-output(network, e) // forward pass T = teacher output for e compute error (T - O) at the output units compute delta_wh for all weights from hidden layer to output layer // backward pass compute delta_wi for all weights from input layer to hidden layer // backward pass continued update the weights in the network until all examples classified correctly or stopping criterion satisfied return the network
Results
Various experiments were conducted to compare the performance of the Chessmaps Heuristic with the History Heuristic on the 24 positions of the Bratko-Kopec Test. Both reduce a randomly ordered tree by about 80%, in favor to HH which can perform the search in much less time. However, along with iterative deepening, and more refined move ordering strategies concerning captures, forced and unsafe moves, the Chessmaps Heuristic got the upper hand in node reductions, specially in combination of an additional heuristic to store the last sector that caused a cutoff at each ply, quite similar to a killer slot. This sector was then retrieved and ordered first in any sector ordering, overriding the output of the neural network [5]. The Chessmaps Heuristic is applied in Kieran Greer's chess playing program ChessMaps, written in C# [6].
Résumé
In his 2012 paper Tree Pruning for New Search Techniques in Computer Games, Kieran Greer further outlines the Chessmaps Heuristic [7]:
This research has been carried out using an existing computer chess game-playing program called Chessmaps. The Chessmaps Heuristic was created as part of a DPhil research project that was completed in 1998. The intention was to try and add some intelligence into a chess game-playing program. If the goal is to build the best possible chess program, then the experience-based approach has probably solved the problem already, as the best programs are now better or at least equal to the best human players. Computer chess can also be used, however, simply as a domain for testing AI-related algorithms. It is still an interesting platform for trying to mimic the human thought process or add human-like intelligence to a game-playing program. Exactly this argument, along with some other points made in this paper, are also written or thought about. While chess provides too much variability for the whole game to be defined, it is still a small enough domain to make it possible to accurately evaluate different kinds of search and evaluation processes. It provides complete information about its environment, meaning that the evaluation functions can be reliable, and is not so complex that trying to encapsulate the process in a comprehensive manner would be impossible.
and further
The Chessmaps Heuristic is therefore used as the move-ordering heuristic at each position in the tree search. The neural network was really only used to order the moves in the “other” moves category, although this would still be a large majority of the moves. The research therefore resulted in a heuristic that was knowledge based, but also still lightweight enough to be used as part of a brute-force alpha-beta (α-β) search. Test results showed that it would reduce the search by more than the History Heuristic, but because of its additional computational requirements; it would use more time to search for a move and would ultimately be inferior. The heuristic, however, proved difficult to optimize in code, for example, trying to create quick move generators through bitmap boards, and so the only way to reduce the search time would probably be to introduce more AI-related techniques into the program. This has led to the following new suggestion for dynamic move sequences.
See also
- Chunking
- Guard Heuristic
- History Heuristic
- Learning
- Neural MoveMap Heuristic
- Neural Networks
- Pattern Recognition
Publications
- Kieran Greer (1998). A Neural Network Based Search Heuristic and its Application to Computer Chess. D.Phil. Thesis, University of Ulster
- Kieran Greer, Piyush Ojha, David A. Bell (1999). A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic. ICCA Journal, Vol. 22, No. 1
- Kieran Greer (2000). Computer chess move-ordering schemes using move influence. Artificial Intelligence, Vol. 120, No. 2
- Levente Kocsis, Jos Uiterwijk, Eric Postma, Jaap van den Herik (2002). The Neural MoveMap Heuristic in Chess. CG 2002
- Kieran Greer (2012). Tree Pruning for New Search Techniques in Computer Games. Advances in Artificial Intelligence, Vol. 2013
External Links
- Backpropagation from Wikipedia
- Feedforward neural network from Wikipedia
- Probabilistic neural network from Wikipedia
- ChessMaps Download by Kieran Greer
References
- ↑ Paul Klee - Polyphony, 1922, Wikimedia Commons, Kunstmuseum Basel
- ↑ Kieran Greer, Piyush Ojha, David A. Bell (1999). A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic. ICCA Journal, Vol. 22, No. 1
- ↑ Kieran Greer (2000). Computer chess move-ordering schemes using move influence. Artificial Intelligence, Vol. 120, No. 2
- ↑ Backpropagation algorithm from Wikipedia
- ↑ Kieran Greer (2000). Computer chess move-ordering schemes using move influence. Artificial Intelligence, Vol. 120, No. 2
- ↑ ChessMaps Download
- ↑ Kieran Greer (2012). Tree Pruning for New Search Techniques in Computer Games. Advances in Artificial Intelligence, Vol. 2013