How do you generate tablebases?

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

How do you generate tablebases?

Postby byakuugan » Thu Aug 18, 2011 7:07 am

I want to be able to see the evaluations of endings on other boards and possibly with fairy pieces. In one of my youtube videos, I explained a concept in a winning Rook vs. Bishop endgame by comparing it to a drawn identical position in Gothic Chess, but I didn't have any tablebase data to confirm my claims. Another project I was working on was studying how to win 2 bishops vs. knight on 8x8, and would be interested to generate 2 bishops vs. knight on a gothic 10x8 board.
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby Kirill Kryukov » Sat Aug 20, 2011 4:11 pm

Making your own tablebase generator takes some time and efforts, but it's doable if you set out to do it. Even if you don't end up with something terribly efficient, you should be able to solve some simple endgames, like 3 or 4 pieces on any reasonable board size. Alternatively you may try to adopt some existing generator to your needs, but I guess it won't make it eaiser.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7338
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: How do you generate tablebases?

Postby h.g.muller » Sun Oct 23, 2011 5:46 pm

The generator posted on my website (as C code) is reasonably 'fairy friendly', as in fact my main reason for building it was to study end-games with unorthodox pieces. E.g. it takes the way the pieces move from tables, and any piece can be royal. A limitation is that it cannot do Pawns. Another limitation is that it is very much based on the edge of the board being a power of 2. For 8x8 doing a 5-men takes about 160MB. (It uses 1 byte per position.) I one made a version that could do 16x16, or part thereof, (by plastering a zone next to the board edges with obstacles to make them inaccessible), to study how mating potential of leapers erodes away on larger boards. But that requires a factor 4 extra space per man, so already 64 for a 3-men, making a 3-men equally space-demanding as a 4-men on 8x8, and a 4-men 4 times as expensive (640MB) as a 5-men on 8x8. And when I do a non-square part of the board, I have to drop the diagonal symmetry, which again 'doubles' the required space to 1GB. (And even my 'big' PC has only 1GB, so it wouldnot leave anything for the program and OS.) So it was an outrageously expensive method for doing 10x8 (But it served the purpose for which it was designed well.)

For 10x8 one could of course do better, because only one of the board dimensions has to be doubled, but even that would be quite wasteful, and put 5-men out of my reach.

So the best solution would be to completely redesign the generator, to be able to work with arbitrary board size. Something that is on my wish list anyway, since I also want to do Xiangqi end-games (9x10, but some pieces only on 3x3). The fact that in themean time I have invented methods that should be 10 times faster than my old generator is also an incentive to not spend too much time on the old one anymore, and start building a new one from scratch. But my to-do list is always soooooh long.... :(
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby byakuugan » Mon Oct 24, 2011 8:10 pm

Thank you, I've been learning C# for over a week now, and I've created my first simple command prompt. It is like a calculator for King vs. King concepts on large chessboards, but it always assumes that the board ends somewhere.

Code: Select all
// Namespace Declaration
using System;

// Program start class
class InteractiveWelcome
{
    // Main begins program execution.
    public static void Main()
    {
        int YKRANK, YKFILE, TKRANK, TKFILE, MOVER;

        Console.WriteLine("What rank is your king on?:");
        YKRANK = int.Parse(Console.ReadLine());

        Console.WriteLine("What file is your king on? (a=1, b=2, c=3, d=4, etc.):");
        YKFILE = int.Parse(Console.ReadLine());

        Console.WriteLine("What rank is their king on?:");
        TKRANK = int.Parse(Console.ReadLine());

        Console.WriteLine("What file is their king on? (a=1, b=2, c=3, d=4, etc.):");
        TKFILE = int.Parse(Console.ReadLine());

        Console.WriteLine("Is it your turn to move? Type 1 for yes, or 0 for no.");
        MOVER = int.Parse(Console.ReadLine());


        if ((Math.Abs(YKRANK - TKRANK)) < 2 && (Math.Abs(YKFILE - TKFILE)) < 2)
            Console.WriteLine("That is an illegal position!");
        else
        {
           

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE - TKFILE) % 2 == 0 && MOVER == 0)
                Console.WriteLine("You have opposition!");

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE - TKFILE) % 2 == 0 && MOVER == 0 && YKRANK != TKRANK && YKFILE != TKFILE)
                Console.WriteLine("You can achieve a more linear form of opposition after at least " + ((Math.Abs(YKRANK - TKRANK) - 1) + (Math.Abs(YKFILE - TKFILE) - 1)) + " half-moves!");


            if ((YKRANK - TKRANK) % 2 == 0 && YKFILE == TKFILE && MOVER == 0)
                Console.WriteLine("You have vertical opposition!");


            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE == TKFILE) && MOVER == 0)
                Console.WriteLine("Use it for defense to stop enemy from reaching/passing the " + ((YKRANK + TKRANK) / 2) + "th rank!");

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE == TKFILE) && MOVER == 0)
                Console.WriteLine("Or use it for offense to forcibly reach/pass the " + ((YKRANK + TKRANK) / 2) + "th rank!");

            if (YKRANK == TKRANK && (YKFILE - TKFILE) % 2 == 0 && MOVER == 0)
                Console.WriteLine("You have horizontal opposition!");

            if (YKRANK == TKRANK && (YKFILE - TKFILE) % 2 == 0 && MOVER == 0)
                Console.WriteLine("Use it for defense to stop enemy from reaching/passing the " + ((YKFILE + TKFILE) / 2) + "th file...");

            if (YKRANK == TKRANK && (YKFILE - TKFILE) % 2 == 0 && MOVER == 0)
                Console.WriteLine("Or use it for offense to forcibly reach/pass the " + ((YKFILE + TKFILE) / 2) + "th file...");

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE - TKFILE) % 2 == 0 && MOVER == 1)
                Console.WriteLine("Your opponent has opposition!");

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE - TKFILE) % 2 == 0 && MOVER == 1 && YKRANK != TKRANK && YKFILE != TKFILE)
                Console.WriteLine("They can achieve a more linear form of opposition after at least " + ((Math.Abs(YKRANK - TKRANK) - 1) + (Math.Abs(YKFILE - TKFILE) - 1)) + " half-moves!");


            if ((YKRANK - TKRANK) % 2 == 0 && YKFILE == TKFILE && MOVER == 1)
                Console.WriteLine("Your opponent has vertical opposition!");

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE == TKFILE) && MOVER == 1)
                Console.WriteLine("They can use it for defense to stop you from reaching/passing the " + ((YKRANK + TKRANK) / 2) + "th rank!");

            if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE == TKFILE) && MOVER == 1)
                Console.WriteLine("Or use it for offense to forcibly reach/pass the " + ((YKRANK + TKRANK) / 2) + "th rank!");


            if (YKRANK == TKRANK && (YKFILE - TKFILE) % 2 == 0 && MOVER == 1)
                Console.WriteLine("Your opponent has horizontal opposition!");

            if (YKRANK == TKRANK && (YKFILE - TKFILE) % 2 == 0 && MOVER == 1)
                Console.WriteLine("They can use it for defense to stop you from reaching/passing the " + ((YKFILE + TKFILE) / 2) + "th file...");

            if (YKRANK == TKRANK && (YKFILE - TKFILE) % 2 == 0 && MOVER == 1)
                Console.WriteLine("Or use it for offense to forcibly reach/pass the " + ((YKFILE + TKFILE) / 2) + "th file...");

            else if ((YKRANK - TKRANK) % 2 != 0 && (YKFILE - TKFILE) % 2 != 0 && MOVER == 0)
                Console.WriteLine("Your opponent can maintain opposition by moving to one of these four places:    (" + ((TKFILE + 1)) + "th file),(" + ((TKRANK + 1)) + "th rank),  or  (" + ((TKFILE + 1)) + "th file),(" + ((TKRANK - 1)) + "th rank),  or  (" + ((TKFILE - 1)) + "th file),(" + ((TKRANK + 1)) + "th rank),  or  (" + ((TKFILE - 1)) + "th file),(" + ((TKRANK - 1)) + "th rank)   ");


            else if ((YKRANK - TKRANK) % 2 != 0 && (YKFILE - TKFILE) % 2 != 0 && MOVER == 1)
                Console.WriteLine("You can maintain opposition by moving to one of these four places:    (" + ((YKFILE + 1)) + "th file),(" + ((YKRANK + 1)) + "th rank),  or  (" + ((YKFILE + 1)) + "th file),(" + ((YKRANK - 1)) + "th rank),  or  (" + ((YKFILE - 1)) + "th file),(" + ((YKRANK + 1)) + "th rank), or  (" + ((YKFILE - 1)) + "th file),(" + ((YKRANK - 1)) + "th rank)   ");


            else if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE - TKFILE) % 2 != 0 && MOVER == 1)
                Console.WriteLine("You can maintain opposition by moving to either of these two places:   (" + ((YKFILE + 1)) + "th file),(" + ((YKRANK + 0)) + "th rank),  or  (" + ((YKFILE - 1)) + "th file),(" + ((YKRANK + 0)) + "th rank)   ");

            else if ((YKRANK - TKRANK) % 2 == 0 && (YKFILE - TKFILE) % 2 != 0 && MOVER == 0)
                Console.WriteLine("Your opponent can maintain opposition by moving to either of these two places:   (" + ((TKFILE + 1)) + "th file),(" + ((TKRANK + 0)) + "th rank),  or  (" + ((TKFILE - 1)) + "th file),(" + ((TKRANK + 0)) + "th rank)   ");

            else if ((YKRANK - TKRANK) % 2 != 0 && (YKFILE - TKFILE) % 2 == 0 && MOVER == 1)
                Console.WriteLine("You can maintain opposition by moving to either of these two places:   (" + ((YKFILE + 0)) + "th file),(" + ((YKRANK + 1)) + "th rank),  or  (" + ((YKFILE + 0)) + "th file),(" + ((YKRANK - 1)) + "th rank)   ");

            else if ((YKRANK - TKRANK) % 2 != 0 && (YKFILE - TKFILE) % 2 == 0 && MOVER == 0)
                Console.WriteLine("Your opponent can maintain opposition by moving to either of these two places:   (" + ((TKFILE + 0)) + "th file),(" + ((TKRANK + 1)) + "th rank),  or  (" + ((TKFILE + 0)) + "th file),(" + ((TKRANK - 1)) + "th rank)   ");

        }

       
        // prevent screen from vanishing
        // when run from VS.NET
        Console.ReadLine();
    }
}


I hope the code copies okay. Before I get started on actual endgames, I am trying to learn if there is a way to create a chessboard interface, where placing a piece on the board is the equivalent to typing integers into a command prompt.
BTW, my laptop always has 400 GB to 500 GB of free space that is never being used, so I would gladly store tablebases for anyone, and possibly explain some of the endgame concepts on my youtube channel.
Last edited by byakuugan on Tue Oct 25, 2011 4:56 pm, edited 1 time in total.
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby h.g.muller » Mon Oct 24, 2011 8:27 pm

You would make life enormously more easy for yourself if you used an existing graphical chess interface like WinBoard. Then you would not have to bother with any graphics at all, but can limit yourself to writing engines that communicate just through reading text from the standard input (normally keyboard) and writing it to the standard output (normally a text window). WinBoard can connect to such an engine, so that in fact it 'types' to it, and catches the output instead of letting it appear on the screen.

All the functionality you are seeking is already in WinBoard; you can enter moves by dragging pieces over the board with the mouse, and WinBoard will translate them to coordinate notation, and send them to the engine like they were typed. The engine can send a move back, in coordinate notation or SAN, and WinBoard will perform the move on its graphical display. There are some other commands, beside moves, which your engine will get, like 'new' when the user resets the board for a new game, or 'setboard FEN' with the board position in FEN notation, when the user set up a non-standard position.

WinBoard supports graphics for 22 different piece types per side, and boards upto 16x16 (although this could be trivially enlarged by recompiling it).

WinBoard can be downloaded from http://hgm.nubati.net/WinBoard-4.5TM.exe as an installer packege including a few engines.

Image

Image

Image
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby Kirill Kryukov » Tue Oct 25, 2011 1:29 am

byakuugan, please use the "code" tag to enclose your code, otherwise it loses indentation and becomes unreadable.

You don't need any graphical interface at this stage. You can think about interface after you have a working generator. For the interface part, instead of asking questions on console, you can read the FEN from it.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7338
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: How do you generate tablebases?

Postby byakuugan » Wed Oct 26, 2011 8:21 pm

h.g.muller wrote:The generator posted on my website (as C code)


I downloaded the only C I found that did not say C++ or C#, but when I paste the code into it, it reads 5 errors, and always goes to Line 54, which is empty except for a {

Either I downloaded the wrong version of C, or I am supposed to type something in Line 54.

It says ISO C++ forbids declaration of 'zgen' with no type
return-statement with no value, in function returning 'int'
'malloc' was not declared in this scope
'exit' was not declared in this scope
invalid conversion from 'char*' to 'unsigned char*'


Also, I put the code tag on my previous post.
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby h.g.muller » Fri Oct 28, 2011 10:19 pm

Oh, you are right! This is not strictly as it should be (the word 'void' is required before 'zgen'). Your compiler seems to be a whole lot more critical than mine; even my most recent version that I was using last week still has this, and I never get an error message for it. (I am using gcc under Cygwin.)

I attached my latest version to this post, after compiling with -Wall, and fixing those warnings that a more critical compiler could perceive as errors. Perhaps you can try that.
Attachments
conv4x.c
EGT generator source
(32.64 KiB) Downloaded 133 times
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby byakuugan » Mon Oct 31, 2011 11:07 am

Yes! Thank You!
I'll probably get used to the glitches, where the winning side will try to give up material.
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby h.g.muller » Mon Oct 31, 2011 2:55 pm

Well, since you seem to have a serious interest in this, I decided to do something that had been on my to-do list, namely upgrade the user-friendliness of that EGT generator a little. I uploaded the source code of the improved version to http://hgm.nubati.net/conv4x.c .

Compared to the previous version the improveents are:
*) It is no longer needed to recompile if you want to build an EGT with other pieces. In stead you can specify the EGT you want to build through a command-line argument. E.g.

conv4x KQ.KR

would build (well, guess what!). The end-game is solved for white wins only (as has always been characteristicof this generator); to get the black wins you have to re-run it with reversed colors. You can use all built-in pieces this way, through letters

KQRBN: orthodox Chess pieces
e: Alfil = A (in Betza notation)
d: Dababba = D
x: Ferz= F
w: Wazir = W
c: Camel = I
f: Flamingo
g: Giraffe
z: Zebra = J
Y: = NJ
G: Gnu = NI
Z: Bison = IJ
U: Buffalo = NIJ
C: Cetaur = KN
S: Squirrel = EDN
H: Nightrider = NN
A: Archbishop = BN
D: Captain = WD
E: Modern Elephant = FA
G: Dragon = FR
L: Lieutenant = FAsmW
X: = BD
F: = FAD
W: = WA

It is also possible to define your own pieces (note this feature is totally untested): if there is a file called piecedef.ini in the same folder, it reads the piece definitions from there before starting (and interpreting the command line). The sytax of this file is per line a piece ID letter, colon, space, and then a list of space-separated move descriptors. A move descripor is two numbers separated by a comma, optionally followed by a comma ad some move-right specifiers. The latter can be the letters c (for capture only), n (non-capture only), s (slider moves). Default would be leaper and both capture and non-capture. A * or + amongst the move rights generalize the move to all symmetry-equivalent moves. For example:

R: 1,0,s*
A: 1,1,s* 1,2,*
L: 1,1,* 2,2,* 0,1,n+

The latter is the Lieutenant from Spartan Chess, which is only quadrisymmetric because of the side-way non-capture moves. (So the first number is the forward step, the second number the lateral step.) The + only works, however, if you make a special compile first with the compiler switch DIAGSYM off (in which case the generator uses twice as much memory).

Alas, recompiling is also still necessary for a different number of men. A Windows binary for a 4-men generator can be downloaded at http://hgm.nubati.net/conv4x.exe .

The generator can now also be queried under WinBoard, in stead of having to type the cumbersome octal representation of the position. To make it work as a WinBoard engine (sort of), you need to put -xboard as first argument on the commad line. So to run under WinBoard you need to type in the egine combobox of the WinBoard startup dialog:

"conv4x -xboard KQ.KR" -fd THEFOLDERWHEREYOUHAVEIT

Installing through the Load Engine dialog would need 'Parameters' -xboard KQ.KR . Running it this way requires you to wait until it is finished building the EGT. (E.g. using the task manager to see when its CPU usage drops to zero, which for a 4-men shouldonly take half a minute or so.) You can the set up a position from KQKR in WinBoard (paste a FEN, or use the Edit Position menu), and click Machine White. (The EGT engine will always move for white, it currently cannot play black.) It should then play until mate or conversion. (Playing in sub-tables also does not work yet; in DTC building mode the sub-tables are destroyed.) All this is experimental and very flakey, but at least for KQKR it seemed to work.

Have fun!

[edit] I now prepaired a package that, apart from the source code also contains Windows binaries for a 3, 4 and 5-men version. Download at http://hgm.nubati.net/fairygen.zip .
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby byakuugan » Tue Nov 08, 2011 10:39 pm

I couldn't get any of the other programs to function properly after downloading, so I've just been entering octal and drawing my own pieces for the videos.

In my most recent I discussed the different combinations for mating with Bishop Alfil Alfil
http://www.youtube.com/watch?v=Xfl2Fs3ASa8
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby h.g.muller » Wed Nov 09, 2011 11:43 am

I see you have been busy! You might have noticed that after generating the tablebase, the last thing the program prints before asking you to enter a position is two octal numbers. These are codes for 'maximin' positions, the longest forcible mate. For instance with N+F this is 36 moves. (For these elementary end-games DTC is the same as DTM, of course). Actually the mating sequence from this position is a pretty interesting one:

The black king can just be trapped in the deadly corner by the dynamic enclosure

5B2/8/8/8/8/3K1N2/8/2k5 b - - 3 2
5B2/8/8/8/8/3K1N2/8/2k5 b - - 3 2

1... Kb2 {make a run for the open} 2. Nd4 Ka3 3. Nc6 Ka4 4. Kc4 Ka3
{the knight and king are just able to close the trap again, and cut off black's escape to the safe corner, by mirroring their original position in the diagonal}
5. Fe7 {white has one free move now, which he uses to approach the Ferz}
5... Kb2 {next futile try for the open} 6. Nd4 Kc1 7. Nf3 Kd1 8. Kd3 Kc1 {and history repeats...}
9. Fd6 {next free white move}.

Apparently N+F are to weak to drive the bare King from the safe corner to the deadly one, which precludes this from being a general win. With K+W there is no safe corner, so I guess forcing your own K+N to the center by definition traps the opponent King in some corner on 8x8, and you can use this dynamic enclosure to approch the Wazir, making it generally won.

Note that when playing by octal numbers, it is possible to just enter a two-digit number in which case it moves the black King there, and leaves the other pieces where they are.


I could not find your video on general mating principles with two fairy pieces anymore! Did you remove it? I thought it was quite useful (although perhaps not complete). I am searching for a simple algorithm to decide if pairs of fairy pieces have mating potential (and if so, in which corner), for use in a general (configurable) variant-playing engine, other than building the entire tablebases. Based on your video I had formulated the following heuristics:

*) to be able to give a corner mate, you must have a piece that can move from c1 to a1 (or symmetry-equivalents) in 3 moves. To account for divergent or asymmetric pieces this would have to be made more specific in one uncapture, one non-capture and one capture.
*) In doing so it must not go over b3 (where the attacking King is supposed to be). If it must go over b3, but not a3, the other piece must be able to attack b1 (for checking) and c2 at the same time. (Or the first piece should cover c1 and c2 at the same time, but this presumably would equip it with mating potential by itself.)
*) The other piece mustbe able to attack b2, from a point that wouldnot interfere with the 3-move tour.
*) If both pieces cannot do both, and one of them is color bound, that determines the color of the corner where a corner mate is possible.

Note that in general simple leapers cannot make the 3-move tour, because they are color or meta-color alterators, and a1 and c1 have the same meta-color. Except for pieces that are both color-bound and meta-color bound, like Dababba, but then their high-order of color-binding makes them useless in the driving process. So the prospect for corner mates is in general a bit bleak. Some compound leapers are of the same general strength as simple leapers, however, because both steps they can make fall on symmetry axes, and result in only 4 moves in stead of the usual 8. Of these the King and Woody Rook have mating potential by themselves, which leaves WA, FA and FD as the interesting ones. All of these can make the 3-move tour needed to force a corner mate (and the latter two are color-bound).

Then we have the edge mates, subject to the following conditions:
*) One piece must be able to attack ('fork') a1 and c1 at the same time.
*) The other piece would have to be able to go from c1 to b1 with in 3-moves (again uncapture + non-capture + capture)
*) Neither piece must need to be on b3 for this. (This is where a pair of Knights fails.)
*) If the forking piece eeds to be on b3, it would still be possible if it could attack c2 on the move before, (or, unlikely, the piece coveri.g c1 woud do that), and it would also attack c2 from b3, (unlikely), or the piece checking b1 should do that. And either should have to be on a3 for that. (This is what makes it possible for N+W.)

Now the mate of Zebra+Ferz falls in neither category, but is a kind of 'double-edge' mate peculiar to Ferz, where you put the King on c3 and the Ferz on b2, because a Ferz can fork a1+c1 and a1+a3 at the same time. This prevents stalemate by trapping the bare King on a2-b1, and thus voids the assumption you now need to be able to mate in a single move. In stead you have all the time in the world to position your second piece, but the condition is that it should be able to attack both a2 and b1 at the same time, (and not do it from c3). But the Zebra can do this.

An interesting corollary is that in the endgame of WA and AJ (=(2,2)+(3,3) compound leaper) the mate can only be performed in the corner of opposite color as the color-bound AJ: none of the pieces can fork a1-c1, so the only hope is a corner mate, but the AJ cannot go from c1 to a1 in 3 moves. So you are dependent on the WA, which indeed can do this. So the AJ must perform the mate on b1. This shows that the fact that you have to be on Bishop color is not so much due to the Bishop being color bound, but more to the Knight not being able to do the 3-move tour.

Of course whether the ability to perform the actual mate on a properly trapped King is a necessary condition, but not a sufficient one for the end-game to be generally won. So the bove heuristics can rule out mating potential (and then by giving the opponent a Pawn to break stalemate it might becomepossible again, as in KNNKP), but to determine general drawishness additional heuristics are needed. I get the impression that the following holds:

Two pieces with 8 move targets have no problem driving a bare King anywhere. When pieces with 4 move targets, like Ferz and Wazir are involved it, is more tricky. A Wazir is in general quite adept in driving the bare King along an edge to a corner, but a Ferz is too clumsy to do it. So if mate is not possible in all corners and you have Ferz, the end-game is not generally won. When oneof your pieces has higher-order color binding, it is hopeless.

With two 4-movers it is not always hopeless, although Ferz+Wazir only has a small number of forced mates: apair 'omni-directional paws' (cFmW) or their Berolina counterparts (cWmF) domake a generally won end-game! Could divergence be an asset in this respect?
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby h.g.muller » Wed Nov 09, 2011 3:57 pm

A pair of mFcW (here indicated by W), despite them having only 4 non-capture and 4 capture targets is actually a very strong force. It is a bit like a self-protecting Commoner. Look at the following mating sequence. (My counter-play by hand was not completely optimal, but close.)

Code: Select all
[Event "Computer Chess Game"]
[Site "CHESS_LAPTOP"]
[Date "2011.11.09"]
[Round "-"]
[White "EGTgen 1.0.4"]
[Black "hgm"]
[Result "1-0"]
[TimeControl "40/60"]
[Variant "fairy"]
[FEN "8/8/8/8/4k3/8/4K3/3WW3 w - - 0 1"]
[SetUp "1"]

{--------------
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . k . . .
. . . . . . . .
. . . . K . . .
. . . W W . . .
white to play
--------------}
1. Wd1c2 Kd4 2. Wc2d3+ Kc4 3. Wd3e4 Kd5 4. Ke3 Kc4 5. We1f2 Kc3 6. Wf2g3
Kc4 7. Wg3f4 Kd5 8. Wf4e5+ Kd6 9. We4d5+ Ke7 10. Wd5e6+ Kf7 11. We5d6 Ke8
12. We6d7 Kf7 13. Kf4 Kf6 14. Wd7e6+ Kg6 15. Kg4 Kf7 16. Wd6e7+ Kg7 17.
We6f7+ Kg6 18. We7f6+ Kh6 19. Wf7g8 Kh7 20. Wf6g7+ Kh6 21. Wg8h7# {checkmate} 1-0


Truly amazing! Of course being quasi-colorbound this only works when they are on unlike color.
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby byakuugan » Wed Nov 09, 2011 9:33 pm

In regards to mating a pair of with omni-directional pawns, it seems like the concept can be understood similarly to how 2 opposite-colored bishops are better than 2 same-colored bishops (like abilities become redundant when combined)
A Ferz is a colorbound piece, so moving as an alternating piece should make it stronger.
A Wazir is slow (only 1,0), so moving a little further (as 1,1) should make it stronger.
Eventually I want to get around to studying these concepts for every piece type, like if Knights moved as Camels when not capturing, they would lose a lot of their straightforward cornering abilities, but would be able to maintain control of the same square when moving.

Right now I was working on comparing the strengths of normal leapers, when stalemate is not an issue.
It seems that Knight+Knight, Knight+Zebra, Camel+Camel, Camel+Zebra, and Zebra+Zebra (all have 8 move targets and none are mating material against a lone king) generally win against a Flamingo, but not if a piece is only a 4-mover (like Knight+Ferz or Zebra+Wazir won't win). But if instead of a Flamingo, if the defender has an Alfil, then Knight+Knight are the only non-matingmaterial leapers that can win.

I am going to do a remake of the video involving mates with 2 leapers, when I formulate a simpler rule involving the mating potential of all leapers. I was thinking of something like a variable scenario, where you have to decide what the two pieces must be, and whether or not they can exist at all. It seems that the knight and wazir are the only leapers with the ability to make the 3-move tour from c1 to b1, , and that there won't be another leaper with that ability until the 3rd dimension (1,2,4) and 4th (1,2,4,8) and then pattern keeps continuing (and analogously the (4,2)leaper and dabbaba are only leapers that can make 3-move tour from c1 to a1 with similar pattern), and regarding a piece that must simultaneously control a1 & c1, there are an infinite number of them. And an infinite number of pieces that can simultaneously control b1 & a2 to do the Zebra's job in the unique Zebra+Ferz checkmate. But there isn't an exact mathematical formula that will say whether or not the piece is flexible enough to make the proper maneuvers to execute the final mate.
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby h.g.muller » Wed Nov 09, 2011 10:48 pm

byakuugan wrote:Eventually I want to get around to studying these concepts for every piece type, like if Knights moved as Camels when not capturing, they would lose a lot of their straightforward cornering abilities, but would be able to maintain control of the same square when moving.

I have done some measurements of empirical piece values on divergent pieces, not based on late end-game but on opening/middle-game performace. Interesting observation was that N,K,mKcN were all very closein value, while mNcK was significantly stronger (about half a Pawn). This was all done with the aid of the virtually knowledgeless Fairy-Max engine, though. I now am constructing a better engine, which will be aware of mating potential, and discount the score of position without it, to do get more reliable empirical values.

Right now I was working on comparing the strengths of normal leapers, when stalemate is not an issue.
It seems that Knight+Knight, Knight+Zebra, Camel+Camel, Camel+Zebra, and Zebra+Zebra (all have 8 move targets and none are mating material against a lone king) generally win against a Flamingo, but not if a piece is only a 4-mover (like Knight+Ferz or Zebra+Wazir won't win). But if instead of a Flamingo, if the defender has an Alfil, then Knight+Knight are the only non-matingmaterial leapers that can win.

It would be nice to make it an option ofthe EGT generator to allow black to null move. Then you would not have to needlessly drive up the building time by including a dummy piece. Unfortunately adding 0,0 as move to the black King will not work, as a 0-step is now used to indicate the end of the list of moves for that piece. Similarly it would be nice to optionally be able to declare stalemate a win, as I did in the version I used for Shatranj.

With the 4-mover examples you quote, apparently zugzwang plays a role in the driving process. Many marginally won end-games have this. I am pretty sure that a pair of Berolina Omni's would not need the zugzwang. But it could be that a Flamingo, however weak it is, still can be used in defense by attacking a crucial square from a large distance.

It seems that the knight and wazir are the only leapers with the ability to make the 3-move tour from c1 to b1,

Indeed, I had reached that conclusion too. But that considers only octo-symmetric simple leapers. As my interest is partly practical, I also want to consider pieces like one encounters in actual Chess variants, which can be of lower symmetry and compound leapers (or divergent). Like the WA, FA, FD, NW compounds. Pieces like Camel, Giraffe and Zebra are awful pieces to play with, (at least on 8x8) absolutely useless in the early end-game. They virtually always are lost without any compensation when the end-game starts, and the only reason they have any opening value at all is that it is very difficult to defend against their long-distance forking power (which does not do much for the attractiveness of the game), so they can be traded for something valuable before the end-game starts. Ferz and Wazir are also no fun, and make for excessively slow and boring games. (It is easy tosee why people abandoned Shatraj for modern Chess...)

So in variants that are fun to play, such as Spartan Chess or the various sub-variants of Chess with Different Armies, tend to have 8 or 12-movers, usually octo-symmetric compound leapers, often without individual mating potential. So I am looking for theories that can also be applied to those.
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby byakuugan » Thu Nov 10, 2011 2:12 pm

I imagined that I would study the single leapers with different moving/capturing abilities before finishing studying hybrids, because that would make finding the mathematical formulas a lot simpler if each characteristic of the piece was treated as individual. I think best would be to find the "minimal" piece needed to accomplish a certain task, that way it would be easy to find the abilities of high-value pieces simply by knowing the minimals.
Example: The movement ability of the Wazir is optimal for making the 3-move tour from c1 to b1, but the capturing ability doesn't really matter, so you could use that logic to say that pieces like mWcZ or mWcG could mate with a Camel in corner same color as Camel, or some other piece that can fork a1 & c1 not from b3. I used to imagine that mWcN is the strongest, but taking into account the fact that it is the Zebra's or Giraffe's awkward movements that make them weak, it might actually be better to have targets that are spread out more, since they can move in any Wazir direction.
byakuugan
 
Posts: 35
Joined: Tue May 18, 2010 4:36 am

Re: How do you generate tablebases?

Postby h.g.muller » Thu Nov 10, 2011 6:01 pm

I have uploaded a new version of the generator (same link). It fixes a probing bug I discovered for when the King was on the diagonal, and a bug in the determination of color-binding of pieces in the piecedef.ini file (affecting the number of columns in the rep2.txt stats file).

But the most important thing is that it can now also calculate under rules where stalemate is a win, stalemate is a forced pass, or where turn passing is allowed always (in which case stalemate is nonexistent). To invoke such rules, the flags -0 (null, not oh!) and -s can be added to the command line. The new syntax is

4men [-xboard] [-0] [-s] KNN.K

When -0 -s are both present, stalemate is a forced pass. Otherwise -0 switches on black turn passing, and -s makes stalemating a win.

KNN.K seems to be won under any of these conditions. Even KFF.K is won when there is no stalemate (but does need zugzwang). KBB.K and KBN.K seem to be also winnable without zugzwang.
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: How do you generate tablebases?

Postby h.g.muller » Fri Nov 18, 2011 8:22 am

I released yet another version of the EGT generator (see the other thread I started). This one supports one more thing you proposed, namely the possibility to declare selected positions ('sub-goals') a win. Like having the black King in a corner (even if it is the safe corner). You can list the collection of positions that constitute the sub-goal in a file, and specify a DTx for each of them (so you could also specify them as a draw).

The -0 and the combination -0 -s is now handled a bit differently: even when black is allowed to null move, the generator still recognizes stalemate (non-check and null-move the only possible move), and assigns a score to it as per the -s option (i.e. without -s: draw, with -s :loss).
h.g.muller
 
Posts: 208
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 1 guest