Devlog of Quixotic

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

Devlog of Quixotic

Post by Mike Sherwin »

Quixotic is showing the first signs of life. I can enter a few moves.
https://www.mediafire.com/file/bwek1zay ... ic.7z/file

Code: Select all

 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  P  P  P  P
 R  N  B  Q  K  B  N  R
e2e4
 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  N  R
e7e4
 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  N  R
e7e5
 r  n  b  q  k  b  n  r
 p  p  p  p  .  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  p  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  N  R
f1a8
 r  n  b  q  k  b  n  r
 p  p  p  p  .  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  p  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  N  R
f1c4
 r  n  b  q  k  b  n  r
 p  p  p  p  .  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  p  .  .  .
 .  .  B  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  .  N  R
f8c5
 r  n  b  q  k  .  n  r
 p  p  p  p  .  p  p  p
 .  .  .  .  .  .  .  .
 .  .  b  .  p  .  .  .
 .  .  B  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  .  N  R
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: Devlog of Quixotic

Post by Mike Sherwin »

More complete ability to enter moves (and to "undo"). Castling, e.p. and pawn promotions verified. I can't say that I have tested every possibility, so feel free to enter move sequences. My approach is quite different. It might be interesting to single step through in debug mode to see how the code works. Or it might not be! The entire MSVC 2022 project is zipped to make it easier to compile and run.
https://www.mediafire.com/file/uig86zh4 ... 3.zip/file
It is not a chess engine yet but it is getting close.
martinn
Posts: 20
Joined: Fri Mar 10, 2023 9:33 am
Full name: Martin Novák

Re: Devlog of Quixotic

Post by martinn »

Hello Mike,
I tried to run your code, I think there are some problems with black captures. For example if I play e2e4 d7d5 g1f3 d5e4 and now undo. The pawn is printed back on e4, but he is really not there. I cannot play anymore d5e4 and if I play something different like d5d4 then white cannot play with e4 pawn either (like e4e5).

But I haven't looked into the code, so maybe it is probably just not implemented yet and my comment is unnecessary.

I recently also started doing my own chess move generator based on your KGSB. Today I was hopefully finally able to find all bugs and passed all perfts. Now I will probably spend another month trying to make it faster, because Kiwipete on depth 5 takes over 7,5 seconds on my computer.
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: Devlog of Quixotic

Post by Mike Sherwin »

martinn wrote: Tue Apr 25, 2023 5:44 pm Hello Mike,
I tried to run your code, I think there are some problems with black captures. For example if I play e2e4 d7d5 g1f3 d5e4 and now undo. The pawn is printed back on e4, but he is really not there. I cannot play anymore d5e4 and if I play something different like d5d4 then white cannot play with e4 pawn either (like e4e5).

But I haven't looked into the code, so maybe it is probably just not implemented yet and my comment is unnecessary.

I recently also started doing my own chess move generator based on your KGSB. Today I was hopefully finally able to find all bugs and passed all perfts. Now I will probably spend another month trying to make it faster, because Kiwipete on depth 5 takes over 7,5 seconds on my computer.
Thanks Martin, I found the problem.

Code: Select all

void BackBP(Thread* t, uMove* m) {
  board[mfs] = BP;
  board[mts] = mtt;
  fsBits[BLACK] ^= 1ull << mfs;
  fsBits[BLACK] ^= 1ull << mts;
  fsBits[WHITE] ^= (u64)(mtt > ES) << mts; // <- the > sign is wrong. Should be less than Empty Square
  mat[WHITE] += value[mtt];                     // should reduce to 1ull << mts instead reduces to 0ull << mts
}
Good luck with your engine! And thanks for using KGSB. And please make it fast. KGSB needs the publicity. :D

And if you start your own Dev Log I will contribute if I can.

Code: Select all

 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  P  P  P  P
 R  N  B  Q  K  B  N  R
e2e4
 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  N  R
d7d5
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  p  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  N  R
g1f3
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  p  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
d5e4
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  p  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
undo
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  p  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
d5e4
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  p  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
undo
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  p  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
d5d4
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  p  P  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
e4e5
 r  n  b  q  k  b  n  r
 p  p  p  .  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  P  .  .  .
 .  .  .  p  .  .  .  .
 .  .  .  .  .  N  .  .
 P  P  P  P  .  P  P  P
 R  N  B  Q  K  B  .  R
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: Devlog of Quixotic

Post by Mike Sherwin »

Today after a little bug hunting I wrote Qsearch as simply as I can just to try to get something up and running. Tomorrow I'll write a depth one search function just so I have something to debug. I could use a second pair of eyes to see if my Qsearch looks reasonable. I'm trying fail soft first.

Code: Select all

s32 Qsearch(Thread* t, s32 alpha, s32 beta) {
  bool ok;
  s08 n = 0;
  u64 tss; // to squares bb
  uMove m[20] = { 0 }, tmp; // Empty list of moves

  s32 score = mat[stm] - mat[1 - stm] + 10;

  if (score >= beta) return score;

  ok = GenCaptures(t);
  if (!ok) return MATE - ply;

  if (!attackers[ply]) return score; // attackers are all the pieces that actually have a capture to make

  if (score > alpha) alpha = score;

  do {
	m[n].s.fs = std::countr_zero(attackers[ply]); // get the from square
	attackers[ply] ^= 1ull << mfs;
	tss = tsBits[ply][m[n].s.fs]; // get the to square bits
	do {
	  m[n].s.ts = std::countr_zero(tss); // get a to square
	  tss ^= 1ull << mts;
	  m[n].s.sc = value[board[m[n].s.ts]] - value[board[m[n].s.fs]]; // Score the move
	  n++;
	} while (tss);
  } while (attackers[ply]);
  
  // now that we have a partially populated list of moves sort them by score, one at a time
  for (s32 i = 0; i < n; i++) {
	for (s32 j = 1; j < n; j++) {
	  if (m[j].s.sc > m[i].s.sc) {
		tmp = m[i];
		m[i] = m[j];
		m[j] = tmp;
	  }
	}

	m[i].s.ft = FindFT(t, &m[i]); // finish filling in the move the from type may change depending on the 
	m[i].s.tt = board[m[i].s.fs];  // specifics of the move
	MakeMove(t, &m[i]);
	m[i].s.sc = -Qsearch(t, -beta, -alpha);
	TakeBack(t, &m[i]);

	if (m[i].s.sc > alpha) {
	  if (m[i].s.sc >= beta) {
		return m[i].s.sc;
	  }
	  alpha = m[i].s.sc;
	}
  }
  return alpha;
}
martinn
Posts: 20
Joined: Fri Mar 10, 2023 9:33 am
Full name: Martin Novák

Re: Devlog of Quixotic

Post by martinn »

Good luck with your engine! And thanks for using KGSB. And please make it fast. KGSB needs the publicity. :D

And if you start your own Dev Log I will contribute if I can.
Well I don't think that I will start making Dev Log. I don't think that I will start turning my move generator into engine now. This is my first time programming something about chess. I have zero knowledge about search or evaluation algorithms. But I've been reading about move generation for a while now, so I wanted to try program something of my own.

I have put my code on Github if you would like to look at it. Here is a link for current state: https://github.com/martinnovaak/motor/releases/tag/v0 . I haven't tested it much yet, but it passed all perft tests from CPW. I haven't still done checks if FEN position is legal, so it is possible that it will crash. Also code is still pretty messy (everything in header files, almost no comments in code).

I found interesting way how KGSB can be used in finding pinners. I have added these 4 simple functions:

Code: Select all

    static uint64_t bishop_diagonal(int sq, uint64_t occ) {
        return  dSubset[sq][(((occ & dMask[sq]) * file_b2_b7) >> 58)];
    }

    static uint64_t bishop_antidiagonal(int sq, uint64_t occ) {
        return  aSubset[sq][(((occ & aMask[sq]) * file_b2_b7) >> 58)];
    }

    static uint64_t rook_horizontal(int sq, uint64_t occ) {
        return hSubset[sq][(occ >> horizontal_shift_table[sq]) & 63];
    }

    static uint64_t rook_vertical(int sq, uint64_t occ) {
        return vSubset[sq][((((occ >> (sq & 7)) & file_a2_a7) * diag_c2h7) >> 58)];
    }
They are really usefull when I need only 1 ray. For example my code to get horizontal pinners:

Code: Select all

 
 	uint64_t horizontal_pinners = KGSSB::rook_horizontal(king_square, occupied) & seen_enemy_hv_pieces;
Like that I can get pinners on all rays from king_square:

Code: Select all

	uint64_t possibly_pinned_pieces = seen_squares & our_side_occupancy;
        uint64_t seen_enemy_pieces  = ~(seen_squares & side_occupancy[their_color]);
        uint64_t seen_enemy_hv_pieces = seen_enemy_pieces & hv_occupancy[their_color];
        uint64_t seen_enemy_ad_pieces = seen_enemy_pieces & ad_occupancy[their_color];
        uint64_t horizontal_pinners = KGSSB::rook_horizontal(king_square, occupied) & seen_enemy_hv_pieces;
        uint64_t vertical_pinners = KGSSB::rook_vertical(king_square, occupied) & seen_enemy_hv_pieces;
        uint64_t antidiagonal_pinners = KGSSB::bishop_antidiagonal(king_square, occupied) & seen_enemy_ad_pieces;
        uint64_t diagonal_pinners = KGSSB::bishop_diagonal(king_square, occupied) & seen_enemy_ad_pieces;
It's used in method get_pinners in board.h.

I have also tried to do some profiling. I have never done that before but I think that KGSSB::rook runs aproximately 3-4x times faster than function KGSSB::bishop. So I was thinking that it could be interesting to combine KGSSB::rook with for example Black magic Bishop and queen could be KGSSB::rook | BlackMagic::bishop. It might be interesting to see if it would be faster or not.
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: Devlog of Quixotic

Post by Mike Sherwin »

martinn wrote: Mon May 01, 2023 12:55 am I have also tried to do some profiling. I have never done that before but I think that KGSSB::rook runs aproximately 3-4x times faster than function KGSSB::bishop. So I was thinking that it could be interesting to combine KGSSB::rook with for example Black magic Bishop and queen could be KGSSB::rook | BlackMagic::bishop. It might be interesting to see if it would be faster or not.
That would be surprising. However, if the KGSSB::rook & Black Magic Bishop is the fastest combo then that should be the standard use.

I downloaded your code and will study it. Thanks :D
martinn
Posts: 20
Joined: Fri Mar 10, 2023 9:33 am
Full name: Martin Novák

Re: Devlog of Quixotic

Post by martinn »

Mike Sherwin wrote: Mon May 01, 2023 1:25 am
martinn wrote: Mon May 01, 2023 12:55 am I have also tried to do some profiling. I have never done that before but I think that KGSSB::rook runs aproximately 3-4x times faster than function KGSSB::bishop. So I was thinking that it could be interesting to combine KGSSB::rook with for example Black magic Bishop and queen could be KGSSB::rook | BlackMagic::bishop. It might be interesting to see if it would be faster or not.
That would be surprising. However, if the KGSSB::rook & Black Magic Bishop is the fastest combo then that should be the standard use.

I downloaded your code and will study it. Thanks :D
Well today I played with Daniel's Chess Movegen. I compared KGSSB Rook with BlackMagic Rook. These are the results:
KGSSB Rook 1004.713782 16544 [129kb] imul64 no https://www.talkchess.com/forum3/viewto ... 4&start=30
Black Magic Rook 789.071881 88891 [694kb] imul64 no Onno Garms and Volker Annuss https://www.chessprogramming.org/Magic_ ... hift_Fancy

For bishop I got these results:
KGSSB Bishop 792.945953 16544 [129kb] imul64 no https://www.talkchess.com/forum3/viewto ... 4&start=30
Black Magic Bishop 1087.234239 88891 [694kb] imul64 no Onno Garms and Volker Annuss https://www.chessprogramming.org/Magic_ ... hift_Fancy

The results simply almost switched. Maybe that is the reason why BlackMagic and KGSSB results for Queen are so similar. Then I merged KGSSB::Rook with BlackMagic::Bishop and these are new results for the Queen:

KGSSB Bishop + BlackMagic Bishop 580.753818 16544 [129kb] imul64 no https://www.talkchess.com/forum3/viewto ... 4&start=30
Black Magic BB 501.439549 88891 [694kb] imul64 no Onno Garms and Volker Annuss https://www.chessprogramming.org/Magic_ ... hift_Fancy
Kindergarten Super SISSY Bitboards 495.964912 16544 [129kb] imul64 no Michael Sherwin https://www.talkchess.com/forum3/viewto ... 4&start=30
Pext constexpr 717.957554 107904 [843kb] pext_u64 yes Zach Wegner https://www.chessprogramming.org/BMI2#PEXTBitboards
SISSY Bitboards 178.695824 180416 [1409kb] none no Michael Sherwin http://www.talkchess.com/forum3/viewtop ... =7&t=73083
Fancy Magic BB - Variable shift 362.512575 93376 [729kb] imul64 yes Pradu Kannan https://www.chessprogramming.org/Magic_Bitboards#Fancy

So it looks like that it is aproximately 16% faster than both BlackMagic and KGSSB. So Kindergarten of Black Magic Sissy Bitboards looks promising :D .
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: Devlog of Quixotic

Post by Mike Sherwin »

+1 8-)