Partial Magic Boards

[Roy van Rijn]

So, I'm now about to implement magic boards into my engine. And I've been reading a lot about the different kind of magic board (some even fancier then the other, no pun intended). The main goal in optimizing bitboards seems to be having as small as possible hashes, thus smaller tables.

For some reason (which I haven't found out yet) the tables for the rook are much larger then the bishop tables. But that got me thinking, why not have two tables for the rook? One will have the vertical line(s) the other the horizontal lines. This would probably leave a very small hash and will result in two small tables. The obvious drawback is doing twice the work for a rook, two magic lookups.

Has anybody played with this idea before? Or is the idea flawed from the start?

You can mask like this:

rookVert:
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 X 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0

rookHor:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 X 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

It is one small step back in the space-time tradeoff, but if the tables are small enough I think it might be beneficial.
The tables could even be reused if you turn the occ mask-result 90 degrees, leaving just one small rook lookup table. But turning the board 90 degrees (and back) takes quite a lot of processing... and is probably not worth it.

I've seen only one table comparing the performance of different board implementations. I.e. different kinds of magic boards v.s. Kogge Stone v.s. classic methods. Are there more?

[Grant Osborne]

Perhaps you would like to take a look at this http://talkchess.com/forum/viewtopic.ph ... =&start=60

Regards
Grant

[Roy van Rijn]

Ah thanks, I figured something like that had to be done before. Thanks for the link/reading material.

[Gerd Isenberg]

But that got me thinking, why not have two tables for the rook? One will have the vertical line(s) the other the horizontal lines. This would probably leave a very small hash and will result in two small tables. The obvious drawback is doing twice the work for a rook, two magic lookups.

Has anybody played with this idea before? Or is the idea flawed from the start?

You can mask like this:

rookVert:
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 X 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0

rookHor:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 X 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

It is one small step back in the space-time tradeoff, but if the tables are small enough I think it might be beneficial.
The tables could even be reused if you turn the occ mask-result 90 degrees, leaving just one small rook lookup table. But turning the board 90 degrees (and back) takes quite a lot of processing... and is probably not worth it.

I've seen only one table comparing the performance of different board implementations. I.e. different kinds of magic boards v.s. Kogge Stone v.s. classic methods. Are there more?

Hi,
you may also have a look at Kindergarten Bitboards, which covers disjoint rank/file or diagonal/antidiagonal attacks with small tables.

Gerd

[Roy van Rijn]

Actually, I've changed my mind (for the better I hope). I'm going to force myself to implement the (still) missing chess rules first. When I have implemented castling/e.p./(under)promotion/repetition moves, then I might tackle other kinds of move generation. With some minor optimalisations I've already increased the speed another 33%, without even touching the bitboards. Implementing WinBoard-protocol, PGN/FEN notations etc will also take a lot of time, something I'm not looking forward to

Playing around with different bitboards/magic boards, kindergarten and more will probably also be a lot more satisfying when the engine is fully operational.

One thing I'm pondering about, every ply I generate all possible moves, but is this starting from scratch really nessecary? Every move at most 2 pieces have moved (ok, maybe four when castling), so a lot of possible moves will be the same as your last move? Are there engines working with this knowledge in mind? Move-generation is one of the most time-consuming things the engine does right (because it does so many of it)? If a chess engine is able to take advantage of this, going deeper in the permutations will be faster...

It should be possible that, everytime a move is made, you isolate all pieces that might have new moves, and generate new moves for just them. Pieces that don't attack the old or new position of the moved piece and aren't under attack of the piece that moved, will still have the same move-options as before (?).

[H.G.Muller]

Making a competative incremental move generation is very hard. Problem is that moving pieces blocks and unblocks sliders of both sides. So you would either have to reconsider all sliders, or incrementally keep info of which slider can move to which empty square (sorted by square).

FEN reader or WB interface is quite simple. In my Dark Chess engine it is something like this (no castling /e.p. in the FEN, and the negine has no time control because it moves instantly, though). There is no real need to burdon the engine with PGN or SAN.

Code: Select all

int Setup(char *fen)
{
    int r, f, piece;
    char *p = fen, c;

    for(r=7; r>= 0; r--) {
        for(f=0; f<8; f++) board[16*r+f] = 0;
        f = 0;
        while(1) {
            if(*p >='0' && *p <= '9') { f += *p++ - '0'; continue; }
            piece = CharToPiece(*p++);
            if(piece) { board[16*r+f++] = piece; continue; }
            break;
        }
    }
    return *p == 'b' ? BLACK : WHITE;
}


Code: Select all

   while(1) {
        int c, i;
        fflush(stdout);
        if(stm == computer) {
            Search(...); // sets bestX, bestY
            stm = MakeMove(bestX, bestY, 0);
        }
        fflush(stdout);
        i = 0;
        while((line[i++] = getchar()) != '\n') if(c == EOF) return;
        line[i] = 0;
        sscanf(line, "%s", command);
        if(!strcmp(command,"protover"))
        { printf("feature myname=\"Darth " VERSION "\" variants=\"dark\" setboard=1 ping=1 usermove=1 sigint=0 done=1\n"); continue; }
        if(!strcmp(command,"new"))      { stm = Setup("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w"); computer = BLACK; continue; }
        if(!strcmp(command,"go"))       { computer = stm; continue; }
        if(!strcmp(command,"force"))    { computer = NONE; continue; }
        if(!strcmp(command,"variant"))  { continue; }
        if(!strcmp(command,"ping"))     { printf("pong %d\n", atoi(line+5)); continue; }
        if(!strcmp(command,"level"))    { continue; } // TC stuff ignored
        if(!strcmp(command,"time"))     { continue; }
        if(!strcmp(command,"otim"))     { continue; }
        if(!strcmp(command,"st"))       { continue; }
        if(!strcmp(command,"sd"))       { continue; }
        if(!strcmp(command,"infoboard")){ stm = Setup(line+10); continue; }
        if(!strcmp(command,"setboard")) { stm = Setup(line+9); computer = NONE; continue; }
        if(!strcmp(command,"p"))        { PBoard(); continue; } // for debugging
        if(!strcmp(command,"random"))   { srand(GetTickCount()); continue; }
        if(!strcmp(command,""))         { continue; }
        if(!strcmp(command,"usermove")) { stm = MakeMove(line[9]-'a'+16*(line[10]-'1'),line[11]-'a'+16*(line[12]-'1'),line[13]); continue; }
        if(!strcmp(command,"quit"))       return;
    }


[Roy van Rijn]

Thanks for the code example.

I want to create complete FEN in my engine (thus including castling/e.p.) because of the ability to do automatic testing using different kinds of perft tables. I really love the idea of universal (unit-test like) testing for chess, using FEN as input, and Perft tables as reference.

[H.G.Muller]

Sure, in a real engine you would need to understand castling rights and e.p.square. (The example was from an engine that could not castle.) That would hardly add any code, however. After having read the stm field you would ust scan through the FEN looking for KQkq or a-h and set the corresponding castling or e.p. right (depending on how you code these internally, obviously). E.g.

Code: Select all

stm *p == 'b' ? BLACK : WHITE;
while(SetRights(*p++));
return stm;


with SetRights(x) returning 0 when x==0, and 1 otherwise.

[Roy van Rijn]

FEN reader or WB interface is quite simple. In my Dark Chess engine it is something like this (no castling /e.p. in the FEN, and the negine has no time control because it moves instantly, though). There is no real need to burdon the engine with PGN or SAN.

Thanks again for the code, it provided an excellent start for my own implementation. I'm now able to use Arena to play against my own engine, and it works like a charm.
There is just one little bug left (which I already located) so it is almost time to implement evaluation/search (it currently plays random, legal, moves heh).

Current bug: When a rook is captured this removes the castling-rights as well (not just moving the rook or king) My current program will happily castle without the rook in place (!?)