A Go algorithm for chess programmers to try ?

[Dan Andersson]

There is some synchronicity at work here. I kept hearing the UCT-MC on the Go list. All the while I was playing at extracting metrics from graphs and networks using random walks. Getting reliable metrics through sampling led me to existing MCMC. Extracting/optimizing metrics seem a great fit for search and/or Genetic algorithms.

MvH Dan Andersson

[Gerd Isenberg]

Hi Rémi,

Thanks for providing the paper, but sorry for my lack of understanding - I am a novice in statistics as well in neuronal nets, temporal differences and such stuff. I read your paper a few times - and sometimes there was a kind of flighty mental dust which gives me the illusion to understand something

A few questions related to the domain specific features. You somehow index the database of your learned values by a move - like indexing a history table? Each feature has a kind of let say persistant history table with former learned values. And if featuers of a move have in combination (weighted by game-state?) a lower probability than some threshold, it is a candidate for reduction or even pruning. Does that roughly describe how it works?

What features would you suggest for the domain of chess for your algorithm? Are there disjoint features considering game state, closed/open positions, blocked pawn center, opposite castles, etc.? According to your distance features - how would those translate to chess since in Go you have only to-squares, but not from-to. Is it something like center- or piece-king tropism?

Thanks for your patience,
Gerd

[Rémi Coulom]

Hi Gerd,

A few questions related to the domain specific features. You somehow index the database of your learned values by a move - like indexing a history table? Each feature has a kind of let say persistant history table with former learned values. And if featuers of a move have in combination (weighted by game-state?) a lower probability than some threshold, it is a candidate for reduction or even pruning. Does that roughly describe how it works?

Yes, I think so (I am not completely certain what you mean). Features are properties of a move. History table of that move can be used, but any other property would work: SEE value, check, capture, ... . The database of games serves to estimate how good (or bad) each feature is.

What features would you suggest for the domain of chess for your algorithm? Are there disjoint features considering game state, closed/open positions, blocked pawn center, opposite castles, etc.? According to your distance features - how would those translate to chess since in Go you have only to-squares, but not from-to. Is it something like center- or piece-king tropism?

Some features I would try:

1. SEE value
2. MVV/LVA value
3. Check
4. Capture previous move
5. Move piece attacked by previous move
6. Attack previous move
7. Attack/capture piece not defended any more because of previous move
8. Number of pieces attacked
9. Number of pieces defended
10. Pieces no more defended because of this move
11. Pieces no more attacked because of this move
12. Piece type and destination square
13. Move history (history heuristic)

You can imagine plenty more. 4,5,6,7 would be the chess analogous to "distance to the previous move" in Go.

I suppose plenty of programs already use such heuristics to order/reduce/prune their moves. My algorithm allows to automatically compute a move "Elo strength" by estimating the strength of each value that these features may take. It is convenient because I do not have to tune manually how these features are combined. I can also rapidly test whether a new feature brings significant additional information.

Also, in order to find the right features, I can automatically detect when a reduction/pruning was made by error. By looking at the errors, I can usually come up with a domain-specific feature that will avoid it.

Rémi

[Gerd Isenberg]

Hi Gerd,

A few questions related to the domain specific features. You somehow index the database of your learned values by a move - like indexing a history table? Each feature has a kind of let say persistant history table with former learned values. And if featuers of a move have in combination (weighted by game-state?) a lower probability than some threshold, it is a candidate for reduction or even pruning. Does that roughly describe how it works?

Yes, I think so (I am not completely certain what you mean). Features are properties of a move. History table of that move can be used, but any other property would work: SEE value, check, capture, ... . The database of games serves to estimate how good (or bad) each feature is.

What features would you suggest for the domain of chess for your algorithm? Are there disjoint features considering game state, closed/open positions, blocked pawn center, opposite castles, etc.? According to your distance features - how would those translate to chess since in Go you have only to-squares, but not from-to. Is it something like center- or piece-king tropism?

Some features I would try:

1. SEE value
2. MVV/LVA value
3. Check
4. Capture previous move
5. Move piece attacked by previous move
6. Attack previous move
7. Attack/capture piece not defended any more because of previous move
8. Number of pieces attacked
9. Number of pieces defended
10. Pieces no more defended because of this move
11. Pieces no more attacked because of this move
12. Piece type and destination square
13. Move history (history heuristic)

You can imagine plenty more. 4,5,6,7 would be the chess analogous to "distance to the previous move" in Go.

I suppose plenty of programs already use such heuristics to order/reduce/prune their moves. My algorithm allows to automatically compute a move "Elo strength" by estimating the strength of each value that these features may take. It is convenient because I do not have to tune manually how these features are combined. I can also rapidly test whether a new feature brings significant additional information.

Also, in order to find the right features, I can automatically detect when a reduction/pruning was made by error. By looking at the errors, I can usually come up with a domain-specific feature that will avoid it.

Rémi

Thanks,

that sounds very interesting and promising - you somehow autoscale the weights of different aspects of a move to get a score for move-sorting and/or reduction/extension/pruning. But I still have to think how to differentiate between game-states, and for instance pawn-structure properties and king-placement. And between moves of a defender versus a attacker (or weaker versus stronger side) on one wing or center, and how does it interact with all apects of the evaluation.

Gerd

[Rémi Coulom]

that sounds very interesting and promising - you somehow autoscale the weights of different aspects of a move to get a score for move-sorting and/or reduction/extension/pruning. But I still have to think how to differentiate between game-states, and for instance pawn-structure properties and king-placement. And between moves of a defender versus a attacker (or weaker versus stronger side) on one wing or center, and how does it interact with all apects of the evaluation.

In Monte-Carlo tree search, there is no position-evaluation function. The only heuristics are in move evaluation for ordering/pruning. Each branch of the tree is expanded until a terminal position is found. It is scored as a win or a loss. That is what makes MC search so special and cool. A lot of complex notions, such as King safety, should automatically "emerge" from the search. I wonder what kind of playing style it would produce in chess. Certainly not materialistic.

Some notions automatically emerge from the search when doing alpha-beta too, but I feel that what MC does is much more powerful. In a classical chess program, you have to compensate the short-sightedness of the search with evaluation features that anticipate what will happen in the long term. With MC search, the search goes to the end of the game, so the search is not blind to long-term considerations.

Rémi