A Go algorithm for chess programmers to try ?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dan Andersson
Posts: 442
Joined: Wed Mar 08, 2006 7:54 pm

Re: A Go algorithm for chess programmers to try ?

Post by Dan Andersson » Wed Jun 06, 2007 7:58 am

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
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: A Go algorithm for chess programmers to try ?

Post by Gerd Isenberg » Wed Jun 06, 2007 1:50 pm

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
Posts: 434
Joined: Mon Apr 24, 2006 6:06 pm
Contact:

Re: A Go algorithm for chess programmers to try ?

Post by Rémi Coulom » Wed Jun 06, 2007 2:40 pm

Hi Gerd,
Gerd Isenberg wrote: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.
Gerd Isenberg wrote: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
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: A Go algorithm for chess programmers to try ?

Post by Gerd Isenberg » Wed Jun 06, 2007 6:05 pm

Rémi Coulom wrote:Hi Gerd,
Gerd Isenberg wrote: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.
Gerd Isenberg wrote: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
Posts: 434
Joined: Mon Apr 24, 2006 6:06 pm
Contact:

Re: A Go algorithm for chess programmers to try ?

Post by Rémi Coulom » Wed Jun 06, 2007 6:21 pm

Gerd Isenberg wrote: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

Post Reply