OpenChess

Here are some papers of Jonathan Schaeffer that touch on chess programming.

Pre-searching: http://webdocs.cs.ualberta.ca/~jonathan ... Search.pdf
The idea is: at ply D, you run across position X at depth Y, but you "expect" to run across it again (at the same ply) at depth Z, where Z is bigger than Y. So you search to depth Z in the first place.

Imperfect Information Endgame Databases: http://webdocs.cs.ualberta.ca/~jonathan ... tialDB.pdf
Building checkers databases w/o having to have the recursive promotion DBs built, relying instead on partial information. So they could work with 6c vs 5c w/o having the 6 king versus 5 king built.

Automatic Generation of Search Engines: http://webdocs.cs.ualberta.ca/~jonathan ... GPilot.pdf
Some ideas toward automated advances to surpass alpha-beta.

Rediscovering *-Minimax Search: http://webdocs.cs.ualberta.ca/~jonathan ... 04smm1.pdf

Building the Checkers 10-piece Endgame Databases: http://webdocs.cs.ualberta.ca/~jonathan ... ases10.pdf
The paper that describes various techniques with bitbases.

Search Ideas in Chinook: http://webdocs.cs.ualberta.ca/~jonathan ... chideas.ps
One idea that appears here: in aspiration search, on fail-low at root, use a sort of IID (reduce ply back to 1). Then again, Chinook rarely fails low.

Some of these later ones have problems with the Figures in the Postscript files.

Diminishing Returns for Additional Search in Chess: http://webdocs.cs.ualberta.ca/~jonathan ... ers/dim.ps
Somewhat of a precursor to "Crafty goes deep" I guess.

New Advances in Alpha-Beta Searching: http://webdocs.cs.ualberta.ca/~jonathan ... m-final.ps
New as in 1996. He has many papers from the mid-90s about alternatives for minimax trees. See for instance: http://webdocs.cs.ualberta.ca/~jonathan ... .1994.html

Solving Large Retrograde Analysis Problems Using a Network of Workstations: http://webdocs.cs.ualberta.ca/~jonathan ... tabases.ps

The Game of Chess: http://webdocs.cs.ualberta.ca/~jonathan ... s/simon.ps
A brief overview written with Simon in 1989.

Checkers: A Preview of What Will Happen in Chess? http://webdocs.cs.ualberta.ca/~jonathan ... preview.ps

Empirical Results with Conspiracy Numbers: http://webdocs.cs.ualberta.ca/~jonathan ... s/compi.ps
See section 6 for the experimental results with Phoenix.

Chunking for Experience: http://webdocs.cs.ualberta.ca/~jonathan ... rs/mach.ps
Trying to do something with pattern recognition in Phoenix.

The History Heuristic and the Performance of Alpha-Beta Enhancements: http://webdocs.cs.ualberta.ca/~jonathan ... rs/pami.ps

BB+ wrote:Here are some papers of Jonathan Schaeffer that touch on chess programming.

Pre-searching: http://webdocs.cs.ualberta.ca/~jonathan ... Search.pdf
The idea is: at ply D, you run across position X at depth Y, but you "expect" to run across it again (at the same ply) at depth Z, where Z is bigger than Y. So you search to depth Z in the first place.

Imperfect Information Endgame Databases: http://webdocs.cs.ualberta.ca/~jonathan ... tialDB.pdf
Building checkers databases w/o having to have the recursive promotion DBs built, relying instead on partial information. So they could work with 6c vs 5c w/o having the 6 king versus 5 king built.

Automatic Generation of Search Engines: http://webdocs.cs.ualberta.ca/~jonathan ... GPilot.pdf
Some ideas toward automated advances to surpass alpha-beta.

Rediscovering *-Minimax Search: http://webdocs.cs.ualberta.ca/~jonathan ... 04smm1.pdf

Building the Checkers 10-piece Endgame Databases: http://webdocs.cs.ualberta.ca/~jonathan ... ases10.pdf
The paper that describes various techniques with bitbases.

Search Ideas in Chinook: http://webdocs.cs.ualberta.ca/~jonathan ... chideas.ps
One idea that appears here: in aspiration search, on fail-low at root, use a sort of IID (reduce ply back to 1). Then again, Chinook rarely fails low.

This is not new. We had lotws of discussions about the idea. I think John Stanback might have been the first to try this. It all dates back to the old days where most programs did use aspiration search at all. Once most started to use it, the question to answer is "if you fail low on the aspiration window on the first move, do you continue looking thru the rest of the moves, do you re-set alpha to a lower value and try the first move again, or what?"

John had played with the idea that if you fail low at depth D, just re-start the search at ply 1. The move that failed low should not be chosen by early iterations because of that deep-draft fail-low TT entry. In theory. In reality, it wasn't so simple. Occasionally the TT entry would get overwritten and not be there when you need it. Or the score, iteration by iteration can oscillate significantly occasionally letting that TT entry fail to cause a cutoff for that move. And you know what happens on an open-window research. It becomes best until you reach the same depth, and start the cycle again...

Some of these later ones have problems with the Figures in the Postscript files.

Diminishing Returns for Additional Search in Chess: http://webdocs.cs.ualberta.ca/~jonathan ... ers/dim.ps
Somewhat of a precursor to "Crafty goes deep" I guess.

New Advances in Alpha-Beta Searching: http://webdocs.cs.ualberta.ca/~jonathan ... m-final.ps
New as in 1996. He has many papers from the mid-90s about alternatives for minimax trees. See for instance: http://webdocs.cs.ualberta.ca/~jonathan ... .1994.html

Solving Large Retrograde Analysis Problems Using a Network of Workstations: http://webdocs.cs.ualberta.ca/~jonathan ... tabases.ps

The Game of Chess: http://webdocs.cs.ualberta.ca/~jonathan ... s/simon.ps
A brief overview written with Simon in 1989.

Checkers: A Preview of What Will Happen in Chess? http://webdocs.cs.ualberta.ca/~jonathan ... preview.ps

Empirical Results with Conspiracy Numbers: http://webdocs.cs.ualberta.ca/~jonathan ... s/compi.ps
See section 6 for the experimental results with Phoenix.

Chunking for Experience: http://webdocs.cs.ualberta.ca/~jonathan ... rs/mach.ps
Trying to do something with pattern recognition in Phoenix.

The History Heuristic and the Performance of Alpha-Beta Enhancements: http://webdocs.cs.ualberta.ca/~jonathan ... rs/pami.ps

BB+ wrote:Here are some papers of Jonathan Schaeffer that touch on chess programming.

Thank you! I'll incorporate the papers in cpw, if you don't mind.

BB+ wrote:Here are some papers of Jonathan Schaeffer that touch on chess programming.

How about this one?

http://www.GothicChess.com/7_piece.pdf



Funny you mention that, I am building more checkers endgames right now, using a 64-bit checkers engine. It might seem odd to use 64-bits for a game with 32 squares, but I found a cool trick to reduce my move generator down to about 19 lines of code due to some interesting properties of larger aperture bit words.

Like, I never have to see if I generate a checker move "off the board", which plagues all 32-bit move generators.