move structure

[smatovic]

keep its size small or put as much information as possible in it?

My thoughts for an 0x88 Engine:

Code: Select all

/*  Move 64 bit
    1-7:   from square 
    8-14:  to square 
    15-21: capture square
    22-24: from piece type
    25-27: to piece type/ promo piece
    28-30: captured piece type
    31:    castle flag
    32:    pawn double square move /en passant flag
    Castling Rights
    33: White King E1 moved
    34: White Rook A1 moved
    35: White Rook H1 moved
    36: Black King E8 moved
    37: Black Rook A8 moved
    38: Black Rook H8 moved

    48-64  move score
*/

...not sure about the castling rights and the score...

Regards,
Srdja

[hgm]

Why would you want to put all that stuff in the move structure, for a 0x88 engine? I just have from square and to-square. When I need the victim or the piece, I can fetch it just as easily from the board as from a move structure.

To indicate castling or promotion, I use off-board to-squares.

[smatovic]

The search i use is not recursive, its based on a while loop with a move stack.

Until now i created hole boards instead of domove/undomove.

If i put more information from the move generator into the move structure i keep the domove function slim, otherwise i have to handle en passant and castling in domove more complex.

[hgm]

OK, I see. So this really has the function of the stack frame of local variables in a recursive implementation, and it has to contain all information needed to undo the move. As the board usually does contain piece numbers rather than piece types, I guess you would have to store those in stead.

But why would you want to make that compact? This just causes extra work unpacking it. Putting data that is used separately in places where it can also be accessed separately (e.g. in a separate byte) seems much more efficient, even if it takes some extra memory. (Unless you are programming an embedded micro-controller chip with only 256 bytes RAM, or something like that.)

Testing a bit flag does not require less complicated code than testing if a 0x88 square is off-board. The latter also tests specific bits of the square number. If that test indicates, say, a castling, I use the full square number as index in tables that tell me the Rook from- and to-square. This is more efficient than figuring out these squares in the move generation, as you might never get to doing the move, because of beta cutoffs.

[smatovic]

But why would you want to make that compact? This just causes extra work unpacking it. Putting data that is used separately in places where it can also be accessed separately (e.g. in a separate byte) seems much more efficient, even if it takes some extra memory. (Unless you are programming an embedded micro-controller chip with only 256 bytes RAM, or something like that.)

Something familiar, i (try) to code in OpenCl on a GPU. Some have just 512 Bytes of private/local memory by thread or process and no recursion is possible. So i need a movestack in global memory anyway...

Testing a bit flag does not require less complicated code than testing if a 0x88 square is off-board. The latter also tests specific bits of the square number. If that test indicates, say, a castling, I use the full square number as index in tables that tell me the Rook from- and to-square. This is more efficient than figuring out these squares in the move generation, as you might never get to doing the move, because of beta cutoffs.

MicroMaxs Castling Handling is still a little mystery for me...i have to take a closer look into your code. I use the idea of a king capture engine also for castling. If the lastmove was a castling (therefore the castling flag ) i check if the affected squares are attacked.

By the way:
I ported the MicroMax move generator (without castling) to the GPU...its faster than my own 12x10 Array Code and my first BitBoard approach. I extended the main while loop with BitBoard information....

Code: Select all

while (bb) 
x=pop_1st_bit(&bb)
....

Just have to keep the BitBoard for each side up to date when pieces are changing...

[Edmund]

The search i use is not recursive, its based on a while loop with a move stack.

Until now i created hole boards instead of domove/undomove.

If i put more information from the move generator into the move structure i keep the domove function slim, otherwise i have to handle en passant and castling in domove more complex.

I don't quite get you. If you create whole new boards, then why keep the undo information at all? All it would take is sq_from, sq_to, promotion_piece (, score).

Should you however need to restore the old board, I would suggest using a second struct for the relevant information. That has two reasons. Firstly it wastes space having such bulky move structures and secondly it takes more time to fill them. In the alpha beta search on cut nodes it is very likely that you will never have to search more than the first move of the movelist so all the packing of the others was a waste of time. Thats why you will mostly find in other programs just sq_from, sq_to, promotion_piece, score in the movelist. And only once you have eventually reached the move_to you fill an additional structure with data (ep-flag, castling-flags, 50-move counter, hash, captured piece) this struct is mostly small enough so you can keep this as your stack information. That means you only have to deal with it during move make and can just drop it in unmake.

[hgm]

MicroMaxs Castling Handling is still a little mystery for me...i have to take a closer look into your code. I use the idea of a king capture engine also for castling. If the lastmove was a castling (therefore the castling flag ) i check if the affected squares are attacked.

Micro-Max uses the same system. The square skipped by the King on castling is passed as e.p. square E to the daughter node. There a check is made if the e.p. square is occupied (to distinguish it from genuine e.p.; after castling the Rook stands there), and if it is any capture to a square between E-1 and E+1 is considered a King capture, and causes an immediate return with a +INF score. (This caused a bug in early uMax versions, because the capture to the old from-square of the King is a capture to an empty square, so that Pawns refused to make it, and you were allowed to casle out of a Pawn check. So I had to move the test up to before testing the validity of Pawn moves, which now also considers a Pawn non-capture to any of these squares as a show stopper. This turned out to be without consequence, as when you have a Pawn non-capture to one of the criticl squares, you will always have at least one Pawn capture to nother critical square. Come to think of it, this probably fails in variant berolina for Fairy-Max...)

I suppose you have not enough RAM to keep move lists. So when you use the triply nested loop for move generation, and immediately search every move as it is generated (as uMax does), you would have to store the state of the move generator (the three loop indices) as well. Now the inner and outer loop indexes are the to- and from-squares themselves, but you still would have to store the ndex of the loop over directions.

An alternative I thought about for when RAM is extremely scarce is to encode moves as 1 byte, using a lookup table (which can be in ROM) to transte the byte code to a piece number plus step vector. On undo the to-square could then be recovered from the piece list, and the from-square calculated from it with the aid of the step vector. Another lookup table, also indexed by the move code, could give you the code for the next move of this piece.

[smatovic]

don't quite get you. If you create whole new boards, then why keep the undo information at all? All it would take is sq_from, sq_to, promotion_piece (, score).

The boards i create resist currently in global memory (RAM), which is slow. What I want is to keep an actual working-board in private/local memory (L1/L2) to perform a fast move generation. Therefore i want to use domove/undomove functions. I could store the needed data in seperate places instead of packing it into a move. But i am not sure if the handling (indexing, settting, clearing) of that places is slower than packing all data into one move structure.

[smatovic]

Micro-Max uses the same system.

Then i understood after all your documention.

(This caused a bug in early uMax versions, because the capture to the old from-square of the King is a capture to an empty square, so that Pawns refused to make it, and you were allowed to casle out of a Pawn check. So I had to move the test up to before testing the validity of Pawn moves, which now also considers a Pawn non-capture to any of these squares as a show stopper.

Thanks for the explanation. I fall into this pawn "trap"...

I suppose you have not enough RAM to keep move lists. So when you use the triply nested loop for move generation, and immediately search every move as it is generated (as uMax does), you would have to store the state of the move generator (the three loop indices) as well. Now the inner and outer loop indexes are the to- and from-squares themselves, but you still would have to store the ndex of the loop over directions.

There is enough RAM/global memory for keeping move lists. Just want to keep the actual board in L1/L2 memory which is on some GPUs 512 bytes by thread/process.

An alternative I thought about for when RAM is extremely scarce is to encode moves as 1 byte, using a lookup table (which can be in ROM) to transte the byte code to a piece number plus step vector. On undo the to-square could then be recovered from the piece list, and the from-square calculated from it with the aid of the step vector. Another lookup table, also indexed by the move code, could give you the code for the next move of this piece.

Good trick,but even with 1 Byte for a move it lacks L1/L2 memory on some GPUs.
The move stack i use to resolve recursion has to store "depth * 218 possible moves"

[hgm]

Indeed, you could not afford a move stack in local RAM. This design was for micro-controllers, where you cannot afford a move stack at all, and thus are forced to do the moves in move-generator order (like uMax does).

Code: Select all

move = nextMoveTable[victim==EMPTYSQUARE][move];
piece = pieceTable[move];
from = position[piece];
to = from + stepTable[move];
if(to & 0x88) continue; // off-board
victim = board[to];
if(victim & stm) continue; // capture own

would be a reasonably efficient way to generate moves.