move generation with one dimensional "12 x 10" arr

[AndrewShort]

suppose you use a one dimensional board array, with 120 elements - the classic one with border squares containing, say, 99. 2 border "rows" on bottom and top, and 1 border "column" on left and right. This was, I imagine, the way chess boards were stored internally for a long time, before 0x88 and bitboards were used.

Now imagine your pieces are represented by pos and neg numbers to denote color.

Where I'm getting stuck is how to efficiently test for squares to be not off the board, and either empty or containing an opposing piece. (or, in the cae of piece list, pointing or indexing to empty or opposing piece).

For example, to test if a pawn can capture to its right or left, you would have to test that the destination square is not off the board, and contains an opposing piece. You would have to check the Sign (-1, 0, or 1) of the two pieces - make sure they are not equal, and also check that the destination square is not an off the board square. With say Knights, you have to check that the destination square is not off the board, and that the destination square is either empty or contains an opposing piece. Again, with pos and neg piece values, you have play with signs of the pieces to see if it's possible.

Seems so inefficinet. What tricks do people use. All positive piece values, followed by some kind of bitwise operations to efficiently know the destination square is either empty or contains an opposing piece? (or, in the case of pawn capture - contains an opposing piece but is not empty).

thanks...

[hgm]

Well, for one: never use the sign to distinguish color. Mostly I use different bits for indicating black and white, e.g. the bit indicating 16s and 32s. Then I can set both of these to indicate off board squares ('border guards'), while empty squares have neither of those bits set. That way a border guard always automatically tests as an 'own piece', (if(board[to]&myColor)break;) so that you don't need any extra tests for off-board moves.

Testing for a pure enemy piece could be done with:

if((board[to]&COLORBITS)!=hisColor)break;

In Joker I could gain a little speed by indicating empty squares with a third bit (the 64s bit, say), and preparing a mask for testing the Pawn captures outside the loop over Pawns:

Code: Select all

mask = myColor|64;
for(ALL_PAWNS) {
  ...
  if((board[to]&mask)==0) PUSH_CAPTURE;
  if((board[to]&COLORBITS)==0) PUSH_NONCAPTURE;
}

[Tony]

suppose you use a one dimensional board array, with 120 elements - the classic one with border squares containing, say, 99. 2 border "rows" on bottom and top, and 1 border "column" on left and right. This was, I imagine, the way chess boards were stored internally for a long time, before 0x88 and bitboards were used.

Now imagine your pieces are represented by pos and neg numbers to denote color.

Where I'm getting stuck is how to efficiently test for squares to be not off the board, and either empty or containing an opposing piece. (or, in the cae of piece list, pointing or indexing to empty or opposing piece).

For example, to test if a pawn can capture to its right or left, you would have to test that the destination square is not off the board, and contains an opposing piece. You would have to check the Sign (-1, 0, or 1) of the two pieces - make sure they are not equal, and also check that the destination square is not an off the board square. With say Knights, you have to check that the destination square is not off the board, and that the destination square is either empty or contains an opposing piece. Again, with pos and neg piece values, you have play with signs of the pieces to see if it's possible.

Seems so inefficinet. What tricks do people use. All positive piece values, followed by some kind of bitwise operations to efficiently know the destination square is either empty or contains an opposing piece? (or, in the case of pawn capture - contains an opposing piece but is not empty).

thanks...

Create a new piece "NooneIsAllowedHere" and put it on all of the squares of the border rows and test for it.

Sounds expensive ? It isn't. This is really one of things where you shouldn't optimize too early.

Because fe a bishop going North East:

Code: Select all

toSquare=fromSquare;
while (true)
{
   toSquare+=dirNorthEast;
   if (board[toSquare]==Empty)
   {
      AddMove(fromSquare,toSquare);
      continue;
   }
   if (PieceSide[board[toSquare]]==opponentSide) 
         AddCapture(fromSquare,toSquare);

   break;
}

the test for the border will not show up.


Tony

[Zach Wegner]

That is true, but I would prefer writing it like this, easier to understand IMO:

Code: Select all

toSquare=fromSquare+dirNorthEast;
while (board[toSquare]==Empty)
{
   AddMove(fromSquare,toSquare);
   toSquare+=dirNorthEast;
}
if (PieceSide[board[toSquare]]==opponentSide) 
   AddCapture(fromSquare,toSquare);

but of course, this is a matter of preference. It will most likely generate identical assembly.

[Tony]

That is true, but I would prefer writing it like this, easier to understand IMO:

Code: Select all

toSquare=fromSquare+dirNorthEast;
while (board[toSquare]==Empty)
{
   AddMove(fromSquare,toSquare);
   toSquare+=dirNorthEast;
}
if (PieceSide[board[toSquare]]==opponentSide) 
   AddCapture(fromSquare,toSquare);

but of course, this is a matter of preference. It will most likely generate identical assembly.

Yes, it is.

For certain reasons (bad experiences) that don't really apply here, I only want to apply the addition (+dirNorthEast) at 1 place in the code.

For me that makes sense, but I have to admit, not really in this case.

Cheers,

Tony

[Zach Wegner]

Then how about this?

Code: Select all

goto first;
do
{
   AddMove(fromSquare,toSquare);
first:
   toSquare+=dirNorthEast;
} while (board[toSquare]==Empty);
if (PieceSide[board[toSquare]]==opponentSide) 
   AddCapture(fromSquare,toSquare);

[Tony]

Then how about this?

Code: Select all

goto first;
do
{
   AddMove(fromSquare,toSquare);
first:
   toSquare+=dirNorthEast;
} while (board[toSquare]==Empty);
if (PieceSide[board[toSquare]]==opponentSide) 
   AddCapture(fromSquare,toSquare);

Well, my code is nicely between these 2 ( but hopefully closer to the first one) .

Tony

[bob]

That is true, but I would prefer writing it like this, easier to understand IMO:

Code: Select all

toSquare=fromSquare+dirNorthEast;
while (board[toSquare]==Empty)
{
   AddMove(fromSquare,toSquare);
   toSquare+=dirNorthEast;
}
if (PieceSide[board[toSquare]]==opponentSide) 
   AddCapture(fromSquare,toSquare);

but of course, this is a matter of preference. It will most likely generate identical assembly.

Yes, it is.

For certain reasons (bad experiences) that don't really apply here, I only want to apply the addition (+dirNorthEast) at 1 place in the code.

For me that makes sense, but I have to admit, not really in this case.

Cheers,

Tony

I'd go for a simple 0x88 approach which is simpler and has a nicer characteristic in that you can tell whether two squares are on the same diagonal and not get any "false" matches.

[Zach Wegner]

Personally I think traditional 0x88 is obsolete. You must test the square number first in order to see if its on the board, but you are in most cases going to access the contents of the square anyway to see if the square is empty. If I was going to do a mailbox approach, I'd do 12x16.

[sje]

It was a very long time ago that I wrote a chess program in Zilog z80 assembly language. For obscure reasons that I don't exactly recall, I used an 8x8 byte board centered (two dimensionally) in a 16x16 byte array aligned on a 256 byte boundary. There were two of these boards, one for pieces in index format (zero through five, plus six for vacant), and one for pieces in bit format (six bits plus two bits for colors).

Move generation and attack scanning were both very fast, and unrolling the ray scanning loops helped speed up things. Too bad that the search and the evaluation were quite poor. Still, it beat up on Sargon quite handily.