Difference between revisions of "Chessmaps Heuristic"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Move Ordering * Chessmaps Heuristic''' border|right|thumb|[[Arts#Klee|Paul Klee - Polyphony, 1922 <ref>Arts#...")
 
Line 84: Line 84:
  
 
'''[[Move Ordering|Up one Level]]'''
 
'''[[Move Ordering|Up one Level]]'''
 +
[[Category:Paul Klee]]

Revision as of 13:45, 10 May 2018

Home * Search * Move Ordering * Chessmaps Heuristic

Paul Klee - Polyphony, 1922 [1]

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.

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

Publications

External Links

References

Up one Level