[Retros] A new program to solve fairy proof games

[François Labelle]

Marco Bonavoglia wrote:
> Great program, thanks! I checked it with different fairy SPGs with 
> excellent results, with one strange exception:
> PDB P1066705 (Initial position without BPh7 SPG4.0 Circe)
>
> Popeye solves it in abt 50 seconds, Jacobi takes a lot of time, after 
> ten minutes it's at about 11% and has analyzed only 1. Sc3 1. Sa3 and 
> was analyzing 1. Sh3 when I stopped it.
> I think it could take more than one hour. This on my laptop (with i7) 
> using Chrome or Firefox (I tried both). Is it the homebase position 
> that "confuses" Jacobi, or may be is a bug?

Hi Marco,

Thank you for this example. On my laptop Jacobi took 1339 s, and Popeye 
4.79 took 33 s. This is a huge difference!

Currently the PG solver is not very smart. In Circe it doesn't assign 
any cost to a rebirth, so if the final diagram is homebase it's playing 
pretty much any move during the game.

The good news is that Jacobi solves the "Tacu enigma" version of the 
same problem in 10 s:

stip dia 4.0 forsyth XXXXXXXX/XXXXXXX1/8/8/8/8/XXXXXXXX/XXXXXXXX 
ColorThePieces
cond circe

It finds 122 solutions, and the desired solution is among them.

The Tacu enigma solver is calculating costs differently, which explains 
why it can be faster. I'll see if I can incorporate some of its logic 
into the generic solver.

Actually it's already possible to run both solvers at the same time, and 
when I do that Jacobi solves the original problem in 49 s:

stip dia 4.0 forsyth rsbqkbsr/ppppppp1/8/8/8/8/PPPPPPPP/RSBQKBSR
test dia forsyth XXXXXXXX/XXXXXXX1/8/8/8/8/XXXXXXXX/XXXXXXXX ColorThePieces
cond circe

So this is a workaround that you can use while you're waiting for a 
version of Jacobi with this performance fix integrated.


CAILLAUD Michel wrote:
> I am not specialist but I wonder if the use of hash tables can help 
> (François mentioned hash keys, not the same thing??!). By experience I 
> know hash tables have spectacular influence on the solving time of 
> these kinds of position by Natch (orthodox). I don't know if Jacobi 
> uses them (?!). They are used in Euclide (fixed), Natch, Popeye and 
> Gustav (dimensionable by user).

Hi Michel,

You're right that hash tables give an enormous speed boost for some 
problems. Jacobi v0.1 uses a hash table with a fixed size of ~128 MB. I 
think I'll be able to make it configurable in v0.2. I wanted the default 
value to be on the small side to avoid causing problems on low end 
devices (Jacobi runs on smartphones!)

Solving Marco's problem with "py -maxmem 128M" took 38 s instead of 33 
s, so it appears that for this particular problem the smaller hash table 
size of Jacobi wasn't responsible for much difference.

     François