The LBR move ordering heuristic

[sje]

The LBR move ordering heuristic

I've done some experimentation with what I call the LBR (Last Best Reply) move ordering heuristic. An LBR move is something like a killer move, but more specialized. Here's how it works:

1) At each node in a search, the prior move (played at ply N-1) and the best move (if any) found by the search are recorded. At the root (ply 0), the prior move is the last move played in the game (if any). These two moves are the "reply pair".

2) For each ply in a search, a store of reply pairs is maintained. In the new Chess In Lisp toolkit, this store is a binary tree with each node key the move hash of the prior move and the node value is the most recent best reply for that move. For both the prior move and the reply move, five components are used for matching: from/to squares, from/to men, and the move special case (regular, en passant, castling, promotion); checking status is ignored. So the keying is more specific than the common from/to square pairing seen in the usual history reply heuristic.

3) At each node in a search at move ordering time, the reply pair store is probed for a match of the prior move. If found, the move list for the current node is scanned for a match of the stored best reply. If the stored best reply is matched, then the corresponding move in the move list in given an ordering bonus so it will be chosen early in the scan.

Have others tried this approach? Sometimes it works and sometimes it doesn't. It appears that a lot is dependent on how much of a bonus is given to the matched generated move.

[Sven]

It sounds interesting. I have never tried it. The first thing that comes into my mind is that this heuristic might interfere with the regular ordering heuristics for captures since your idea includes the "from/to men" information. To avoid this interference, why not skipping the "to" and only keeping the "from men", while not using LBR for captures and promotions at all?

Another point is, it is possible that the "move special case" part is mostly redundant. A pawn move from 7th to 8th (2nd to 1st) rank is always a promotion. A diagonal pawn move to an empty square (if you keep the "to men") is always an e.p. move. So only castling would make a difference but this is a very rare move.

Nevertheless I think that LBR may be worth a try.

Sven

[sje]

First, I should point out that Jos Uiterwijk wrote about a related "Countermove" heuristic in 1992. See: http://chessprogramming.wikispaces.com/ ... +Heuristic

However, this employed a butterfly board index coding and did not consider the moving man value, the captured man value, or the move special case.

Coding the special move case does help for promotion (consider underpromotions, each with their own hash contribution) , but not for castling. It can help for en passant depending on how the "captured" man is coded. If the captured man in an en passant move is recorded as an empty square, then coding the special case makes no contribution.

[sje]

Other issues:

1) At present, the "best move" at a node exists only if the analysis for that move improves on the alpha score.

2) At present, a separate LBR store is kept for each ply. It may be an improvement to have only two stores (one for each color) maintained for an entire search.

3) At present, only the hash of the last played move is used for a key in an LBR store. This could be extended to a hash of the last two (or more) played moves.

4) Another idea is to use a wildcard for the last played move and use the second to last played move (one ply up) as an LBR store key.

Postscript: I've gotten a Wikispace account so I can contribute to the chess programming wiki. So much has been done by others here so I guess I should be dong some help too.

[Gerd Isenberg]

Postscript: I've gotten a Wikispace account so I can contribute to the chess programming wiki. So much has been done by others here so I guess I should be dong some help too.

You are welcome!

[sje]

Postscript: I've gotten a Wikispace account so I can contribute to the chess programming wiki. So much has been done by others here so I guess I should be dong some help too.

You are welcome!

A while ago I was looking at the general Wikipedia entry for chess tablebases. Now, back in 2002 or so, Chess Life carried a good article on tablebases and it included accurate references to the work of Ken Thompson, myself, and Eugene Namilov. But somehow, the Wikipedia entry forgot to mention me in any way including the fact that it was I who first associated the term "tablebase" as a synonym for the phrase "complete endgame position database". So maybe that entry needs a few edits.

[sje]

The wiki page is up:

http://chessprogramming.wikispaces.com/Last+Best+Reply

[mcostalba]

The wiki page is up:

http://chessprogramming.wikispaces.com/Last+Best+Reply

Please don't take this personaly, but I think is misleading adding not tested stuff to chessprogrammingwiki.

This wiki is a real reference for all of us and IMHO is critical for keeping the high quality standard of that site that all the information that goes in is, ehmm, high quality that, for chess engine software, it means reliably tested and proven.

I can easily full chessprogrammingwiki with tens of my "new" ideas that I got in this years, some of them even very pretty and cool, the kind of "it must work because is a smart one and is obvious that it works"...the reality is that most of them didin't, but only after testing I was able to spot that the "smart and clever" idea was just garbage.

For novices and for people starting with chess programming can be frustrating trying to implement ideas considered "good" and don't get any result and this could make them leave early. So because what is written in chessprogramming wiki is considered "good" by a lot of people (me included) I think is a disservice to the commuity adding random stuff there. With "random stuff" I mean not properly tested (please let me be pedantic and indulge on "properly" word).

So I suggest to remove that part until not proven or at least add a notice in which is clearly written that is a "Not tested" idea.

[Gerd Isenberg]

The wiki page is up:

http://chessprogramming.wikispaces.com/Last+Best+Reply

Please don't take this personaly, but I think is misleading adding not tested stuff to chessprogrammingwiki.

This wiki is a real reference for all of us and IMHO is critical for keeping the high quality standard of that site that all the information that goes in is, ehmm, high quality that, for chess engine software, it means reliably tested and proven.

I can easily full chessprogrammingwiki with tens of my "new" ideas that I got in this years, some of them even very pretty and cool, the kind of "it must work because is a smart one and is obvious that it works"...the reality is that most of them didin't, but only after testing I was able to spot that the "smart and clever" idea was just garbage.

For novices and for people starting with chess programming can be frustrating trying to implement ideas considered "good" and don't get any result and this could make them leave early. So because what is written in chessprogramming wiki is considered "good" by a lot of people (me included) I think is a disservice to the commuity adding random stuff there. With "random stuff" I mean not properly tested (please let me be pedantic and indulge on "properly" word).

So I suggest to remove that part until not proven or at least add a notice in which is clearly written that is a "Not tested" idea.

CPW is about sharing ideas, and of course move ordering ideas may work for some and not for others, dependent what you do otherwise and how it interacts. Steven said sometimes it works for him and sometimes it doesn't and it appears that a lot is dependent on how much of a bonus is given to the matched generated move.

LBR is a generalization of the counter move heuristic (which might not work for engines as well) or a even more general killer heuristic, with many implementations nuances. Also the post here by computer chess pioneer Steven Edwards, similar to a publication in ICGAJ, qualifies the idea worth a CPW page.

Gerd

[sje]

I can't recall exactly when I came up with the idea of using the LBR heuristic. But it was at one point part of experiments with my old 1987 program Spector back in the pre-Web days. Concerning details, my memory fails me here as it often does.

In any case, I've brought back the technique for application in the new Chess In Lisp toolkit. At present, LBR is used only for the defensive side in the sample matefinder routine where a bonus of a half pawn is added for move ordering. Sometimes it works, and sometimes it doesn't. But in any case, it will be more specific (and so have a better chance at working) than the Countermove heuristic.

People are welcome to check it out for themselves. The constantly evolving CIL toolkit can be found at:

https://public.me.com/chessnotation -> ChessInLisp -> Source

The LBR data store for each ply is organized as an unbalanced binary tree keyed by the prior move's hash. For debugging purposes, the value part of each hash node includes both the last best reply and a clear copy of the prior move in a two element list.

One surprise for me was that the hash tree at a search node can wind up having hundreds of different prior moves, each with a corresponding LBR move (some duplicates here). This is a consequence of the extra specificity of LBR vs Countermove.

Anyone with a Lisp processor can run the code themselves and see what's happening. (The *acs* dbg0 option flag needs to be activated manually for LBR to kick-in.)

Note that any results may (will) be different as more move ordering techniques are added. Also, results will certainly be different for a general move selector vs the existing mate finder.