25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Chessmaps Heuristic''' border|right|thumb|[[Arts#Klee|Paul Klee - Polyphony, 1922 <ref>Arts#..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Chessmaps Heuristic'''
[[File:Polyphony.JPG|border|right|thumb|[[Arts#Klee|Paul Klee]] - Polyphony, 1922 <ref>[[Arts#Klee|Paul Klee]] - Polyphony, 1922, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Kunstmuseum_Basel Kunstmuseum Basel]</ref>]]
'''Chessmaps Heuristic''',<br/>
a move ordering heuristic proposed in 1999 by [[Kieran Greer]] et al. <ref>[[Kieran Greer]], [[Piyush Ojha]], [[David A. Bell]] ('''1999'''). ''A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic''. [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]]</ref>, which uses a board vector of 64 [[Square Control|square controls]] {dominated by White (1), Black (-1), or neutral (0)}, the '''Chessmap''', along with king locations, to determine an importance vector of [[Squares|square]] areas or '''sectors''' by probing a [[Neural Networks|neural network]]. [[Quiet Moves|Quiet moves]] are then sorted by the number and ranking of areas, they influence.
=Sectors=
Following square sector definition with arbitrary enumeration had most promising results.
<pre>
╔════╤════╤════╦════╤════╦════╤════╤════╗
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
</pre>
=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 <ref>[[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2</ref>.
==Training==
The [[Supervised Learning|supervised learning]] [[Neural Networks#Backpropagation|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 Flipping|color flipped]].
Backpropagation algorithm for a 3-layer network <ref>[https://en.wikipedia.org/wiki/Backpropagation#Algorithm Backpropagation algorithm from Wikipedia]</ref>:
<pre>
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
</pre>
=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|iterative deepening]], and more refined move ordering strategies concerning [[Captures|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|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 <ref>[[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2</ref>. The Chessmaps Heuristic is applied in [[Kieran Greer|Kieran Greer's]] chess playing program [[ChessMaps]], written in [[C sharp|C#]] <ref>[http://www.distributedcomputingsystems.co.uk/chessmapsdownload.html ChessMaps Download]</ref>.
=Résumé=
In his 2012 paper ''Tree Pruning for New Search Techniques in Computer Games'', [[Kieran Greer]] further outlines the Chessmaps Heuristic <ref>[[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013</ref>:
This research has been carried out using an existing computer chess game-playing program called [[ChessMaps|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, [https://en.wikipedia.org/wiki/University_of_Ulster University of Ulster]
* [[Kieran Greer]], [[Piyush Ojha]], [[David A. Bell]] ('''1999'''). ''A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic''. [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]]
* [[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2
* [[Levente Kocsis]], [[Jos Uiterwijk]], [[Eric Postma]], [[Jaap van den Herik]] ('''2002'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-40031-8_11 The Neural MoveMap Heuristic in Chess]''. [[CG 2002]]
* [[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013
=External Links=
* [https://en.wikipedia.org/wiki/Backpropagation Backpropagation from Wikipedia]
* [https://en.wikipedia.org/wiki/Feedforward_neural_network Feedforward neural network from Wikipedia]
* [https://en.wikipedia.org/wiki/Probabilistic_neural_network Probabilistic neural network from Wikipedia]
* [http://www.distributedcomputingsystems.co.uk/chessmapsdownload.html ChessMaps Download] by [[Kieran Greer]]
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
[[File:Polyphony.JPG|border|right|thumb|[[Arts#Klee|Paul Klee]] - Polyphony, 1922 <ref>[[Arts#Klee|Paul Klee]] - Polyphony, 1922, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Kunstmuseum_Basel Kunstmuseum Basel]</ref>]]
'''Chessmaps Heuristic''',<br/>
a move ordering heuristic proposed in 1999 by [[Kieran Greer]] et al. <ref>[[Kieran Greer]], [[Piyush Ojha]], [[David A. Bell]] ('''1999'''). ''A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic''. [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]]</ref>, which uses a board vector of 64 [[Square Control|square controls]] {dominated by White (1), Black (-1), or neutral (0)}, the '''Chessmap''', along with king locations, to determine an importance vector of [[Squares|square]] areas or '''sectors''' by probing a [[Neural Networks|neural network]]. [[Quiet Moves|Quiet moves]] are then sorted by the number and ranking of areas, they influence.
=Sectors=
Following square sector definition with arbitrary enumeration had most promising results.
<pre>
╔════╤════╤════╦════╤════╦════╤════╤════╗
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
</pre>
=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 <ref>[[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2</ref>.
==Training==
The [[Supervised Learning|supervised learning]] [[Neural Networks#Backpropagation|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 Flipping|color flipped]].
Backpropagation algorithm for a 3-layer network <ref>[https://en.wikipedia.org/wiki/Backpropagation#Algorithm Backpropagation algorithm from Wikipedia]</ref>:
<pre>
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
</pre>
=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|iterative deepening]], and more refined move ordering strategies concerning [[Captures|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|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 <ref>[[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2</ref>. The Chessmaps Heuristic is applied in [[Kieran Greer|Kieran Greer's]] chess playing program [[ChessMaps]], written in [[C sharp|C#]] <ref>[http://www.distributedcomputingsystems.co.uk/chessmapsdownload.html ChessMaps Download]</ref>.
=Résumé=
In his 2012 paper ''Tree Pruning for New Search Techniques in Computer Games'', [[Kieran Greer]] further outlines the Chessmaps Heuristic <ref>[[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013</ref>:
This research has been carried out using an existing computer chess game-playing program called [[ChessMaps|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, [https://en.wikipedia.org/wiki/University_of_Ulster University of Ulster]
* [[Kieran Greer]], [[Piyush Ojha]], [[David A. Bell]] ('''1999'''). ''A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic''. [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]]
* [[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2
* [[Levente Kocsis]], [[Jos Uiterwijk]], [[Eric Postma]], [[Jaap van den Herik]] ('''2002'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-40031-8_11 The Neural MoveMap Heuristic in Chess]''. [[CG 2002]]
* [[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013
=External Links=
* [https://en.wikipedia.org/wiki/Backpropagation Backpropagation from Wikipedia]
* [https://en.wikipedia.org/wiki/Feedforward_neural_network Feedforward neural network from Wikipedia]
* [https://en.wikipedia.org/wiki/Probabilistic_neural_network Probabilistic neural network from Wikipedia]
* [http://www.distributedcomputingsystems.co.uk/chessmapsdownload.html ChessMaps Download] by [[Kieran Greer]]
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
