The Hoffman User's Guide

			   by Brent Baccala
			 cosine@freesoft.org


Hoffman is a program to solve chess endgames using retrograde
analysis.  For those not up on Americana, the program is named after
Trevor Hoffman, an All Star baseball pitcher who specializes in
"closing" games.  It was written specifically for The World vs. Arno
Nickel game.

A retrograde analysis program is much different from a conventional
computer chess programs.  Retrograde analysis is only useful in the
endgame, runs very slowly, and produces enormous amounts of data.  Its
great advantage lies in its ability to completely solve the endgame.
In a very real sense, a retrograde engine has no 'move horizon' like a
conventional chess engine.  It sees everything.

Hoffman (and this guide) is still very much a work in progress.

Let me illustrate how Hoffman works using some simple examples.

First, Hoffman operates using XML control files to govern its
operation.  You build a Hoffman tablebase (traditionally an '.htb'
file) by running Hoffman with the '-g' (generate) option, and passing
it an XML control file.

Here is about the simplest possible XML control file, for the king
vs. king endgame:


<?xml version="1.0"?>
<!DOCTYPE tablebase SYSTEM "tablebase.dtd">

<tablebase>
   <pieces>
      <mobile color="white" type="king"/>
      <mobile color="black" type="king"/>
   </pieces>
</tablebase>


You put this in a file called "kk.xml", and run Hoffman like this:


baccala@debian ~/src/endgame$ ./hoffman -g -o kk.htb kk.xml
Initializing tablebase
Checking futuremoves...
All futuremoves handled under move restrictions
Intra-table propagating
Pass 0 complete; 840 positions processed
Pass 1 complete; 0 positions processed
baccala@debian ~/src/endgame$


There isn't much to see, of course.  King vs king is nothing more than
figuring out the different between illegal positions and draws.  But
this information is important, because it's needed to back propagate
from the (slightly) more complex three piece endgames, like K+Q vs K:


<?xml version="1.0"?>
<!DOCTYPE tablebase SYSTEM "tablebase.dtd">

<tablebase>
   <pieces>
      <mobile color="white" type="king"/>
      <mobile color="black" type="king"/>
      <mobile color="white" type="queen"/>
   </pieces>
   <futurebase filename="kk.htb" type="capture"/>
</tablebase>


Notice the new "futurebase" line.  This tells Hoffman where to get the
information about what happens when the black king can capture the
white queen.  The current version of Hoffman actually needs this
information, since it doesn't distinguish between positions where the
white king is guarding the queen or not.

You put this is a file called "kqk.xml", make sure the "kk.htb" that
was generated from the first run is present, and run Hoffman again:


baccala@debian ~/src/endgame$ ./hoffman -g -o kqk.htb kqk.xml
Initializing tablebase
Back propagating from 'kk.htb'
Checking futuremoves...
All futuremoves handled under move restrictions
Intra-table propagating
Pass 0 complete; 131516 positions processed
Pass 1 complete; 364 positions processed
Pass 2 complete; 2448 positions processed
Pass 3 complete; 1352 positions processed
Pass 4 complete; 5012 positions processed
Pass 5 complete; 2956 positions processed
Pass 6 complete; 9064 positions processed
Pass 7 complete; 7480 positions processed
Pass 8 complete; 19964 positions processed
Pass 9 complete; 14144 positions processed
Pass 10 complete; 26164 positions processed
Pass 11 complete; 25484 positions processed
Pass 12 complete; 32064 positions processed
Pass 13 complete; 39908 positions processed
Pass 14 complete; 32104 positions processed
Pass 15 complete; 54052 positions processed
Pass 16 complete; 15000 positions processed
Pass 17 complete; 43800 positions processed
Pass 18 complete; 2680 positions processed
Pass 19 complete; 11300 positions processed
Pass 20 complete; 8 positions processed
Pass 21 complete; 56 positions processed
Pass 22 complete; 0 positions processed
baccala@debian ~/src/endgame$


See, it's a little more interesting this time, right?

All of these XML files are available on the freesoft.org web server.
After processing "kk.xml" and "kqk.xml", you'll want to compute
"krk.xml" and "knk.xml".  Now you're ready to build "kpk.xml":


<?xml version="1.0"?>
<!DOCTYPE tablebase SYSTEM "tablebase.dtd">

<tablebase>
   <pieces>
      <mobile color="white" type="king"/>
      <mobile color="black" type="king"/>
      <mobile color="white" type="pawn"/>
   </pieces>
   <futurebase filename="kqk.htb" type="promotion"/>
   <futurebase filename="krk.htb" type="promotion"/>
   <futurebase filename="knk.htb" type="promotion"/>
   <futurebase filename="kk.htb" type="capture"/>
</tablebase>


Notice we've added a new type of "futurebase" line - pawn promotion.
Right now, Hoffman handles queen, rook, and knight promotions.
Bishops would be easy to add, but I haven't done that yet.

After computing "kpk.htb", you've got all of the three piece
tablebases (except bishop).  Ready to try a four piece?  Here's
"kqkq.xml":


<?xml version="1.0"?>
<!DOCTYPE tablebase SYSTEM "tablebase.dtd">

<tablebase>
   <pieces>
      <mobile color="white" type="king"/>
      <mobile color="black" type="king"/>
      <mobile color="white" type="queen"/>
      <mobile color="black" type="queen"/>
   </pieces>
   <futurebase filename="kqk.htb" type="capture"/>
   <futurebase filename="kqk.htb" type="capture" colors="invert"/>
</tablebase>


Notice several things.  First, we no longer specify "kk.htb" as a
futurebase.  We're only interested in the single captures that lead
out of the tablebase we're building.  "kk.htb" has already been used
to build "kqk.htb", so its data is in there.  Two queens can't be
taken on a single move, so all we need to worry about is what happens
if one of them is captured.  That's why I use the "kqk.htb" tablebase.
Notice that I use it twice, depending on which queen is being
captured.  The "kqk.htb" tablebase has a white queen in it, and the
colors="invert" option handles the case where the white queen is
captured and we're left with a black queen on the board.

Notice also that a four piece tablebase takes a good bit longer to
compute than a three piece one.

By the way, if you have the appropriate Nalimov tablebases, you
can verify Hoffman tablebases using the "-v" option:


baccala@debian ~/src/endgame$ ./hoffman -v kqk.htb
4 piece Nalimov tablebases found
Loading 'kqk.htb'
Verifying tablebase against Nalimov
baccala@debian ~/src/endgame$


Tablebases take a lot longer to verify than to create.

Now you can process "kqkr.xml" and "kqkn.xml", which prepares you for
"kqkp.xml":


<?xml version="1.0"?>
<!DOCTYPE tablebase SYSTEM "tablebase.dtd">

<tablebase>
   <pieces>
      <mobile color="white" type="king"/>
      <mobile color="black" type="king"/>
      <mobile color="white" type="queen"/>
      <mobile color="black" type="pawn"/>
   </pieces>
   <futurebase filename="kqk.htb" type="capture"/>
   <futurebase filename="kpk.htb" type="capture" colors="invert"/>
   <futurebase filename="kqkq.htb" type="promotion"/>
   <futurebase filename="kqkr.htb" type="promotion"/>
   <futurebase filename="kqkn.htb" type="promotion"/>
   <futurebase filename="kqk.htb" type="promotion-capture" colors="invert"/>
   <futurebase filename="krk.htb" type="promotion-capture" colors="invert"/>
   <futurebase filename="knk.htb" type="promotion-capture" colors="invert"/>
</tablebase>


Notice the new type of futurebase, "promotion-capture", that is pretty
much what its name implies.  It handles the case where the pawn boths
captures something (the enemy queen, in this case) and promotes on the
same move.

You will notice that the number of "futurebase" statements is starting
to pile up.  That's one of the big reasons I used XML for a control
file.  I fully expect to have another "meta-program" to generate
XML files to govern a whole series of Hoffman runs.

Oh, and I suppose having generating all of these tablebases, you now
want to query them, huh?

You do that using the probe (-p) option, followed by a list of
tablebases.  Since we've got a small collection of simple tablebases,
it's easiest to just load them all, like this:


baccala@debian ~/src/endgame$ ./hoffman -p *.htb
4 piece Nalimov tablebases found
Loading 'kk.htb'
Loading 'knk.htb'
Loading 'knkn.htb'
Loading 'knkp.htb'
Loading 'kpk.htb'
Loading 'kpkp.htb'
Loading 'kpkq.htb'
Loading 'kqk.htb'
Loading 'kqkn.htb'
Loading 'kqkp.htb'
Loading 'kqkq.htb'
Loading 'kqkr.htb'
Loading 'krk.htb'
Loading 'krkn.htb'
Loading 'krkp.htb'
Loading 'krkr.htb'
FEN? 8/8/8/8/p7/8/1P4k1/2K5 b
FEN 8/8/8/8/p7/8/1P4k1/2K5 b - -
Index 12658437
Draw

Nalimov score: DRAW
   g2h2    White moves and wins in 22
   g2f2    White moves and wins in 25
   g2g3    White moves and wins in 25
   g2g1    White moves and wins in 25
   g2f3    Draw
   g2h3    White moves and wins in 22
   g2f1    White moves and wins in 25
   g2h1    White moves and wins in 21
   a4a3    White moves and wins in 16
FEN or move? g2f3
FEN 8/8/8/8/p7/5k2/1P6/2K5 w - -
Index 12659332
Draw

Nalimov score: DRAW
   c1d1    Draw
   c1b1    Draw
   c1c2    Draw
   c1d2    Draw
   b2b3    Draw
   b2b4    Draw
FEN or move? b2b4
FEN 8/8/8/8/pP6/5k2/8/2K5 b - b3
Index 12593797
Draw

Nalimov score: DRAW
   f3g3    White moves and wins in 15
   f3e3    White moves and wins in 15
   f3f4    White moves and wins in 23
   f3f2    White moves and wins in 15
   f3e4    Draw
   f3g4    White moves and wins in 15
   f3e2    White moves and wins in 15
   f3g2    White moves and wins in 15
   a4xb3   Draw
FEN or move?
baccala@debian ~/src/endgame$


At the "FEN?" prompt you want to enter a chess position in FEN
notation (you can leave off the castling rights and en passant square
if you want).  The program spits back its evaluation of the position
(if it has one), along with a list of moves and how they evaluate.  It
has a history and readline function, so once you've typed a FEN
position in once, if you end the program with a CNTL-D and not a
CNTL-C, it will save everything to a history file, and you can
retrieve it again on a later run using the up arrow key.

After you've put a FEN position in, you get a "FEN or move?" prompt,
which allows you to enter moves and thus step forward in the game.
The move parser isn't very smart right now; you can make illegal moves
pretty easily and there's no way to back up.  The quirkiest thing at
the moment is that if you want to promote, you need to specify EXACTLY
the piece you're promoting into; "b7b8=Q" is radically different from
"b7b8=q"!!

That's all for now.