I have eliminated ALL if statements from the move generator :)

Discussion of chess software programming and technical issues.

Moderator: Ras

Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

I have eliminated ALL if statements from the move generator :)

Post by Mike Sherwin »

Even in the castling code which I thought was not possible! :D

It is a bitboard move generator that does not make a move list. It simply generates and stores all the bitboards by [ply] and by [fs]. The philosophy is why spin all those bits into a move list before the moves are needed and lose all that information in the process. Meaning that if a killer move is being tried it is quick to verify the move by looking at gbb[ply][fs] to see if the ts bit is set, etc. It will work most efficiently when the position is legal. That is because the check for legality has become a branchless calculation rather than using an if statement. As in return 1 - (king[1 - stm] & abb[ply]);. abb[ply] is the attacked squares bitboard that is very useful in other parts of the code like for move ordering, etc. Rather than keeping castling rights in other parts of the code it just uses pseudo pieces like WKC (white king that can castle) and WRC. When a WKC moves it puts a WK on the board and castling cost no more clock cycles after that. And WRC becomes just WR when a WRC moves.

So as of now there is not a single if statement in, GenAllMoves(), GenQuiescent(), MakeMove() and TakeBack(), and that is very pleasing. 8-)

It is using Bob's classical approach which I have spent much time optimizing. However, it can be changed to use any sliding piece generators. And the pawn code is much faster than in RomiChess. I also spent a lot of time on that.

Code: Select all

bool GenAllMoves(Thread* t) {
  s08 fs, ft;
  u64 b, atk;

  u64 pieces = piece[stm];
  u64 notme = ~pieces;
  u64 occ = pieces | piece[1 - stm];
  u64 empty = ~occ;
  u64 enemy = notme ^ empty;

  abb[ply] = 0;

  do {
    fs = std::countr_zero(pieces);
    ft = board[fs];
    switch (ft) {
    case ES:
      // can't get here
      break;
    case WP:
      switch (fs >> 3) {
      case RANK1:
        // can't get here
        break;
      case RANK2:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        gbb[ply][fs] |= ((gbb[ply][fs] << 8) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] = atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK3:
      case RANK4:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] = atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK5:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] |= (atk & (enemy | epbit[ply]));
        abb[ply] |= atk;
        break;
      case RANK6:
      case RANK7:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] = atk & enemy;
        abb[ply] |= atk;
        break;
      }
      break;
    case WN:
      gbb[ply][fs] = knightMoves[fs] & notme;
      abb[ply] |= knightMoves[fs];
      break;
    case WB:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].SE & occ)].SE
        | ray[std::countl_zero(ray[fs].SW & occ)].SW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case WRC:
    case WR:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].SS & occ)].SS
        | ray[std::countl_zero(ray[fs].WW & occ)].WW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case WQ:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].SE & occ)].SE
        | ray[std::countl_zero(ray[fs].SW & occ)].SW
        | ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].SS & occ)].SS
        | ray[std::countl_zero(ray[fs].WW & occ)].WW
        ^ queenMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case WKC:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      gbb[ply][fs] |= (u64)((((board[h1] == WRC) + !(occ & SWCS) + !AttackedByBlack(t, AWCS)) == 3) << g1);
      gbb[ply][fs] |= (u64)((((board[a1] == WRC) + !(occ & SWCL) + !AttackedByBlack(t, AWCL)) == 3) << c1);
      break;
    case WK:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        // can't get here
        break;
      case RANK2:
      case RANK3:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK4:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= (atk & (enemy | epbit[ply]));
        abb[ply] |= atk;
        break;
      case RANK5:
      case RANK6:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK7:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        gbb[ply][fs] |= ((gbb[ply][fs] >> 8) & empty);
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= atk & enemy;
        abb[ply] |= atk;
        break;
      }
      break;
    case BN:
      gbb[ply][fs] = knightMoves[fs] & notme;
      abb[ply] |= knightMoves[fs];
      break;
    case BB:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].SE & occ)].SE
        | ray[std::countl_zero(ray[fs].SW & occ)].SW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case BRC:
    case BR:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].SS & occ)].SS
        | ray[std::countl_zero(ray[fs].WW & occ)].WW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case BQ:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].SE & occ)].SE
        | ray[std::countl_zero(ray[fs].SW & occ)].SW
        | ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].SS & occ)].SS
        | ray[std::countl_zero(ray[fs].WW & occ)].WW
        ^ queenMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case BKC:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      gbb[ply][fs] |= ((((board[h8] == BRC) + !(occ & SBCS) + !AttackedByWhite(t, ABCS)) == 3) << g8);
      gbb[ply][fs] |= ((((board[a8] == BRC) + !(occ & SBCL) + !AttackedByWhite(t, ABCL)) == 3) << c8);
      break;
    case BK:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      break;
    }
    pieces ^= 1ull << fs;
  } while (pieces);

  return 1 - (king[1 - stm] & abb[ply]);
}
Top
dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: I have eliminated ALL if statements from the move generator :)

Post by dangi12012 »

Congrats! Does this fit in compile Explorer?
I would like to take a closer look.

You could even do without the switch by looping over the 12 canonical boards directly.

Hair in the soup: A loop is also a conditional branch.

As I have noted in another thread 99.97% of all positions contain 2 of all pieces (or less).
The mitigation - I will pm you with unpunished but implemented ideas.
Also I am glad we revived that algorithm this year!
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Top
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: I have eliminated ALL if statements from the move generator :)

Post by Mike Sherwin »

dangi12012 wrote: ↑Sun Aug 14, 2022 3:22 am Congrats! Does this fit in compile Explorer?
I would like to take a closer look.

You could even do without the switch by looping over the 12 canonical boards directly.

Hair in the soup: A loop is also a conditional branch.

As I have noted in another thread 99.97% of all positions contain 2 of all pieces (or less).
The mitigation - I will pm you with unpunished but implemented ideas.
Also I am glad we revived that algorithm this year!
Thanks!
I never was able to use compile explorer. It's hard to learn new tricks. So I don't know.
I do not use the 12 canonical bitboards. I just use an int board[64] because pseudo piece types are used. For example to be pedantic there could be 36 different types of pawns on the board depending upon color, rank and file. For example a white pawn on a2 is a WX2L and if it captures on b3 it becomes a WR3L, etc. I'm not doing that but the option is there with an s32 board[64] array.
A loop is a very well predicted conditional branch! So no problems there.
Yes of course you helped with the algorithm. And you are credited in the engine introduction! However, my initialization is different and the rev ray is not needed saving a bit of memory.

// bishop rays
for (c = 1, ts = sq + 7; file - c >= FILEa && rank + c <= RANK8; c++, ts += 7) ray[sq].NW |= 1ull << ts;
for (c = 1, ts = sq + 9; file + c <= FILEh && rank + c <= RANK8; c++, ts += 9) ray[sq].NE |= 1ull << ts;
for (c = 1, ts = sq - 7; file + c <= FILEh && rank - c >= RANK1; c++, ts -= 7) ray[63 - sq].SE |= 1ull << ts;
for (c = 1, ts = sq - 9; file - c >= FILEa && rank - c >= RANK1; c++, ts -= 9) ray[63 - sq].SW |= 1ull << ts;

The 63 - sq is done in the initialization for negative rays. It simply puts it in the "wrong" cell from the start because the generator gives the wrong square.

I look forward to your pm! :D

Edit: Maybe the rev ray is needed after all. I can't keep anything in my head anymore. :( One is flipped and one is not and that is why the rev ray is needed. Apologies!
Top
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: I have eliminated ALL if statements from the move generator :)

Post by Mike Sherwin »

Okay, it has been changed. I hope it is correct now. Here's all.

Code: Select all

// !
// Equates.cpp

constexpr auto AWCS = 0b0000000000000000000000000000000000000000000000000000000001110000;
constexpr auto AWCL = 0b0000000000000000000000000000000000000000000000000000000000011100;
constexpr auto ABCS = 0b0111000000000000000000000000000000000000000000000000000000000000;
constexpr auto ABCL = 0b0001110000000000000000000000000000000000000000000000000000000000;

constexpr auto SWCS = 0b0000000000000000000000000000000000000000000000000000000001100000;
constexpr auto SWCL = 0b0000000000000000000000000000000000000000000000000000000000001110;
constexpr auto SBCS = 0b0110000000000000000000000000000000000000000000000000000000000000;
constexpr auto SBCL = 0b0000111000000000000000000000000000000000000000000000000000000000;

enum { EXIT, GETCMD, SEARCH };

enum { BLACK, WHITE };

enum { ILLEGAL, LEGAL };

enum {
  a1, b1, c1, d1, e1, f1, g1, h1,
  a2, b2, c2, d2, e2, f2, g2, h2,
  a3, b3, c3, d3, e3, f3, g3, h3,
  a4, b4, c4, d4, e4, f4, g4, h4,
  a5, b5, c5, d5, e5, f5, g5, h5,
  a6, b6, c6, d6, e6, f6, g6, h6,
  a7, b7, c7, d7, e7, f7, g7, h7,
  a8, b8, c8, d8, e8, f8, g8, h8
};

enum { FILEa, FILEb, FILEc, FILEd, FILEe, FILEf, FILEg, FILEh };

enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

enum {
  ES,
  WP, WN, WB, WRC, WR, WQ, WKC, WK,
  BP, BN, BB, BRC, BR, BQ, BKC, BK
};

// !
// Defines.cpp

typedef char s08;
typedef int s32;
typedef unsigned long long u64;
typedef long long s64;

struct Ray {
  u64 NW;
  u64 NN;
  u64 NE;
  u64 EE;
  u64 SE;
  u64 SS;
  u64 SW;
  u64 WW;
  u64 RSE;
  u64 RSS;
  u64 RSW;
  u64 RWW;
};

struct sMove {
  s08 fs;
  s08 ts;
  s08 ft;
  s08 tt;
  s32 sc;
};

union uMove {
  sMove s;
  u64 u;
};

struct rMove {
  uMove u;
  u64 r;
};

struct Thread {
  uMove g[500];
  u64 piece[2];
  u64 king[2];
  u64 epbit[100];
  u64 abb[100];
  u64 gbb[100][64];
  s32 board[64];
  s32 fifty[100];
  s32 ply;
  s32 gly;
  s32 stm;
};

#define g     t->g
#define piece t->piece
#define king  t->king
#define epbit t->epbit
#define abb   t->abb
#define gbb   t->gbb
#define board t->board
#define ply   t->ply
#define gly   t->gly
#define stm   t->stm

// !
// Globals.cpp

s32 mode;

s32 numThreads;

Thread** thread;

Ray ray[64];

u64 wPawnCapts[64];
u64 bPawnCapts[64];
u64 knightMoves[64];
u64 bishopMoves[64];
u64 rookMoves[64];
u64 queenMoves[64];
u64 kingMoves[64];

// !
// Initialize.cpp

void InitThreads() {
  numThreads = 32;

  thread = new Thread * [numThreads];

  for (s32 i = 0; i < numThreads; i++) {
	thread[i] = new Thread;
  }
}

void InitRays() {
  s32 c, ts, file, rank;
  for (s32 sq = a1; sq <= h8; sq++) {
	file = sq & 7;
	rank = sq >> 3;

	ray[sq].NW = 0;
	ray[sq].NN = 0;
	ray[sq].NE = 0;
	ray[sq].EE = 0;
	ray[sq].SE = 0;
	ray[sq].SS = 0;
	ray[sq].SW = 0;
	ray[sq].WW = 0;

	// bishop rays
	for (c = 1, ts = sq + 7; file - c >= FILEa && rank + c <= RANK8; c++, ts += 7) ray[sq].NW |= 1ull << ts;
	for (c = 1, ts = sq + 9; file + c <= FILEh && rank + c <= RANK8; c++, ts += 9) ray[sq].NE |= 1ull << ts;
	for (c = 1, ts = sq - 7; file + c <= FILEh && rank - c >= RANK1; c++, ts -= 7) ray[sq].SE |= 1ull << ts;
	for (c = 1, ts = sq - 9; file - c >= FILEa && rank - c >= RANK1; c++, ts -= 9) ray[sq].SW |= 1ull << ts;

	// rook rays
	for (c = 1, ts = sq + 8; rank + c <= RANK8; c++, ts += 8) ray[sq].NN |= 1ull << ts;
	for (c = 1, ts = sq + 1; file + c <= FILEh; c++, ts += 1) ray[sq].EE |= 1ull << ts;
	for (c = 1, ts = sq - 8; rank - c >= RANK1; c++, ts -= 8) ray[sq].SS |= 1ull << ts;
	for (c = 1, ts = sq - 1; file - c >= FILEa; c++, ts -= 1) ray[sq].WW |= 1ull << ts;
  }

  for (s32 sq = a1; sq <= h8; sq++) {
	ray[63 - sq].RSE = ray[sq].SE;
	ray[63 - sq].RSS = ray[sq].SS;
	ray[63 - sq].RSW = ray[sq].SW;
	ray[63 - sq].RWW = ray[sq].WW;
  }
}

void InitBoardBB() {
  s32 file, rank;
  for (s32 sq = a1; sq <= h8; sq++) {
	file = sq & 7;
	rank = sq >> 3;

	wPawnCapts[sq] = 0;
	bPawnCapts[sq] = 0;
	knightMoves[sq] = 0;
	bishopMoves[sq] = 0;
	rookMoves[sq] = 0;
	queenMoves[sq] = 0;
	kingMoves[sq] = 0;

	// pawns
	if (sq >= a2 && sq <= h7) {
	  if (file != FILEa) {
		wPawnCapts[sq] |= 1ull << (sq + 7);
		bPawnCapts[sq] |= 1ull << (sq - 9);
	  }
	  if (file != FILEh) {
		wPawnCapts[sq] |= 1ull << (sq + 9);
		bPawnCapts[sq] |= 1ull << (sq - 7);
	  }
	}

	// knights
	if (rank <= RANK6 && file <= FILEg) knightMoves[sq] |= 1ull << (sq + 17);
	if (rank <= RANK7 && file <= FILEf) knightMoves[sq] |= 1ull << (sq + 10);
	if (rank >= RANK2 && file <= FILEf) knightMoves[sq] |= 1ull << (sq - +6);
	if (rank >= RANK3 && file <= FILEg) knightMoves[sq] |= 1ull << (sq - 15);
	if (rank >= RANK3 && file >= FILEb) knightMoves[sq] |= 1ull << (sq - 17);
	if (rank >= RANK2 && file >= FILEc) knightMoves[sq] |= 1ull << (sq - 10);
	if (rank <= RANK7 && file >= FILEc) knightMoves[sq] |= 1ull << (sq + +6);
	if (rank <= RANK6 && file >= FILEb) knightMoves[sq] |= 1ull << (sq + 15);

	// bishops
	bishopMoves[sq] = ray[sq].NW | ray[sq].NE | ray[63 - sq].SE | ray[63 - sq].SW;

	//rooks
	rookMoves[sq] = ray[sq].NN | ray[sq].EE | ray[63 - sq].SS | ray[63 - sq].WW;

	// queen
	queenMoves[sq] = bishopMoves[sq] | rookMoves[sq];

	// king
	if (rank <= RANK7) kingMoves[sq] |= 1ull << (sq + 8);
	if (rank >= RANK2) kingMoves[sq] |= 1ull << (sq - 8);
	if (file <= FILEg) kingMoves[sq] |= 1ull << (sq + 1);
	if (file >= FILEb) kingMoves[sq] |= 1ull << (sq - 1);
	if (rank <= RANK7 && file <= FILEg) kingMoves[sq] |= 1ull << (sq + 9);
	if (rank >= RANK2 && file <= FILEg) kingMoves[sq] |= 1ull << (sq - 7);
	if (rank >= RANK2 && file >= FILEb) kingMoves[sq] |= 1ull << (sq - 9);
	if (rank <= RANK7 && file >= FILEb) kingMoves[sq] |= 1ull << (sq + 7);
  }
}

void NewGame(Thread* t) {
  ply = 0;
  gly = 0;
}

void Initialize() {
  mode = GETCMD;
  InitThreads();
  InitRays();
  InitBoardBB();
  NewGame(thread[0]);
}

// !
// GenMoves.cpp

bool GenAllMoves(Thread* t) {
  s08 fs, ft;
  u64 b, atk;

  u64 pieces = piece[stm];
  u64 notme = ~pieces;
  u64 occ = pieces | piece[1 - stm];
  u64 empty = ~occ;
  u64 enemy = notme ^ empty;

  abb[ply] = 0;

  do {
    fs = std::countr_zero(pieces);
    ft = board[fs];
    switch (ft) {
    case ES:
      // can't get here
      break;
    case WP:
      switch (fs >> 3) {
      case RANK1:
        // can't get here
        break;
      case RANK2:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        gbb[ply][fs] |= ((gbb[ply][fs] << 8) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] = atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK3:
      case RANK4:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] = atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK5:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] |= (atk & (enemy | epbit[ply]));
        abb[ply] |= atk;
        break;
      case RANK6:
      case RANK7:
        gbb[ply][fs] = ((0x0000000000000100ull << fs) & empty);
        atk = wPawnCapts[fs];
        gbb[ply][fs] = atk & enemy;
        abb[ply] |= atk;
        break;
      }
      break;
    case WN:
      gbb[ply][fs] = knightMoves[fs] & notme;
      abb[ply] |= knightMoves[fs];
      break;
    case WB:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].RSE & occ)].SE
        | ray[std::countl_zero(ray[fs].RSW & occ)].SW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case WRC:
    case WR:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].RSS & occ)].SS
        | ray[std::countl_zero(ray[fs].RWW & occ)].WW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case WQ:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].RSE & occ)].SE
        | ray[std::countl_zero(ray[fs].RSW & occ)].SW
        | ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].RSS & occ)].SS
        | ray[std::countl_zero(ray[fs].RWW & occ)].WW
        ^ queenMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case WKC:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      gbb[ply][fs] |= (u64)((((board[h1] == WRC) + !(occ & SWCS) + !AttackedByBlack(t, AWCS)) == 3) << g1);
      gbb[ply][fs] |= (u64)((((board[a1] == WRC) + !(occ & SWCL) + !AttackedByBlack(t, AWCL)) == 3) << c1);
      break;
    case WK:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        // can't get here
        break;
      case RANK2:
      case RANK3:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK4:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= (atk & (enemy | epbit[ply]));
        abb[ply] |= atk;
        break;
      case RANK5:
      case RANK6:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= atk & enemy;
        abb[ply] |= atk;
        break;
      case RANK7:
        gbb[ply][fs] = (1ull << (fs - 8)) & empty;
        gbb[ply][fs] |= ((gbb[ply][fs] >> 8) & empty);
        atk = bPawnCapts[fs];
        gbb[ply][fs] |= atk & enemy;
        abb[ply] |= atk;
        break;
      }
      break;
    case BN:
      gbb[ply][fs] = knightMoves[fs] & notme;
      abb[ply] |= knightMoves[fs];
      break;
    case BB:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].RSE & occ)].SE
        | ray[std::countl_zero(ray[fs].RSW & occ)].SW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case BRC:
    case BR:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].RSS & occ)].SS
        | ray[std::countl_zero(ray[fs].RWW & occ)].WW
        ^ bishopMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case BQ:
      gbb[ply][fs]
        = ray[std::countr_zero(ray[fs].NW & occ)].NW
        | ray[std::countr_zero(ray[fs].NE & occ)].NE
        | ray[std::countl_zero(ray[fs].RSE & occ)].SE
        | ray[std::countl_zero(ray[fs].RSW & occ)].SW
        | ray[std::countr_zero(ray[fs].NN & occ)].NN
        | ray[std::countr_zero(ray[fs].EE & occ)].EE
        | ray[std::countl_zero(ray[fs].RSS & occ)].SS
        | ray[std::countl_zero(ray[fs].RWW & occ)].WW
        ^ queenMoves[fs];
      abb[ply] |= gbb[ply][fs];
      gbb[ply][fs] &= notme;
      break;
    case BKC:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      gbb[ply][fs] |= (u64)((((board[h8] == BRC) + !(occ & SBCS) + !AttackedByWhite(t, ABCS)) == 3) << g8);
      gbb[ply][fs] |= (u64)((((board[a8] == BRC) + !(occ & SBCL) + !AttackedByWhite(t, ABCL)) == 3) << c8);
      break;
    case BK:
      gbb[ply][fs] = kingMoves[fs] & notme;
      abb[ply] |= kingMoves[fs];
      break;
    }
    pieces ^= 1ull << fs;
  } while (pieces);

  return 1 - (king[1 - stm] & abb[ply]);
}

// !
// Main.cpp

s32 main() {

  Initialize();

  while (mode) {
	if (mode == GETCMD) GetCommand();
	if (mode == SEARCH) StartSearch(thread[0]);
  }

  return 0;
}

// !
// !.cpp

#include <bit>

#include "Defines.cpp"
#include "Equates.cpp"
#include "Globals.cpp"
#include "Utilities.cpp"
#include "Move.cpp"
#include "GenMoves.cpp"
#include "Search.cpp"
#include "GetCommand.cpp"
#include "Initialize.cpp"
#include "Main.cpp"
I just started this rewrite today. It will be able to search up to the, number of threads, starting positions in a GUI designed to do that. It will use continuous Real Time Learning on each position until the user tells it to quit a position. It will run RTL for an amount of time followed by an n ply search followed by more RTL followed by more searching, etc.

And for now the name is just !, lol. Maybe I'll name it NewRomi or RomiChess 2022 or ...
Top
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: I have eliminated ALL if statements from the move generator :)

Post by lithander »

Very interesting! The branchless stuff is neat, I guess, but the fact that you store bitboards instead of moves is also a thought-provoking novelty to me.

Currently I generate my move-lists and then have to go over the list again and remove the hash-move and later also the killer-moves from the list of quiets so I don't play them again. (You can play them again because it's usually resolved quickly through a TT hit but I use the number of played moves for LMR and it bugs me when I count duplicates)

With your idea of generating bitboards instead of moves maybe my problem could also be solved more elegantly by masking.
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
Top
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: I have eliminated ALL if statements from the move generator :)

Post by hgm »

The problem is that at some point you will want to sort the moves, e.g. by history score. That seems hard when you 'bundle' them by from-square.

For captures it would be far more useful to bundle them by to-square. They then already start sorted in MVV order.
Top
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: I have eliminated ALL if statements from the move generator :)

Post by Mike Sherwin »

lithander wrote: ↑Sun Aug 14, 2022 1:21 pm Very interesting! The branchless stuff is neat, I guess, but the fact that you store bitboards instead of moves is also a thought-provoking novelty to me.

Currently I generate my move-lists and then have to go over the list again and remove the hash-move and later also the killer-moves from the list of quiets so I don't play them again. (You can play them again because it's usually resolved quickly through a TT hit but I use the number of played moves for LMR and it bugs me when I count duplicates)

With your idea of generating bitboards instead of moves maybe my problem could also be solved more elegantly by masking.
Thanks Thomas for the positive reply. Maybe Leorik 3 will do it this way. 8-)
Top
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: I have eliminated ALL if statements from the move generator :)

Post by Mike Sherwin »

hgm wrote: ↑Sun Aug 14, 2022 2:55 pm The problem is that at some point you will want to sort the moves, e.g. by history score. That seems hard when you 'bundle' them by from-square.

For captures it would be far more useful to bundle them by to-square. They then already start sorted in MVV order.
At the end of the generation there is abb[ply] which is the attack bitboard making it trivial to find if the Queen [etc.] is attacked so time is not wasted looking for attackers when there are none.
Top
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: I have eliminated ALL if statements from the move generator :)

Post by hgm »

But if it is attacked, you will somehow have to find out what attacks it (in LVA order if there are more).
Top
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: I have eliminated ALL if statements from the move generator :)

Post by Mike Sherwin »

hgm wrote: ↑Sun Aug 14, 2022 7:14 pm But if it is attacked, you will somehow have to find out what attacks it (in LVA order if there are more).
True, but on most squares most of the time the queen is either not attacked or not attacked by more than one piece. So if there was no abb[ply] most of the time will be spent just finding out if the queen is attacked at all. I remember what you did in your mailbox trials thread and while extremely efficient in the opening and middlegame I still suspect that it would lose efficiency as the number of pieces diminished. What I'm doing if I understand it correctly is improving the efficiency of a bitboard move generator quite a bit by not taking the time to spin the bits into a move list and then using the bits for some cheap test that are not possible once the bits are destroyed. And any early beta-cut once the bits are generated means never having to spin the remaining bits into moves. I don't see a downside except using memory to store the bits. But does that really matter that much on modern machines? I guess the question to ask is how would you change a bitboard mg to do more efficient MVV - (LVA / n) move ordering?
Top

Return to “Computer Chess Club: Programming and Technical Discussions”