Is it time for another new move generator?

[Michael Sherwin]

Yep!

Code: Select all

// Non Promotion Moves only, No Captures - a la Crafty
// NOT BITBOARD
void GenMoves() {
  s32 fs, ts, type, i, vec, stop, vic;
  u32 vecBits;
  u64 pieces;

  pieces = picesOfColor[wtm];
  do {
       fs = FirstBit64(pieces);
       pieces &= clrBit64(fs);
       type = board[fs];
       vecBits = vectors[fs][type];                     // an index bit for each possible vector
       do {
            i = FirstBit32(vecBits);
            vecBits &= clrBit32(i);
            vec = offset[i];                            // the offset to generate the next square
            stop = theEnd[i][type][fs];                 // the stop value is for off of board  
            for(ts = fs + vec; ts != stop; ts += vec) { // or for a limited range piece 
                 vic = board[ts];                        
                 if(vic) break;                         // No Captures
                 Link(type, fs, ts);                    // Will also link Castling moves
            }
       } while(vecBits);
  } while (pieces);
}

This routine does it all, no seperate move code for any of the piece types including castling.
And it's fast!

[hristo]

Yep!

Code: Select all

// Non Promotion Moves only, No Captures - a la Crafty
// NOT BITBOARD
void GenMoves() {
  s32 fs, ts, type, i, vec, stop, vic;
  u32 vecBits;
  u64 pieces;

  pieces = picesOfColor[wtm];
  do {
       fs = FirstBit64(pieces);
       pieces &= clrBit64(fs);
       type = board[fs];
       vecBits = vectors[fs][type];                     // an index bit for each possible vector
       do {
            i = FirstBit32(vecBits);
            vecBits &= clrBit32(i);
            vec = offset[i];                            // the offset to generate the next square
            stop = theEnd[i][type][fs];                 // the stop value is for off of board  
            for(ts = fs + vec; ts != stop; ts += vec) { // or for a limited range piece 
                 vic = board[ts];                        
                 if(vic) break;                         // No Captures
                 Link(type, fs, ts);                    // Will also link Castling moves
            }
       } while(vecBits);
  } while (pieces);
}

This routine does it all, no seperate move code for any of the piece types including castling.
And it's fast!

I have been using vectors for generating moves for a long time. Currently it takes ~22 CPU cycles to generate a move, where the moves are proper captures (including enpassant), promotions (all) and castling -- what is not validated within the move generator is whether the move would leave the king in check or if a castling move crosses attacked square.

For sliding pieces I use independent vectors that represent the direction in which they slide.
For instance the Knight moves from any given square are stored in a single vector, where the Bishop uses four vectors.
(The Queen borrows the vectors from the Rook and the Bishop)

In the end the size of the vector lookup table is ~9K (this includes all pieces and all squares of origin) I'm sure that those who are 'size' conscious can squeeze the vector table to less than 4K.

Regards.

[Aleks Peshkov]

Code: Select all

stop = theEnd[i][type][fs];                 // the stop value is for off of board  
for(ts = fs + vec; ts != stop; ts += vec) { // or for a limited range piece 
    vic = board[ts];                        
    if(vic) break;                         // No Captures
    Link(type, fs, ts);                    // Will also link Castling moves
}

Looks like a bad mailbox generator: you test each destination square twice: ts != stop and board[ts] != 0 during scanning board for each direction, even for non-sliding piece.
I see you find a way to exclude empty loops for impossible directions for some "from" squares near border. Doing so you may be possibly be able to unroll a first move from each direction and avoid loops with exactly one iteration for nonsliders.

[Aleks Peshkov]

Code: Select all

ts = fs;
do {
    ts += vec;
    if (board[ts]) break;                       
    Link(type, fs, ts);
} while (ts != last) //last legal square

[Karlo Bala]

Code: Select all

ts = fs;
do {
    ts += vec;
    if (board[ts]) break;                       
    Link(type, fs, ts);
} while (ts != last) //last legal square

It reminds me on ingenious idea from gnuchess:

Code: Select all

This file contains a description of GNU's new move generation algoritm.
   Copyright (C) 1989 Free Software Foundation, Inc.

This file is part of CHESS.

CHESS is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY.  No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing.  Refer to the CHESS General Public
License for full details.

Everyone is granted permission to copy, modify and redistribute
CHESS, but only under the conditions described in the
CHESS General Public License.   A copy of this license is
supposed to have been given to you along with CHESS so you
can know your rights and responsibilities.  It should be in a
file named COPYING.  Among other things, the copyright notice
and this notice must be preserved on all copies.

New move Generation algoritm:

Revision: 1989-09-06

Author: Hans Eric Sandstroem.

This algortim is the result of an attempt to make an hardware move
generator, but since I newer had the time and resources to build
the hardware I wrote a software version and incorporated that one
into gnuchess. This was the best way I could think of sharing this
algorithm with the computer chess community.

If there is anybody out there with the time and rescources to build
a hardware move generator I will be glad to assist.

The general idea behind this algoritm is to pre calculate
a lot of data. The data that is pre calculated is every possible move
for every piece from every square disregarding any other pieces on the
board. This pre calculated data is stored in an array that looks like
this:

struct sqdata {
  short nextpos;
  short nextdir;
};
struct sqdata posdata[8][64][64];
/* posdata[piecetype][fromsquare][destinationsquare] */
example:
	the first move for a queen at e8 is stored at;
	posdata[queen][e8][e8].nextpos
	suppose this is e7 and e7 is occupied then the next move
	will be found in;
	posdata[queen][e8][e7].nextdir

To handle the differeces between white and black pawns (they move in
opposite directions) an array ptype has been introduced:

static const short ptype[2][8] = {
  no_piece,pawn,knight,bishop,rook,queen,king,no_piece,
  no_piece,bpawn,knight,bishop,rook,queen,king,no_piece};
           ^^^^^
And it is used like this:
   piecetype = ptype[side][piece]
When generating moves for pieces that are not black pawns, piece
can be used directly in posdata. As in the example above.

Thus the only thing one has to do when generating the moves
is to check for collisions with other pieces. 
the move generation to do this looks like this: (for non pawns)
    p = posdata[piece][sq];
    u = p[sq].nextpos;
    do {
      if (color[u] == neutral) {
        LinkMove(ply,sq,u,xside);
        u = p[u].nextpos;
      }
      else {
        if (color[u] == xside) LinkMove(ply,sq,u,xside);
        u = p[u].nextdir;
      }
    } while (u != sq);

 - I`nt this just beautiful!

The array posdata is initialized in the routine Initialize_moves.
This routine is called just once and it works so no time has been spent
on the structure of this code. GenMoves and CaptureList generates the
moves but the routines ataks, BRscan, Sqatakd, KingScan and trapped
also relies on the move generation algoritm so they have also been
rewritten.

[bob]

You should read Carl Ebeling's thesis (CM university) "All the right moves". He did pretty much this in hardware around 1984-1985 in HiTech. It was the first piece of hardware they had...

[Bill Rogers]

Hi
I am not sure if this is even the same thing but I have been using indices since 1980 in my chess program and the coding looks very similiar to your vectors. I don't know if they are the same thing or not but it sure simpliflied my programming.
Bill
P.S.
My original chess program was written in Basic.

[Michael Sherwin]

Code: Select all

ts = fs;
do {
    ts += vec;
    if (board[ts]) break;                       
    Link(type, fs, ts);
} while (ts != last) //last legal square

Good point Aleks, I will rework it. Thanks!

To others, this is nothing like the move generator in GNUChess. I also have an improved version of that too!

[Michael Sherwin]

Hi Bill,

You are allowed to publish 'basic code'. We C/C++ people are not going to attack you!

[Bill Rogers]

Hi Michael
I did just that years ago. I published my first version of my little chess program. I will see if I still have a copy so you can see my move generator.
Bill