Hi Mike,
Possible problem:
At depth 4 and above, Black doesn't recapture on a4 after the initial moves:
1.a3 a5 2.b3 a4 3.bxa4 d5
Oddly enough, I think 3...d5 is the expected move (!!) by your program at this time. Think about the move search priority. A capture, 3...A8A4, is given lower priority than a pawn push such as 3...D7D5. Therefore the move 3...D7D5 is searched before 3...A8A4. And guess what? They BOTH evaluate to equal material and a score of 0. Even at depth 4, Black can see that after most moves by White, that 4...Bd7 will restore material equality. Since 3...D7D5 found the score 0 first, it is the move played.
At depth 4, the game continues:
3...d5 4.e3 Bd7 5.c3 Bxa4 and material is back to even.
By the way, out of curiosity I gave the position after 3...d5 to Stockfish, and at depth 40 it thinks the position is 0.00. LOL!
I will keep looking into why material balance was never restored at depths above 4, but I might not be surprised if it is working as it should, but just got caught in a short horizon effect problem "thinking" it could recapture the pawn but then a few moves later discovering that it couldn't.
I think what is missed during the Qsearch is that after 3...d5 4. e3 Bd7 5. Nc3 that the pawn on a4 cannot now be captured because at the end of exchanges on a4, White has Bb5+ (not a capture) and it is White that comes out ahead by capturing the Rook on a4.
=====
I spent a lot of time looking for bugs in your move generation code and only found those that I already reported, so I agree with you that perft testing should be tried.
=====
One oddity I did discover while looking at the first problem -- the move priority for a pawn capture en passant is the same as a pawn push forward, and not the higher priority of a piece capturing a similar piece. It's probably not worth having special code for it, but something you might see in "move ordering".
Kind Regards,
Tommy
I don't want to give up
Moderators: hgm, Rebel, chrisw
-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
Hi Tommy,
I did not get to do any more work today. Had to spend most of the day in bed because of a fibromyalgia attack. Just one of my many health problems I have to live with. It has been going on for about 4 days now and today was the worst day. I'm hoping tomorrow I'll be able to get back to work!
Really great news your last post was. One probable problem I discovered, is that I forgot to initialize t->epbb[] to zeros. I'll do that first thing tomorrow. Also when I mentioned how much time 8 ply searches were taking I forgot that debug mode was really slow. Is it slower by up to a factor of 10? I don't remember but I will find out tomorrow. If it really is working the way it should then I am very excited because the statistical data collecting can be easily added and the statistical driven search can finally be demonstrated.
I posted about this a few times in the past. For those that have not read those post it is a repeat of an experiment I did ~30 years ago. I wrote a simple 32 bit assembly program that ran on an 80386. All it was was a material searcher that counted AB cutoffs for each side for each root move and subtracted one from the other (I may have tried a ratio also) to get a value to choose one best material root move over another. It did not castle or cep or promote so it technically lost most games because of that but mostly it held its own against CM5000 even gaining many winning positions. It opened with e2e4 ... f1c4 ... g1f3 when appropriate. It seemed to understand pawn structure and even king safety. It had to be pretty good to hold its own against CM5000! There are many more stats it can collect and weight during search like checks, checkmates, and null move failures among others. I really believe that it can open up a whole new area of investigation!
I'm off to bed again. See you tomorrow.
THANKS
Mike
I did not get to do any more work today. Had to spend most of the day in bed because of a fibromyalgia attack. Just one of my many health problems I have to live with. It has been going on for about 4 days now and today was the worst day. I'm hoping tomorrow I'll be able to get back to work!
Really great news your last post was. One probable problem I discovered, is that I forgot to initialize t->epbb[] to zeros. I'll do that first thing tomorrow. Also when I mentioned how much time 8 ply searches were taking I forgot that debug mode was really slow. Is it slower by up to a factor of 10? I don't remember but I will find out tomorrow. If it really is working the way it should then I am very excited because the statistical data collecting can be easily added and the statistical driven search can finally be demonstrated.
I posted about this a few times in the past. For those that have not read those post it is a repeat of an experiment I did ~30 years ago. I wrote a simple 32 bit assembly program that ran on an 80386. All it was was a material searcher that counted AB cutoffs for each side for each root move and subtracted one from the other (I may have tried a ratio also) to get a value to choose one best material root move over another. It did not castle or cep or promote so it technically lost most games because of that but mostly it held its own against CM5000 even gaining many winning positions. It opened with e2e4 ... f1c4 ... g1f3 when appropriate. It seemed to understand pawn structure and even king safety. It had to be pretty good to hold its own against CM5000! There are many more stats it can collect and weight during search like checks, checkmates, and null move failures among others. I really believe that it can open up a whole new area of investigation!
I'm off to bed again. See you tomorrow.
THANKS
Mike
-
TommyTC
- Posts: 38
- Joined: Thu Mar 30, 2017 8:52 am
Re: I don't want to give up
Hi Mike,
Just a few quick notes.
I tried depth 9, which was significantly more slow than depth 8, and the game started:
1.a3 a5 2.b3 a4 3.bxa4 Rxa4
So this leads credence to the idea that at depth 8 3...d5 was played because of a horizon effect.
Before perft testing, your code needs to handle checkmate (and probably stalemate too).
I use MSVC 2015. The Bricabrac debug version runs a lot slower than the release version, as I would expect.
I used the release version and I think it was depth = 8, and a long way into the game (R+P endgame?) the game crashed from what looked like a "normal" type position.
I've noticed at times that some moves are labelled as "illegal" that shouldn't be -- certainly not at the root. In one position, the first move searched (order = 0), showed "illegal" score. I suspect that someplace a move is being scored as "illegal" and is being compared to a score in the (-INF, +INF) range, and the "illegal" value is being assigned to a legal move. As I mentioned earlier, the values for INF, and ILLEGAL and using s32 for "score" might be the problem.
The "priority" scheme for selecting the order of moves to search seems to be really bad. Many times the best move isn't searched until 15 to 20 other moves have been searched first and this has to be slowing the search considerably.
Kind Regards,
Tommy
Just a few quick notes.
I tried depth 9, which was significantly more slow than depth 8, and the game started:
1.a3 a5 2.b3 a4 3.bxa4 Rxa4
So this leads credence to the idea that at depth 8 3...d5 was played because of a horizon effect.
Before perft testing, your code needs to handle checkmate (and probably stalemate too).
I use MSVC 2015. The Bricabrac debug version runs a lot slower than the release version, as I would expect.
I used the release version and I think it was depth = 8, and a long way into the game (R+P endgame?) the game crashed from what looked like a "normal" type position.
I've noticed at times that some moves are labelled as "illegal" that shouldn't be -- certainly not at the root. In one position, the first move searched (order = 0), showed "illegal" score. I suspect that someplace a move is being scored as "illegal" and is being compared to a score in the (-INF, +INF) range, and the "illegal" value is being assigned to a legal move. As I mentioned earlier, the values for INF, and ILLEGAL and using s32 for "score" might be the problem.
The "priority" scheme for selecting the order of moves to search seems to be really bad. Many times the best move isn't searched until 15 to 20 other moves have been searched first and this has to be slowing the search considerably.
Kind Regards,
Tommy
-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
Hi Tommy,TommyTC wrote: ↑Fri Sep 25, 2020 6:52 pm Hi Mike,
Just a few quick notes.
I tried depth 9, which was significantly more slow than depth 8, and the game started:
1.a3 a5 2.b3 a4 3.bxa4 Rxa4
So this leads credence to the idea that at depth 8 3...d5 was played because of a horizon effect.
Before perft testing, your code needs to handle checkmate (and probably stalemate too).
I use MSVC 2015. The Bricabrac debug version runs a lot slower than the release version, as I would expect.
I used the release version and I think it was depth = 8, and a long way into the game (R+P endgame?) the game crashed from what looked like a "normal" type position.
I've noticed at times that some moves are labelled as "illegal" that shouldn't be -- certainly not at the root. In one position, the first move searched (order = 0), showed "illegal" score. I suspect that someplace a move is being scored as "illegal" and is being compared to a score in the (-INF, +INF) range, and the "illegal" value is being assigned to a legal move. As I mentioned earlier, the values for INF, and ILLEGAL and using s32 for "score" might be the problem.
The "priority" scheme for selecting the order of moves to search seems to be really bad. Many times the best move isn't searched until 15 to 20 other moves have been searched first and this has to be slowing the search considerably.
Kind Regards,
Tommy
I liked your previous post a lot better, LOL. At least the start at depth 9 is promising! And I am feeling better today so I'm going to try to do some work starting with rethinking the INF and ILLEGAL values. Also your changes have been fully incorporated. Here is the current state of the engine.
THANKS
Mike
Code: Select all
// Bricabrac
// A chess engine by Michael J Sherwin
// TommyTC - Honorary co-author, chief problem solver and bug squisher
// Thanks too - Sven Schule, ...
//#include "stdafx.h" - file not found on my system
#include <intrin.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#define equates 1
#ifdef equates
typedef signed char s08;
typedef unsigned char u08;
typedef int s32;
typedef unsigned long u32;
typedef long long s64;
typedef unsigned long long u64;
constexpr auto one = 1ull;
constexpr auto INF = 0x7fff;
constexpr auto STOP = INF;
constexpr auto ColA = 0;
constexpr auto Row8 = 7;
constexpr auto ILLEGAL = 0xffff;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 2000;
constexpr auto Vq = 800;
constexpr auto Vn = 200;
constexpr auto Vr = 400;
constexpr auto Vb = 200;
constexpr auto WOCCS = 0x0000000000000060;
constexpr auto WOCCL = 0x000000000000000e;
constexpr auto BOCCS = 0x6000000000000000;
constexpr auto BOCCL = 0x0e00000000000000;
constexpr auto WATKS = 0x0000000000000070;
constexpr auto WATKL = 0x000000000000001c;
constexpr auto BATKS = 0x7000000000000000;
constexpr auto BATKL = 0x1c00000000000000;
enum { BLACK, WHITE };
enum { B, R, N, Q };
enum {
OO, WP, WN, WB, WR, WRC, WQ, WK, WC, BP, BN, BB, BR, BRC, BQ, BK, BC,
Wd, We, Wb, Wr, Wn, Wq, Bd, Be, Bb, Br, Bn, Bq, WS, WL, BS, BL
};
enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };
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 { EXIT, GETCMD, BRICABRAC, MOVE };
#endif
#define definitions 1
#ifdef definitions
struct Move {
s32 fs;
s32 ts;
s32 type;
s32 score;
s32 order;
s32 wstats;
s32 bstats;
s32 status;
};
struct Thread {
s32 wtm;
s32 ply;
s32 start;
s32 mat[2];
s32 board[64];
u64 piece[2];
u64 king[2];
u64 epbb[100];
s32 fifty[100];
Move move[10000];
};
#define wtm t->wtm
#define ply t->ply
#define fifty t->fifty
#define start t->start
#define mat t->mat
#define board t->board
#define piece t->piece
#define king t->king
#define epbb t->epbb
#define move t->move
#endif
#define variables 1
#ifdef variables
Thread thread;
Thread* t;
s32 bricabrac;
s32 gamePly;
s32 sd;
u64 wPawnMoves[64];
u64 wPawnCapts[64];
u64 bPawnMoves[64];
u64 bPawnCapts[64];
u64 knightMoves[64];
u64 kingMoves[64];
u64 qss[64][256][8];
u64 bob[64];
u64 rob[64];
u64 above[65];
u64 below[65];
Move gameMoves[1000];
s32 value[] = { OO, VP, VN, VB, VR, VR, VQ, VK, VK, VP, VN, VB, VR, VR, VQ, VK, VK,
Vb, Vr, Vn, Vq, Vb, Vr, Vn, Vq };
u08 startFen[] = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";
#endif
void PrintBoard(Thread* t) {
s32 x, y, sq, pce;
u08 fig[] = { ".PNBRRQKKpnbrrqkk" };
for (y = 7; y >= 0; y--) {
for (x = 0; x < 8; x++) {
sq = ((y << 3) + x);
pce = board[sq];
std::cout << " " << fig[pce];
}
std::cout << std::endl;
}
std::cout << std::endl;
}
s32 LoadFen(Thread* t, u08* f) {
s32 row, col, sq, fs, pce;
for (sq = A1; sq <= H8; sq++) board[sq] = OO;
col = ColA;
row = Row8;
fs = 56;
mat[WHITE] = OO;
mat[BLACK] = OO;
piece[WHITE] = OO;
piece[BLACK] = OO;
for (;; f++) {
if (*f == ' ') break;
switch (*f) {
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
col += *f - '0';
fs = (row * 8 + col) & 63;
continue;
case '/':
col = ColA;
row--;
fs = (row * 8 + col) & 63;
continue;
case 'P':
pce = WP;
mat[WHITE] += VP;
piece[WHITE] ^= one << fs;
break;
case 'N':
pce = WN;
mat[WHITE] += VN;
piece[WHITE] ^= one << fs;
break;
case 'B':
pce = WB;
mat[WHITE] += VB;
piece[WHITE] ^= one << fs;
break;
case 'R':
pce = WR;
mat[WHITE] += VR;
piece[WHITE] ^= one << fs;
break;
case 'Q':
pce = WQ;
mat[WHITE] += VQ;
piece[WHITE] ^= one << fs;
break;
case 'K':
pce = WK;
piece[WHITE] ^= one << fs;
king[WHITE] = one << fs;
break;
case 'p':
pce = BP;
mat[BLACK] += VP;
piece[BLACK] ^= one << fs;
break;
case 'n':
pce = BN;
mat[BLACK] += VN;
piece[BLACK] ^= one << fs;
break;
case 'b':
pce = BB;
mat[BLACK] += VB;
piece[BLACK] ^= one << fs;
break;
case 'r':
pce = BR;
mat[BLACK] += VR;
piece[BLACK] ^= one << fs;
break;
case 'q':
pce = BQ;
mat[BLACK] += VQ;
piece[BLACK] ^= one << fs;
break;
case 'k':
pce = BK;
piece[BLACK] ^= one << fs;
king[BLACK] = one << fs;
break;
default:
return false;
}
board[fs] = pce;
col++;
fs = (row * 8 + col) & 63;
}
f++;
switch (*f++) {
case 'w':
wtm = WHITE;
break;
case 'b':
wtm = BLACK;
break;
default:
return false;
}
if (*f++ != ' ') return false;
if (*f == '-') {
f++;
if (*f++ != ' ') return false;
}
else {
for (;;) {
if (*f == ' ') {
f++;
break;
}
switch (*f++) {
case 'K':
board[E1] = WC;
board[H1] = WRC;
break;
case 'Q':
board[E1] = WC;
board[A1] = WRC;
break;
case 'k':
board[E8] = BC;
board[H8] = BRC;
break;
case 'q':
board[E8] = BC;
board[A8] = BRC;
break;
default:
return false;
}
}
}
epbb[OO] = OO;
if (*f == '-') f++;
else {
if (*f < 'a' || *f > 'h') return false;
if (*(f + 1) < '0' || *(f + 1) > '7') return false;
row = *(f + 1) - '1';
col = *f - 'a';
epbb[OO] = one << (row * 8 + col);
f += 2;
}
if (*f++ != ' ') return false;
fifty[OO] = OO;
for (;;) {
if (!isdigit(*f)) break;
fifty[OO] *= 10;
fifty[OO] += *f++ - '0';
}
if (*f++ != ' ') return false;
start = 0;
for (;;) {
if (!isdigit(*f)) break;
start *= 10;
start += *f++ - '0';
}
if (start < 1) return false;
while (*f == ' ') f++;
if (*f != '\0') return false;
return true;
}
void MakeMove(Thread* t, Move* m) {
s32 ctype = 0, sq;
board[m->fs] = OO;
piece[wtm] ^= one << m->fs;
piece[wtm] ^= one << m->ts;
switch (m->type) {
case OO: break;
case WP:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WP;
break;
case WN:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WN;
break;
case WB:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WB;
break;
case WR:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WR;
break;
case WRC:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WR;
break;
case WQ:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WQ;
break;
case WK:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WK;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
break;
case WC:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WK;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
break;
case BP:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BP;
break;
case BN:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BN;
break;
case BB:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BB;
break;
case BR:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BR;
break;
case BRC:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BR;
break;
case BQ:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BQ;
break;
case BK:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BK;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
break;
case BC:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BK;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
break;
case Wd:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WP;
epbb[ply + 1] = (u64)(m->fs + 16 == m->ts) << (m->fs + 8);
break;
case We:
sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
ctype = board[sq];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << sq;
board[sq] = OO;
board[m->ts] = WP;
break;
case Wb:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WB;
mat[WHITE] += 200;
break;
case Wr:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WR;
mat[WHITE] += 400;
break;
case Wn:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WN;
mat[WHITE] += 200;
break;
case Wq:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WQ;
mat[WHITE] += 800;
break;
case Bd:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BP;
epbb[ply + 1] = (u64)(m->fs - 16 == m->ts) << (m->fs - 8);
break;
case Be:
sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
ctype = board[sq];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << sq;
board[sq] = OO;
board[m->ts] = BP;
break;
case Bb:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BB;
mat[BLACK] += 200;
break;
case Br:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BR;
mat[BLACK] += 400;
break;
case Bn:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BN;
mat[BLACK] += 200;
break;
case Bq:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BQ;
mat[BLACK] += 800;
break;
case WS:
ctype = OO;
board[G1] = WK;
board[H1] = OO;
board[F1] = WR;
king[WHITE] ^= one << E1;
king[WHITE] ^= one << G1;
piece[WHITE] ^= one << H1;
piece[WHITE] ^= one << F1;
break;
case WL:
ctype = OO;
board[C1] = WK;
board[A1] = OO;
board[D1] = WR;
king[WHITE] ^= one << E1;
king[WHITE] ^= one << C1;
piece[WHITE] ^= one << A1;
piece[WHITE] ^= one << D1;
break;
case BS:
ctype = OO;
board[G8] = BK;
board[H8] = OO;
board[F8] = BR;
king[BLACK] ^= one << E8;
king[BLACK] ^= one << G8;
piece[BLACK] ^= one << H8;
piece[BLACK] ^= one << F8;
break;
case BL:
ctype = OO;
board[C8] = BK;
board[A8] = OO;
board[D8] = BR;
king[BLACK] ^= one << E8;
king[BLACK] ^= one << C8;
piece[BLACK] ^= one << A8;
piece[BLACK] ^= one << D8;
break;
}
m->type |= ctype << 6;
wtm = 1 - wtm;
ply++;
}
void TakeBack(Thread* t, Move* m) {
s32 ctype, sq;
ply--;
wtm = 1 - wtm;
piece[wtm] ^= one << m->ts;
piece[wtm] ^= one << m->fs;
ctype = m->type >> 6;
mat[1 - wtm] += value[ctype];
m->type &= 0x3f;
switch (m->type) {
case OO: break;
case WP:
board[m->ts] = ctype;
board[m->fs] = WP;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WN:
board[m->ts] = ctype;
board[m->fs] = WN;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WB:
board[m->ts] = ctype;
board[m->fs] = WB;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WR:
board[m->ts] = ctype;
board[m->fs] = WR;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WRC:
board[m->ts] = ctype;
board[m->fs] = WRC;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WQ:
board[m->ts] = ctype;
board[m->fs] = WQ;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WK:
board[m->ts] = ctype;
board[m->fs] = WK;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WC:
board[m->ts] = ctype;
board[m->fs] = WC;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case BP:
board[m->ts] = ctype;
board[m->fs] = BP;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BN:
board[m->ts] = ctype;
board[m->fs] = BN;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BB:
board[m->ts] = ctype;
board[m->fs] = BB;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BR:
board[m->ts] = ctype;
board[m->fs] = BR;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BRC:
board[m->ts] = ctype;
board[m->fs] = BRC;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BQ:
board[m->ts] = ctype;
board[m->fs] = BQ;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BK:
board[m->ts] = ctype;
board[m->fs] = BK;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BC:
board[m->ts] = ctype;
board[m->fs] = BC;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Wd:
board[m->ts] = ctype;
board[m->fs] = WP;
epbb[ply + 1] = OO;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case We:
sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
board[m->ts] = OO;
board[sq] = ctype;
piece[BLACK] ^= (u64)(ctype != OO) << sq;
board[m->fs] = WP;
break;
case Wb:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 200;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Wr:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 400;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Wn:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 200;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Wq:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 800;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Bd:
board[m->ts] = ctype;
board[m->fs] = BP;
epbb[ply + 1] = OO;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Be:
sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
board[m->ts] = OO;
board[sq] = ctype;
piece[WHITE] ^= (u64)(ctype != OO) << sq;
board[m->fs] = BP;
break;
case Bb:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 200;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Br:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 400;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Bn:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 200;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Bq:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 800;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case WS:
board[G1] = OO;
board[E1] = WC;
board[H1] = WRC;
board[F1] = OO;
king[WHITE] ^= one << G1;
king[WHITE] ^= one << E1;
piece[WHITE] ^= one << H1;
piece[WHITE] ^= one << F1;
break;
case WL:
board[C1] = OO;
board[E1] = WC;
board[A1] = WRC;
board[D1] = OO;
king[WHITE] ^= one << C1;
king[WHITE] ^= one << E1;
piece[WHITE] ^= one << A1;
piece[WHITE] ^= one << D1;
break;
case BS:
board[G8] = OO;
board[E8] = BC;
board[H8] = BRC;
board[F8] = OO;
king[BLACK] ^= one << G8;
king[BLACK] ^= one << E8;
piece[BLACK] ^= one << H8;
piece[BLACK] ^= one << F8;
break;
case BL:
board[C8] = OO;
board[E8] = BC;
board[A8] = BRC;
board[D8] = OO;
king[BLACK] ^= one << C8;
king[BLACK] ^= one << E8;
piece[BLACK] ^= one << A8;
piece[BLACK] ^= one << D8;
break;
}
}
s32 AtkByWhite(Thread* t, u64 bb) {
u32 ts, fs;
u64 b, aPieces = piece[WHITE] | piece[BLACK];
do {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
b = bPawnCapts[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WP) return true;
}
b = knightMoves[ts] & piece[WHITE];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WN) return true;
}
b = kingMoves[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WK) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& bob[ts]
& piece[WHITE];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WB || board[fs] == WQ) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& rob[ts]
& piece[WHITE];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WR || board[fs] == WQ) return true;
}
} while (bb);
return false;
}
s32 AtkByBlack(Thread* t, u64 bb) {
u32 ts, fs;
u64 b, aPieces = piece[WHITE] | piece[BLACK];
do {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
b = wPawnCapts[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BP) return true;
}
b = knightMoves[ts] & piece[BLACK];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BN) return true;
}
b = kingMoves[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BK) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& bob[ts]
& piece[BLACK];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BB || board[fs] == BQ) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& rob[ts]
& piece[BLACK];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BR || board[fs] == BQ) return true;
}
} while (bb);
return false;
}
__forceinline s32 Sort(Thread* t, Move* m) {
s32 i, mi = 0, high = -INF;
Move* mov;
for (i = 0; (m + i)->status != STOP; i++) {
mov = m + i;
if (mov->status == false && mov->score > high) {
high = mov->score;
mi = i;
}
}
(m + mi)->status = true;
return mi;
}
__forceinline s32 Qsort(Thread* t, Move* m, s32 n) {
s32 i = 0, high = -INF;
Move* mov;
for (; n > OO; n--) {
mov = m - n;
if (!mov->status && mov->score > high) {
high = mov->score;
i = n;
}
}
(m - i)->status = true;
return i;
}
s32 Qsearch(Thread* t, Move* m, s32 alpha, s32 beta) {
s32 n, i, mi, type, score;
u32 fs, ts;
u64 bb, captures, pieces, aPieces, enemy, empty;
Move* mov;
score = mat[wtm] - mat[1 - wtm];
if (score >= beta) return beta;
if (score > alpha) alpha = score;
n = 0;
bb = 0;
captures = 0;
pieces = piece[wtm];
aPieces = piece[BLACK] | piece[WHITE];
enemy = aPieces ^ pieces;
empty = 0xffffffffffffffff ^ aPieces;
do {
_BitScanForward64(&fs, pieces);
pieces ^= one << fs;
type = board[fs];
switch (type) {
case OO: break;
case WP:
switch (fs >> 3) {
case RANK1: break;
case RANK2:
case RANK3:
case RANK4:
case RANK6:
bb = wPawnCapts[fs] & enemy;
break;
case RANK5:
bb = wPawnCapts[fs] & (enemy | epbb[ply]);
type = We;
break;
case RANK7:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Wb + i;
m->score = value[board[ts]] + value[m->type];
m->status = false;
m++;
}
n += 4;
}
continue;
}
break;
case WN:
case BN:
bb = knightMoves[fs] & enemy;
break;
case WB:
case BB:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& bob[fs]
& enemy;
break;
case WR:
case WRC:
case BR:
case BRC:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& rob[fs]
& enemy;
break;
case WQ:
case BQ:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& enemy;
break;
case WK:
case BK:
case WC:
case BC:
bb = kingMoves[fs] & enemy;
break;
case BP:
switch (fs >> 3) {
case RANK1:
break;
case RANK2:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Bb + i;
m->score = value[board[ts]] + value[m->type];
m->status = false;
m++;
}
n += 4;
}
continue;
case RANK3:
case RANK5:
case RANK6:
case RANK7:
bb = bPawnCapts[fs] & enemy;
break;
case RANK4:
bb = bPawnCapts[fs] & (enemy | epbb[ply]);
type = Be;
break;
}
break;
}
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = type;
m->score = value[board[ts]] - value[m->type];
m->status = false;
m++;
n++;
}
} while (pieces);
if (captures & king[1 - wtm]) return -ILLEGAL;
for (i = n; i > OO; i--) {
mi = Qsort(t, m, n);
mov = (m - mi);
MakeMove(t, mov);
mov->score = -Qsearch(t, m, -beta, -alpha);
TakeBack(t, mov);
if (mov->score == ILLEGAL) continue;
if (mov->score > alpha) {
if (mov->score >= beta) {
return beta;
}
alpha = mov->score;
}
}
return alpha;
}
u64 GenMoves(Thread* t, Move* m) {
s32 i, type, score = -INF;
u32 fs, ts, sq;
u64 bb = 0, captures = 0;
Move* n = m;
u64 pieces = piece[wtm];
u64 aPieces = piece[BLACK] | piece[WHITE];
u64 enemy = aPieces ^ pieces;
u64 empty = 0xffffffffffffffff ^ aPieces;
u64 notme = 0xffffffffffffffff ^ pieces;
do {
_BitScanForward64(&fs, pieces);
pieces ^= one << fs;
type = board[fs];
switch (type) {
case OO:
break;
case WP:
switch (fs >> 3) {
case RANK1: break;
case RANK2:
_BitScanForward64(&sq, wPawnMoves[fs] & aPieces);
bb = (wPawnMoves[fs] & below[sq]) | (wPawnCapts[fs] & enemy);
type = Wd;
break;
case RANK3:
case RANK4:
case RANK6:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
break;
case RANK5:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & (enemy | epbb[ply]));
type = We;
break;
case RANK7:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Wb + i;
m->score = value[board[m->ts]] - VP;
m->status = false;
m++;
}
}
continue;
}
break;
case WN:
case BN:
bb = knightMoves[fs] & notme;
break;
case WB:
case BB:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& bob[fs]
& notme;
break;
case WR:
case WRC:
case BR:
case BRC:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& rob[fs]
& notme;
break;
case WQ:
case BQ:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& notme;
break;
case WK:
case BK:
bb = kingMoves[fs] & notme;
break;
case WC:
bb = kingMoves[fs] & notme;
if (board[H1] == WRC && !(WOCCS & aPieces) && !AtkByBlack(t, WATKS)) {
m->fs = E1;
m->ts = G1;
m->type = WS;
m->score = 40;
m->status = false;
m++;
}
if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
m->fs = E1;
m->ts = C1;
m->type = WL;
m->score = 40;
m->status = false;
m++;
}
break;
case BP:
switch (fs >> 3) {
case RANK1:
break;
case RANK2:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Bb + i;
m->score = value[board[m->ts]] - VP;
m->status = false;
m++;
}
}
continue;
case RANK3:
case RANK5:
case RANK6:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
break;
case RANK4:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & (enemy | epbb[ply]));
type = Be;
break;
case RANK7:
_BitScanReverse64(&sq, bPawnMoves[fs] & aPieces);
bb = (bPawnMoves[fs] & above[sq]) | (bPawnCapts[fs] & enemy);
type = Bd;
break;
}
break;
case BC:
bb = kingMoves[fs] & notme;
if (board[H8] == BRC && !(BOCCS & aPieces) && !AtkByWhite(t, BATKS)) {
m->fs = E8;
m->ts = G8;
m->type = BS;
m->score = 40;
m->status = false;
m++;
}
if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
m->fs = E8;
m->ts = C8;
m->type = BL;
m->score = 40;
m->status = false;
m++;
}
break;
}
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = type;
m->score = value[board[m->ts]] - value[board[m->fs]];
m->status = false;
m++;
}
} while (pieces);
if (captures & king[1 - wtm]) return OO;
m->status = STOP;
m++;
return m - n;
}
s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
s32 i, mi;
u64 n;
Move* mov;
n = GenMoves(t, m);
if (!n) return -ILLEGAL;
depth--;
for (i = 0; (m + i)->status != STOP; i++) {
mi = Sort(t, m);
mov = m + mi;
#if TOMDEBUG > 0
mov->order = i;
#endif
MakeMove(t, mov);
#if TOMDEBUG == 0
PrintBoard(t);
#endif
if (!depth) {
mov->score = -Qsearch(t, m + n, -beta, -alpha);
}
else {
mov->score = -Search(t, m + n, -beta, -alpha, depth);
}
TakeBack(t, mov);
#if TOMDEBUG == 0
PrintBoard(t);
#endif
if (mov->score == ILLEGAL) continue;
if (mov->score >= beta) return beta;
#if TOMDEBUG == 0
if (mov->score > alpha) alpha = move->score;
#else
if (mov->score > alpha) alpha = mov->score;
#endif
}
return alpha;
}
void Bricabrac(Thread* t) {
Search(t, &move[0], -INF, INF, sd);
bricabrac = MOVE;
}
void GetCmd(Thread* t) {
s32 match, i, fs, ts;
u64 n;
char data[256], mvstr[20];
match = false;
PrintBoard(t);
fgets(data, 256, stdin);
_strlwr_s(data);
std::cout << std::endl;
if (data[0] >= 'a' && data[0] <= 'h' &&
data[1] >= '1' && data[1] <= '8' &&
data[2] >= 'a' && data[2] <= 'h' &&
data[3] >= '1' && data[3] <= '8') {
n = GenMoves(t, &move[0]);
for (i = OO; i < n; i++) {
fs = move[i].fs;
ts = move[i].ts;
sprintf_s(mvstr, 20, "%c%d%c%d\n", (fs & 7) + 'a', (fs >> 3) + 1, (ts & 7) + 'a', (ts >> 3) + 1);
if (!strcmp(data, mvstr)) {
gameMoves[gamePly].fs = fs;
gameMoves[gamePly].ts = ts;
gameMoves[gamePly].type = move[i].type;
MakeMove(t, &gameMoves[gamePly]);
gamePly++;
ply--;
return;
}
}
return;
}
if (!strcmp(data, "go\n")) {
bricabrac = BRICABRAC;
return;
}
if (!strcmp(data, "u\n") || !strcmp(data, "undo\n")) {
gamePly--;
ply++;
TakeBack(t, &gameMoves[gamePly]);
return;
}
}
void DoMove(Thread* t) {
s32 i, j = 0, score;
s32 PrevSearchOrder = 1000;
score = -INF;
for (i = 0; move[i].status != STOP; i++) {
printf("%i: ", i);
printf("%c%c", 'A' + (move[i].fs & 7), '1' + (move[i].fs >> 3));
printf("%c%c", 'A' + (move[i].ts & 7), '1' + (move[i].ts >> 3));
printf(" Score: %i ", move[i].score);
printf("order: %i\n", move[i].order);
if (move[i].score > score) {
score = move[i].score;
PrevSearchOrder = move[i].order;
j = i;
} else
if ((move[i].score == score)
&& (move[i].order < PrevSearchOrder)) {
PrevSearchOrder = move[i].order;
j = i;
}
if ((move[i].score != ILLEGAL)
&& (move[i].score > score)) {
score = move[i].score;
PrevSearchOrder = move[i].order;
j = i;
} else
if ((move[i].score != ILLEGAL)
&& (move[i].score == score)
&& (move[i].order < PrevSearchOrder)) {
PrevSearchOrder = move[i].order;
j = i;
}
}
printf("\nMove Played: ");
printf("%c%c", 'A' + (move[j].fs & 7), '1' + (move[j].fs >> 3));
printf("%c%c\n", 'A' + (move[j].ts & 7), '1' + (move[j].ts >> 3));
gameMoves[gamePly].fs = move[j].fs;
gameMoves[gamePly].ts = move[j].ts;
gameMoves[gamePly].type = move[j].type;
MakeMove(t, &gameMoves[gamePly]);
ply--;
gamePly++;
bricabrac = GETCMD;
}
void InitializeQSS() {
u08 sq, sqr, k, l;
s08 x, y, dx, dy;
s32 i;
u64 b, bb;
for (sq = 0; sq < 64; sq++) {
y = sq >> 3;
x = sq & 7;
bob[sq] = 0;
rob[sq] = 0;
for (i = 0; i < 256; i++) {
for (k = 0, l = 0; k <= 56; k += 8, l++) {
bb = 0;
b = (u64)i << k;
for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1; x + dx > -1; dx--) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1; x + dx < +8; dx++) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = +1; y + dy < +8; dy++) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = -1; y + dy > -1; dy--) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
qss[sq][i][l] = bb;
}
}
}
}
void InitializeRNK() {
u08 sq, sqr, i;
s08 x, y, dx, dy;
u64 bb, b;
for (sq = 0; sq < 64; sq++) {
y = sq >> 3;
x = sq & 7;
for (i = 0; i < 128; i++) {
bb = 0;
b = (u64)i << (sq & 56);
for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1; x + dx > -1; dx--) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1; x + dx < +8; dx++) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = +1; y + dy < +8; dy++) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = -1; y + dy > -1; dy--) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
qss[sq][i][0] = bb;
}
}
}
void InitPieceBB() {
s32 sq, x, y;
above[0] = 0xffffffffffffffff;
below[0] = 0xffffffffffffffff;
for (sq = A1; sq <= H8; sq++) {
x = sq & 7;
y = sq >> 3;
above[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) ^ 1) << (sq + 1);
below[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) << (sq + 1)) ^ 0xffffffffffffffff;
wPawnMoves[sq] = 0;
wPawnCapts[sq] = 0;
bPawnMoves[sq] = 0;
bPawnCapts[sq] = 0;
if (sq > H1 && sq < A8) {
// White Pawn Moves
wPawnMoves[sq] |= one << (sq + 8);
if (sq < A3) wPawnMoves[sq] |= one << (sq + 16);
// White Pawn Captures
if (x + 1 < +8) wPawnCapts[sq] |= one << (sq + 9);
if (x - 1 > -1) wPawnCapts[sq] |= one << (sq + 7);
// Black Pawn Moves
bPawnMoves[sq] |= one << (sq - 8);
if (sq > H6) bPawnMoves[sq] |= one << (sq - 16);
// Black Pawn Captures
if (x + 1 < +8) bPawnCapts[sq] |= one << (sq - 7);
if (x - 1 > -1) bPawnCapts[sq] |= one << (sq - 9);
}
// Knight Moves
knightMoves[sq] = 0;
if (y + 2 < +8 && x + 1 < +8) knightMoves[sq] |= one << (sq + 17);
if (y + 1 < +8 && x + 2 < +8) knightMoves[sq] |= one << (sq + 10);
if (y - 1 > -1 && x + 2 < +8) knightMoves[sq] |= one << (sq - +6);
if (y - 2 > -1 && x + 1 < +8) knightMoves[sq] |= one << (sq - 15);
if (y - 2 > -1 && x - 1 > -1) knightMoves[sq] |= one << (sq - 17);
if (y - 1 > -1 && x - 2 > -1) knightMoves[sq] |= one << (sq - 10);
if (y + 1 < +8 && x - 2 > -1) knightMoves[sq] |= one << (sq + +6);
if (y + 2 < +8 && x - 1 > -1) knightMoves[sq] |= one << (sq + 15);
// King Moves
kingMoves[sq] = 0;
if (y + 1 < +8) kingMoves[sq] |= one << (sq + 8);
if (y - 1 > -1) kingMoves[sq] |= one << (sq - 8);
if (x + 1 < +8) kingMoves[sq] |= one << (sq + 1);
if (x - 1 > -1) kingMoves[sq] |= one << (sq - 1);
if (y + 1 < +8 && x + 1 < +8) kingMoves[sq] |= one << (sq + 9);
if (y - 1 > -1 && x + 1 < +8) kingMoves[sq] |= one << (sq - 7);
if (y - 1 > -1 && x - 1 > -1) kingMoves[sq] |= one << (sq - 9);
if (y + 1 < +8 && x - 1 > -1) kingMoves[sq] |= one << (sq + 7);
}
InitializeQSS();
InitializeRNK();
}
void NewGame(Thread* t) {
s32 i;
LoadFen(t, startFen);
for (i = 0; i < 100; i++) epbb[i] = OO;
}
void Initialize() {
bricabrac = GETCMD;
gamePly = OO;
wtm = WHITE;
ply = OO;
InitPieceBB();
NewGame(t);
}
void SetSearchDepth()
{
char data[256];
int x = 0;
printf("Enter SEARCH DEPTH (sd): \n");
fgets(data, 4, stdin);
while ((data[x] >= '0') && (data[x] <= '9')) {
sd = 10 * sd + (data[x++] - '0');
}
}
s32 main() {
SetSearchDepth();
t = &thread;
Initialize();
do {
if (bricabrac == BRICABRAC) Bricabrac(t);
if (bricabrac == MOVE) DoMove(t);
GetCmd(t);
} while (bricabrac);
return 0;
}-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
Just some very quick changes. I understood the problem with ILLEGAL being 0xffff used with an s32 so I changed ILLEGAL to 0x8000 one more than INF (0x7fff). And I changed the move order formula from m->score = value[board[m->ts]] - value[board[m->fs]]; to m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];. Any suggestions here are welcome.
It takes noticeably less time at sd = 8. And the rook takes the pawn after a2a3, a7a5, b2b3, a5a4, b3a4, a8a4. Don't know if the change to 0x8000 solves all the other issues. Going to start more in depth testing!
It takes noticeably less time at sd = 8. And the rook takes the pawn after a2a3, a7a5, b2b3, a5a4, b3a4, a8a4. Don't know if the change to 0x8000 solves all the other issues. Going to start more in depth testing!
Code: Select all
// Bricabrac
// A chess engine by Michael J Sherwin
// TommyTC - Honorary co-author, chief problem solver and bug squisher
// Thanks too - Sven Shule, ...
//#include "stdafx.h" - file not found on my system
#include <intrin.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#define equates 1
#ifdef equates
typedef signed char s08;
typedef unsigned char u08;
typedef int s32;
typedef unsigned long u32;
typedef long long s64;
typedef unsigned long long u64;
constexpr auto one = 1ull;
constexpr auto INF = 0x7fff;
constexpr auto STOP = INF;
constexpr auto ColA = 0;
constexpr auto Row8 = 7;
constexpr auto ILLEGAL = 0x8000;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 2000;
constexpr auto Vq = 800;
constexpr auto Vn = 200;
constexpr auto Vr = 400;
constexpr auto Vb = 200;
constexpr auto WOCCS = 0x0000000000000060;
constexpr auto WOCCL = 0x000000000000000e;
constexpr auto BOCCS = 0x6000000000000000;
constexpr auto BOCCL = 0x0e00000000000000;
constexpr auto WATKS = 0x0000000000000070;
constexpr auto WATKL = 0x000000000000001c;
constexpr auto BATKS = 0x7000000000000000;
constexpr auto BATKL = 0x1c00000000000000;
enum { BLACK, WHITE };
enum { B, R, N, Q };
enum {
OO, WP, WN, WB, WR, WRC, WQ, WK, WC, BP, BN, BB, BR, BRC, BQ, BK, BC,
Wd, We, Wb, Wr, Wn, Wq, Bd, Be, Bb, Br, Bn, Bq, WS, WL, BS, BL
};
enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };
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 { EXIT, GETCMD, BRICABRAC, MOVE };
#endif
#define definitions 1
#ifdef definitions
struct Move {
s32 fs;
s32 ts;
s32 type;
s32 score;
s32 order;
s32 wstats;
s32 bstats;
s32 status;
};
struct Thread {
s32 wtm;
s32 ply;
s32 start;
s32 mat[2];
s32 board[64];
u64 piece[2];
u64 king[2];
u64 epbb[100];
s32 fifty[100];
Move move[10000];
};
#define wtm t->wtm
#define ply t->ply
#define fifty t->fifty
#define start t->start
#define mat t->mat
#define board t->board
#define piece t->piece
#define king t->king
#define epbb t->epbb
#define move t->move
#endif
#define variables 1
#ifdef variables
Thread thread;
Thread* t;
s32 bricabrac;
s32 gamePly;
s32 sd;
u64 wPawnMoves[64];
u64 wPawnCapts[64];
u64 bPawnMoves[64];
u64 bPawnCapts[64];
u64 knightMoves[64];
u64 kingMoves[64];
u64 qss[64][256][8];
u64 bob[64];
u64 rob[64];
u64 above[65];
u64 below[65];
Move gameMoves[1000];
s32 value[] = { OO, VP, VN, VB, VR, VR, VQ, VK, VK, VP, VN, VB, VR, VR, VQ, VK, VK,
Vb, Vr, Vn, Vq, Vb, Vr, Vn, Vq };
u08 startFen[] = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";
#endif
void PrintBoard(Thread* t) {
s32 x, y, sq, pce;
u08 fig[] = { ".PNBRRQKKpnbrrqkk" };
for (y = 7; y >= 0; y--) {
for (x = 0; x < 8; x++) {
sq = ((y << 3) + x);
pce = board[sq];
std::cout << " " << fig[pce];
}
std::cout << std::endl;
}
std::cout << std::endl;
}
s32 LoadFen(Thread* t, u08* f) {
s32 row, col, sq, fs, pce;
for (sq = A1; sq <= H8; sq++) board[sq] = OO;
col = ColA;
row = Row8;
fs = 56;
mat[WHITE] = OO;
mat[BLACK] = OO;
piece[WHITE] = OO;
piece[BLACK] = OO;
for (;; f++) {
if (*f == ' ') break;
switch (*f) {
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
col += *f - '0';
fs = (row * 8 + col) & 63;
continue;
case '/':
col = ColA;
row--;
fs = (row * 8 + col) & 63;
continue;
case 'P':
pce = WP;
mat[WHITE] += VP;
piece[WHITE] ^= one << fs;
break;
case 'N':
pce = WN;
mat[WHITE] += VN;
piece[WHITE] ^= one << fs;
break;
case 'B':
pce = WB;
mat[WHITE] += VB;
piece[WHITE] ^= one << fs;
break;
case 'R':
pce = WR;
mat[WHITE] += VR;
piece[WHITE] ^= one << fs;
break;
case 'Q':
pce = WQ;
mat[WHITE] += VQ;
piece[WHITE] ^= one << fs;
break;
case 'K':
pce = WK;
piece[WHITE] ^= one << fs;
king[WHITE] = one << fs;
break;
case 'p':
pce = BP;
mat[BLACK] += VP;
piece[BLACK] ^= one << fs;
break;
case 'n':
pce = BN;
mat[BLACK] += VN;
piece[BLACK] ^= one << fs;
break;
case 'b':
pce = BB;
mat[BLACK] += VB;
piece[BLACK] ^= one << fs;
break;
case 'r':
pce = BR;
mat[BLACK] += VR;
piece[BLACK] ^= one << fs;
break;
case 'q':
pce = BQ;
mat[BLACK] += VQ;
piece[BLACK] ^= one << fs;
break;
case 'k':
pce = BK;
piece[BLACK] ^= one << fs;
king[BLACK] = one << fs;
break;
default:
return false;
}
board[fs] = pce;
col++;
fs = (row * 8 + col) & 63;
}
f++;
switch (*f++) {
case 'w':
wtm = WHITE;
break;
case 'b':
wtm = BLACK;
break;
default:
return false;
}
if (*f++ != ' ') return false;
if (*f == '-') {
f++;
if (*f++ != ' ') return false;
}
else {
for (;;) {
if (*f == ' ') {
f++;
break;
}
switch (*f++) {
case 'K':
board[E1] = WC;
board[H1] = WRC;
break;
case 'Q':
board[E1] = WC;
board[A1] = WRC;
break;
case 'k':
board[E8] = BC;
board[H8] = BRC;
break;
case 'q':
board[E8] = BC;
board[A8] = BRC;
break;
default:
return false;
}
}
}
epbb[OO] = OO;
if (*f == '-') f++;
else {
if (*f < 'a' || *f > 'h') return false;
if (*(f + 1) < '0' || *(f + 1) > '7') return false;
row = *(f + 1) - '1';
col = *f - 'a';
epbb[OO] = one << (row * 8 + col);
f += 2;
}
if (*f++ != ' ') return false;
fifty[OO] = OO;
for (;;) {
if (!isdigit(*f)) break;
fifty[OO] *= 10;
fifty[OO] += *f++ - '0';
}
if (*f++ != ' ') return false;
start = 0;
for (;;) {
if (!isdigit(*f)) break;
start *= 10;
start += *f++ - '0';
}
if (start < 1) return false;
while (*f == ' ') f++;
if (*f != '\0') return false;
return true;
}
void MakeMove(Thread* t, Move* m) {
s32 ctype = 0, sq;
board[m->fs] = OO;
piece[wtm] ^= one << m->fs;
piece[wtm] ^= one << m->ts;
switch (m->type) {
case OO: break;
case WP:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WP;
break;
case WN:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WN;
break;
case WB:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WB;
break;
case WR:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WR;
break;
case WRC:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WR;
break;
case WQ:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WQ;
break;
case WK:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WK;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
break;
case WC:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WK;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
break;
case BP:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BP;
break;
case BN:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BN;
break;
case BB:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BB;
break;
case BR:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BR;
break;
case BRC:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BR;
break;
case BQ:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BQ;
break;
case BK:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BK;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
break;
case BC:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BK;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
break;
case Wd:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WP;
epbb[ply + 1] = (u64)(m->fs + 16 == m->ts) << (m->fs + 8);
break;
case We:
sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
ctype = board[sq];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << sq;
board[sq] = OO;
board[m->ts] = WP;
break;
case Wb:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WB;
mat[WHITE] += 200;
break;
case Wr:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WR;
mat[WHITE] += 400;
break;
case Wn:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WN;
mat[WHITE] += 200;
break;
case Wq:
ctype = board[m->ts];
mat[BLACK] -= value[ctype];
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = WQ;
mat[WHITE] += 800;
break;
case Bd:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BP;
epbb[ply + 1] = (u64)(m->fs - 16 == m->ts) << (m->fs - 8);
break;
case Be:
sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
ctype = board[sq];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << sq;
board[sq] = OO;
board[m->ts] = BP;
break;
case Bb:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BB;
mat[BLACK] += 200;
break;
case Br:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BR;
mat[BLACK] += 400;
break;
case Bn:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BN;
mat[BLACK] += 200;
break;
case Bq:
ctype = board[m->ts];
mat[WHITE] -= value[ctype];
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
board[m->ts] = BQ;
mat[BLACK] += 800;
break;
case WS:
ctype = OO;
board[G1] = WK;
board[H1] = OO;
board[F1] = WR;
king[WHITE] ^= one << E1;
king[WHITE] ^= one << G1;
piece[WHITE] ^= one << H1;
piece[WHITE] ^= one << F1;
break;
case WL:
ctype = OO;
board[C1] = WK;
board[A1] = OO;
board[D1] = WR;
king[WHITE] ^= one << E1;
king[WHITE] ^= one << C1;
piece[WHITE] ^= one << A1;
piece[WHITE] ^= one << D1;
break;
case BS:
ctype = OO;
board[G8] = BK;
board[H8] = OO;
board[F8] = BR;
king[BLACK] ^= one << E8;
king[BLACK] ^= one << G8;
piece[BLACK] ^= one << H8;
piece[BLACK] ^= one << F8;
break;
case BL:
ctype = OO;
board[C8] = BK;
board[A8] = OO;
board[D8] = BR;
king[BLACK] ^= one << E8;
king[BLACK] ^= one << C8;
piece[BLACK] ^= one << A8;
piece[BLACK] ^= one << D8;
break;
}
m->type |= ctype << 6;
wtm = 1 - wtm;
ply++;
}
void TakeBack(Thread* t, Move* m) {
s32 ctype, sq;
ply--;
wtm = 1 - wtm;
piece[wtm] ^= one << m->ts;
piece[wtm] ^= one << m->fs;
ctype = m->type >> 6;
mat[1 - wtm] += value[ctype];
m->type &= 0x3f;
switch (m->type) {
case OO: break;
case WP:
board[m->ts] = ctype;
board[m->fs] = WP;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WN:
board[m->ts] = ctype;
board[m->fs] = WN;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WB:
board[m->ts] = ctype;
board[m->fs] = WB;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WR:
board[m->ts] = ctype;
board[m->fs] = WR;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WRC:
board[m->ts] = ctype;
board[m->fs] = WRC;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WQ:
board[m->ts] = ctype;
board[m->fs] = WQ;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WK:
board[m->ts] = ctype;
board[m->fs] = WK;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case WC:
board[m->ts] = ctype;
board[m->fs] = WC;
king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case BP:
board[m->ts] = ctype;
board[m->fs] = BP;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BN:
board[m->ts] = ctype;
board[m->fs] = BN;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BB:
board[m->ts] = ctype;
board[m->fs] = BB;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BR:
board[m->ts] = ctype;
board[m->fs] = BR;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BRC:
board[m->ts] = ctype;
board[m->fs] = BRC;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BQ:
board[m->ts] = ctype;
board[m->fs] = BQ;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BK:
board[m->ts] = ctype;
board[m->fs] = BK;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case BC:
board[m->ts] = ctype;
board[m->fs] = BC;
king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Wd:
board[m->ts] = ctype;
board[m->fs] = WP;
epbb[ply + 1] = OO;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case We:
sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
board[m->ts] = OO;
board[sq] = ctype;
piece[BLACK] ^= (u64)(ctype != OO) << sq;
board[m->fs] = WP;
break;
case Wb:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 200;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Wr:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 400;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Wn:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 200;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Wq:
board[m->ts] = ctype;
board[m->fs] = WP;
mat[WHITE] -= 800;
piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
break;
case Bd:
board[m->ts] = ctype;
board[m->fs] = BP;
epbb[ply + 1] = OO;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Be:
sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
board[m->ts] = OO;
board[sq] = ctype;
piece[WHITE] ^= (u64)(ctype != OO) << sq;
board[m->fs] = BP;
break;
case Bb:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 200;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Br:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 400;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Bn:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 200;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case Bq:
board[m->ts] = ctype;
board[m->fs] = BP;
mat[BLACK] -= 800;
piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
break;
case WS:
board[G1] = OO;
board[E1] = WC;
board[H1] = WRC;
board[F1] = OO;
king[WHITE] ^= one << G1;
king[WHITE] ^= one << E1;
piece[WHITE] ^= one << H1;
piece[WHITE] ^= one << F1;
break;
case WL:
board[C1] = OO;
board[E1] = WC;
board[A1] = WRC;
board[D1] = OO;
king[WHITE] ^= one << C1;
king[WHITE] ^= one << E1;
piece[WHITE] ^= one << A1;
piece[WHITE] ^= one << D1;
break;
case BS:
board[G8] = OO;
board[E8] = BC;
board[H8] = BRC;
board[F8] = OO;
king[BLACK] ^= one << G8;
king[BLACK] ^= one << E8;
piece[BLACK] ^= one << H8;
piece[BLACK] ^= one << F8;
break;
case BL:
board[C8] = OO;
board[E8] = BC;
board[A8] = BRC;
board[D8] = OO;
king[BLACK] ^= one << C8;
king[BLACK] ^= one << E8;
piece[BLACK] ^= one << A8;
piece[BLACK] ^= one << D8;
break;
}
}
s32 AtkByWhite(Thread* t, u64 bb) {
u32 ts, fs;
u64 b, aPieces = piece[WHITE] | piece[BLACK];
do {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
b = bPawnCapts[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WP) return true;
}
b = knightMoves[ts] & piece[WHITE];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WN) return true;
}
b = kingMoves[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WK) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& bob[ts]
& piece[WHITE];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WB || board[fs] == WQ) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& rob[ts]
& piece[WHITE];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == WR || board[fs] == WQ) return true;
}
} while (bb);
return false;
}
s32 AtkByBlack(Thread* t, u64 bb) {
u32 ts, fs;
u64 b, aPieces = piece[WHITE] | piece[BLACK];
do {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
b = wPawnCapts[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BP) return true;
}
b = knightMoves[ts] & piece[BLACK];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BN) return true;
}
b = kingMoves[ts];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BK) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& bob[ts]
& piece[BLACK];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BB || board[fs] == BQ) return true;
}
b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
& qss[ts][(aPieces >> 8) & 255][1]
& qss[ts][(aPieces >> 16) & 255][2]
& qss[ts][(aPieces >> 24) & 255][3]
& qss[ts][(aPieces >> 32) & 255][4]
& qss[ts][(aPieces >> 40) & 255][5]
& qss[ts][(aPieces >> 48) & 255][6]
& rob[ts]
& piece[BLACK];
while (b) {
_BitScanForward64(&fs, b);
b ^= one << fs;
if (board[fs] == BR || board[fs] == BQ) return true;
}
} while (bb);
return false;
}
__forceinline s32 Sort(Thread* t, Move* m) {
s32 i, mi = 0, high = -INF;
Move* mov;
for (i = 0; (m + i)->status != STOP; i++) {
mov = m + i;
if (mov->status == false && mov->score > high) {
high = mov->score;
mi = i;
}
}
(m + mi)->status = true;
return mi;
}
__forceinline s32 Qsort(Thread* t, Move* m, s32 n) {
s32 i = 0, high = -INF;
Move* mov;
for (; n > OO; n--) {
mov = m - n;
if (!mov->status && mov->score > high) {
high = mov->score;
i = n;
}
}
(m - i)->status = true;
return i;
}
s32 Qsearch(Thread* t, Move* m, s32 alpha, s32 beta) {
s32 n, i, mi, type, score;
u32 fs, ts;
u64 bb, captures, pieces, aPieces, enemy, empty;
Move* mov;
score = mat[wtm] - mat[1 - wtm];
if (score >= beta) return beta;
if (score > alpha) alpha = score;
n = 0;
bb = 0;
captures = 0;
pieces = piece[wtm];
aPieces = piece[BLACK] | piece[WHITE];
enemy = aPieces ^ pieces;
empty = 0xffffffffffffffff ^ aPieces;
do {
_BitScanForward64(&fs, pieces);
pieces ^= one << fs;
type = board[fs];
switch (type) {
case OO: break;
case WP:
switch (fs >> 3) {
case RANK1: break;
case RANK2:
case RANK3:
case RANK4:
case RANK6:
bb = wPawnCapts[fs] & enemy;
break;
case RANK5:
bb = wPawnCapts[fs] & (enemy | epbb[ply]);
type = We;
break;
case RANK7:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Wb + i;
m->score = value[board[ts]] + value[m->type];
m->status = false;
m++;
}
n += 4;
}
continue;
}
break;
case WN:
case BN:
bb = knightMoves[fs] & enemy;
break;
case WB:
case BB:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& bob[fs]
& enemy;
break;
case WR:
case WRC:
case BR:
case BRC:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& rob[fs]
& enemy;
break;
case WQ:
case BQ:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& enemy;
break;
case WK:
case BK:
case WC:
case BC:
bb = kingMoves[fs] & enemy;
break;
case BP:
switch (fs >> 3) {
case RANK1:
break;
case RANK2:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Bb + i;
m->score = value[board[ts]] + value[m->type];
m->status = false;
m++;
}
n += 4;
}
continue;
case RANK3:
case RANK5:
case RANK6:
case RANK7:
bb = bPawnCapts[fs] & enemy;
break;
case RANK4:
bb = bPawnCapts[fs] & (enemy | epbb[ply]);
type = Be;
break;
}
break;
}
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = type;
m->score = (value[board[ts]] << 4) - value[m->type];
m->status = false;
m++;
n++;
}
} while (pieces);
if (captures & king[1 - wtm]) return -ILLEGAL;
for (i = n; i > OO; i--) {
mi = Qsort(t, m, n);
mov = (m - mi);
MakeMove(t, mov);
mov->score = -Qsearch(t, m, -beta, -alpha);
TakeBack(t, mov);
if (mov->score == ILLEGAL) continue;
if (mov->score > alpha) {
if (mov->score >= beta) {
return beta;
}
alpha = mov->score;
}
}
return alpha;
}
u64 GenMoves(Thread* t, Move* m) {
s32 i, type, score = -INF;
u32 fs, ts, sq;
u64 bb = 0, captures = 0;
Move* n = m;
u64 pieces = piece[wtm];
u64 aPieces = piece[BLACK] | piece[WHITE];
u64 enemy = aPieces ^ pieces;
u64 empty = 0xffffffffffffffff ^ aPieces;
u64 notme = 0xffffffffffffffff ^ pieces;
do {
_BitScanForward64(&fs, pieces);
pieces ^= one << fs;
type = board[fs];
switch (type) {
case OO:
break;
case WP:
switch (fs >> 3) {
case RANK1: break;
case RANK2:
_BitScanForward64(&sq, wPawnMoves[fs] & aPieces);
bb = (wPawnMoves[fs] & below[sq]) | (wPawnCapts[fs] & enemy);
type = Wd;
break;
case RANK3:
case RANK4:
case RANK6:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
break;
case RANK5:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & (enemy | epbb[ply]));
type = We;
break;
case RANK7:
bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Wb + i;
m->score = value[board[m->ts]] - VP;
m->status = false;
m++;
}
}
continue;
}
break;
case WN:
case BN:
bb = knightMoves[fs] & notme;
break;
case WB:
case BB:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& bob[fs]
& notme;
break;
case WR:
case WRC:
case BR:
case BRC:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& rob[fs]
& notme;
break;
case WQ:
case BQ:
bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
& qss[fs][(aPieces >> 8) & 255][1]
& qss[fs][(aPieces >> 16) & 255][2]
& qss[fs][(aPieces >> 24) & 255][3]
& qss[fs][(aPieces >> 32) & 255][4]
& qss[fs][(aPieces >> 40) & 255][5]
& qss[fs][(aPieces >> 48) & 255][6]
& notme;
break;
case WK:
case BK:
bb = kingMoves[fs] & notme;
break;
case WC:
bb = kingMoves[fs] & notme;
if (board[H1] == WRC && !(WOCCS & aPieces) && !AtkByBlack(t, WATKS)) {
m->fs = E1;
m->ts = G1;
m->type = WS;
m->score = 40;
m->status = false;
m++;
}
if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
m->fs = E1;
m->ts = C1;
m->type = WL;
m->score = 40;
m->status = false;
m++;
}
break;
case BP:
switch (fs >> 3) {
case RANK1:
break;
case RANK2:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
for (i = Q; i >= B; i--) {
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = Bb + i;
m->score = value[board[m->ts]] - VP;
m->status = false;
m++;
}
}
continue;
case RANK3:
case RANK5:
case RANK6:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
break;
case RANK4:
bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & (enemy | epbb[ply]));
type = Be;
break;
case RANK7:
_BitScanReverse64(&sq, bPawnMoves[fs] & aPieces);
bb = (bPawnMoves[fs] & above[sq]) | (bPawnCapts[fs] & enemy);
type = Bd;
break;
}
break;
case BC:
bb = kingMoves[fs] & notme;
if (board[H8] == BRC && !(BOCCS & aPieces) && !AtkByWhite(t, BATKS)) {
m->fs = E8;
m->ts = G8;
m->type = BS;
m->score = 40;
m->status = false;
m++;
}
if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
m->fs = E8;
m->ts = C8;
m->type = BL;
m->score = 40;
m->status = false;
m++;
}
break;
}
captures |= bb;
while (bb) {
_BitScanForward64(&ts, bb);
bb ^= one << ts;
m->fs = (s32)fs;
m->ts = (s32)ts;
m->type = type;
m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];
m->status = false;
m++;
}
} while (pieces);
if (captures & king[1 - wtm]) return OO;
m->status = STOP;
m++;
return m - n;
}
s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
s32 i, mi;
u64 n;
Move* mov;
n = GenMoves(t, m);
if (!n) return -ILLEGAL;
depth--;
for (i = 0; (m + i)->status != STOP; i++) {
mi = Sort(t, m);
mov = m + mi;
#if TOMDEBUG > 0
mov->order = i;
#endif
MakeMove(t, mov);
#if TOMDEBUG == 0
PrintBoard(t);
#endif
if (!depth) {
mov->score = -Qsearch(t, m + n, -beta, -alpha);
}
else {
mov->score = -Search(t, m + n, -beta, -alpha, depth);
}
TakeBack(t, mov);
if (mov->score == ILLEGAL) continue;
if (mov->score >= beta) return beta;
#if TOMDEBUG == 0
if (mov->score > alpha) alpha = move->score;
#else
if (mov->score > alpha) alpha = mov->score;
#endif
}
return alpha;
}
void Bricabrac(Thread* t) {
Search(t, &move[0], -INF, INF, sd);
bricabrac = MOVE;
}
void GetCmd(Thread* t) {
s32 match, i, fs, ts;
u64 n;
char data[256], mvstr[20];
match = false;
PrintBoard(t);
fgets(data, 256, stdin);
_strlwr_s(data);
std::cout << std::endl;
if (data[0] >= 'a' && data[0] <= 'h' &&
data[1] >= '1' && data[1] <= '8' &&
data[2] >= 'a' && data[2] <= 'h' &&
data[3] >= '1' && data[3] <= '8') {
n = GenMoves(t, &move[0]);
for (i = OO; i < n; i++) {
fs = move[i].fs;
ts = move[i].ts;
sprintf_s(mvstr, 20, "%c%d%c%d\n", (fs & 7) + 'a', (fs >> 3) + 1, (ts & 7) + 'a', (ts >> 3) + 1);
if (!strcmp(data, mvstr)) {
gameMoves[gamePly].fs = fs;
gameMoves[gamePly].ts = ts;
gameMoves[gamePly].type = move[i].type;
MakeMove(t, &gameMoves[gamePly]);
gamePly++;
ply--;
return;
}
}
return;
}
if (!strcmp(data, "go\n")) {
bricabrac = BRICABRAC;
return;
}
if (!strcmp(data, "u\n") || !strcmp(data, "undo\n")) {
gamePly--;
ply++;
TakeBack(t, &gameMoves[gamePly]);
return;
}
}
void DoMove(Thread* t) {
s32 i, j = 0, score;
s32 PrevSearchOrder = 1000;
score = -INF;
for (i = 0; move[i].status != STOP; i++) {
printf("%i: ", i);
printf("%c%c", 'A' + (move[i].fs & 7), '1' + (move[i].fs >> 3));
printf("%c%c", 'A' + (move[i].ts & 7), '1' + (move[i].ts >> 3));
printf(" Score: %i ", move[i].score);
printf("order: %i\n", move[i].order);
if (move[i].score > score) {
score = move[i].score;
PrevSearchOrder = move[i].order;
j = i;
} else
if ((move[i].score == score)
&& (move[i].order < PrevSearchOrder)) {
PrevSearchOrder = move[i].order;
j = i;
}
if ((move[i].score != ILLEGAL)
&& (move[i].score > score)) {
score = move[i].score;
PrevSearchOrder = move[i].order;
j = i;
} else
if ((move[i].score != ILLEGAL)
&& (move[i].score == score)
&& (move[i].order < PrevSearchOrder)) {
PrevSearchOrder = move[i].order;
j = i;
}
}
printf("\nMove Played: ");
printf("%c%c", 'A' + (move[j].fs & 7), '1' + (move[j].fs >> 3));
printf("%c%c\n", 'A' + (move[j].ts & 7), '1' + (move[j].ts >> 3));
gameMoves[gamePly].fs = move[j].fs;
gameMoves[gamePly].ts = move[j].ts;
gameMoves[gamePly].type = move[j].type;
MakeMove(t, &gameMoves[gamePly]);
ply--;
gamePly++;
bricabrac = GETCMD;
}
void InitializeQSS() {
u08 sq, sqr, k, l;
s08 x, y, dx, dy;
s32 i;
u64 b, bb;
for (sq = 0; sq < 64; sq++) {
y = sq >> 3;
x = sq & 7;
bob[sq] = 0;
rob[sq] = 0;
for (i = 0; i < 256; i++) {
for (k = 0, l = 0; k <= 56; k += 8, l++) {
bb = 0;
b = (u64)i << k;
for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1; x + dx > -1; dx--) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1; x + dx < +8; dx++) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = +1; y + dy < +8; dy++) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = -1; y + dy > -1; dy--) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
qss[sq][i][l] = bb;
}
}
}
}
void InitializeRNK() {
u08 sq, sqr, i;
s08 x, y, dx, dy;
u64 bb, b;
for (sq = 0; sq < 64; sq++) {
y = sq >> 3;
x = sq & 7;
for (i = 0; i < 128; i++) {
bb = 0;
b = (u64)i << (sq & 56);
for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
sqr = (((y + dy) << 3) + x + dx);
bb |= one << sqr;
bob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = -1; x + dx > -1; dx--) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dx = +1; x + dx < +8; dx++) {
sqr = (y << 3) + x + dx;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = +1; y + dy < +8; dy++) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
for (dy = -1; y + dy > -1; dy--) {
sqr = ((y + dy) << 3) + x;
bb |= one << sqr;
rob[sq] |= one << sqr;
if ((one << sqr) & b) break;
}
qss[sq][i][0] = bb;
}
}
}
void InitPieceBB() {
s32 sq, x, y;
above[0] = 0xffffffffffffffff;
below[0] = 0xffffffffffffffff;
for (sq = A1; sq <= H8; sq++) {
x = sq & 7;
y = sq >> 3;
above[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) ^ 1) << (sq + 1);
below[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) << (sq + 1)) ^ 0xffffffffffffffff;
wPawnMoves[sq] = 0;
wPawnCapts[sq] = 0;
bPawnMoves[sq] = 0;
bPawnCapts[sq] = 0;
if (sq > H1 && sq < A8) {
// White Pawn Moves
wPawnMoves[sq] |= one << (sq + 8);
if (sq < A3) wPawnMoves[sq] |= one << (sq + 16);
// White Pawn Captures
if (x + 1 < +8) wPawnCapts[sq] |= one << (sq + 9);
if (x - 1 > -1) wPawnCapts[sq] |= one << (sq + 7);
// Black Pawn Moves
bPawnMoves[sq] |= one << (sq - 8);
if (sq > H6) bPawnMoves[sq] |= one << (sq - 16);
// Black Pawn Captures
if (x + 1 < +8) bPawnCapts[sq] |= one << (sq - 7);
if (x - 1 > -1) bPawnCapts[sq] |= one << (sq - 9);
}
// Knight Moves
knightMoves[sq] = 0;
if (y + 2 < +8 && x + 1 < +8) knightMoves[sq] |= one << (sq + 17);
if (y + 1 < +8 && x + 2 < +8) knightMoves[sq] |= one << (sq + 10);
if (y - 1 > -1 && x + 2 < +8) knightMoves[sq] |= one << (sq - +6);
if (y - 2 > -1 && x + 1 < +8) knightMoves[sq] |= one << (sq - 15);
if (y - 2 > -1 && x - 1 > -1) knightMoves[sq] |= one << (sq - 17);
if (y - 1 > -1 && x - 2 > -1) knightMoves[sq] |= one << (sq - 10);
if (y + 1 < +8 && x - 2 > -1) knightMoves[sq] |= one << (sq + +6);
if (y + 2 < +8 && x - 1 > -1) knightMoves[sq] |= one << (sq + 15);
// King Moves
kingMoves[sq] = 0;
if (y + 1 < +8) kingMoves[sq] |= one << (sq + 8);
if (y - 1 > -1) kingMoves[sq] |= one << (sq - 8);
if (x + 1 < +8) kingMoves[sq] |= one << (sq + 1);
if (x - 1 > -1) kingMoves[sq] |= one << (sq - 1);
if (y + 1 < +8 && x + 1 < +8) kingMoves[sq] |= one << (sq + 9);
if (y - 1 > -1 && x + 1 < +8) kingMoves[sq] |= one << (sq - 7);
if (y - 1 > -1 && x - 1 > -1) kingMoves[sq] |= one << (sq - 9);
if (y + 1 < +8 && x - 1 > -1) kingMoves[sq] |= one << (sq + 7);
}
InitializeQSS();
InitializeRNK();
}
void NewGame(Thread* t) {
s32 i;
LoadFen(t, startFen);
for (i = 0; i < 100; i++) epbb[i] = OO;
}
void Initialize() {
bricabrac = GETCMD;
gamePly = OO;
wtm = WHITE;
ply = OO;
InitPieceBB();
NewGame(t);
}
void SetSearchDepth()
{
char data[256];
int x = 0;
printf("Enter SEARCH DEPTH (sd): \n");
fgets(data, 4, stdin);
while ((data[x] >= '0') && (data[x] <= '9')) {
sd = 10 * sd + (data[x++] - '0');
}
}
s32 main() {
SetSearchDepth();
t = &thread;
Initialize();
do {
if (bricabrac == BRICABRAC) Bricabrac(t);
if (bricabrac == MOVE) DoMove(t);
GetCmd(t);
} while (bricabrac);
return 0;
}-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
Don't use the source in the post above. I screwed everything up because I did not see the TOMDEBUG lines in the search function and when I tried to edit it I ran out of time. As soon as I get it fixed I'll repost the corrected source. 
-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
I had to go back to Tommy's code and start over. And I'm thinking of changing this engine's name to DumbDonkey.
-
TommyTC
- Posts: 38
- Joined: Thu Mar 30, 2017 8:52 am
Re: I don't want to give up
Hi Mike,
Please disregard my previous comment:
===
Your change to "initial move priority" may have fixed a problem -- it at least changed the behavior.
I was testing "TOMDEBUG 3" version.
With search depth (sd) = 8, the "default" game (played by continuously entering "go") played relatively quickly on my pc, but with sd = 9, there were some positions that took over 2 hours (!) to complete the search.
Times are approximate.
1. a2a3 0:00:10 a7a5 0:00:06
2. b2b3 0:00:09 a5a4 0:00:05
3. b3a4 0:00:07 a8a4 0:08:28
4. c2c3 0:10:35 b7b5 0:04:58
5. d2d3 0:11:05 c7c5 0:35:49
6. e2e3 0:16:10 d7d5 0:37:52
7. f2f3 0:20:00 c5c4 1:10:00
8. d3c4 0:07:00 d5c4 2:10:00
9. d1d8 0:00:54
The first moves only took seconds, but after 8. d3c4, it took over 2 hours to complete the search and return a move.
To see more information, I found it useful to insert the following in Search just before the recursive call to Search:
With "TOMDEBUGA 2", it showed that the search was making continuous, but very slow progress.
I restarted with sd = 8, and entered the moves including 8. d3c4 and typed "go". It only took 1 minute and 40 seconds to search and return 8...d5c4 as the best move!
Next I updated the "initial move priority" to your:
m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];
Sure enough, that changed things considerably! At sd = 9, it now took 21 seconds to find d5c4 as the best move! At least it now finds the proper move in a short period of time. If there is another bug out there, it will need to be found on another day.
===
Ok, so I now started to look at your "initial move priorty" and constructed the following chart.
This is better than the previous version for "initial move priority", but there are a few things "wrong":
A King capturing a pawn is less priority than:
And....
===
A funny thing happened on the way to verifying that a King move is lower priority than a pawn move!
#define TOMDEBUG 3
#define TOMDEBUGA 2
sd 5
I entered the following moves: 1. e2e4 f7f5 2. e4f5 a7a6 3. f5f6 d7d6 4. f6f7
And then entered "go".
The first thing to notice is that indeed A6A5 was the first move searched and 20 other non-capture moves were examined before 4...e8f7 (Black King capturing a pawn).
You might think all is fine, since it eventually played 4...e8f7, but now look at the score for A6A5: -2000. This is NOT the value for ILLEGAL. This is the value for the Black King being knocked off the board!
If you scroll your screen up you will see that at search depth 3 there are positions being passed to "Search" that do not have a Black King!
The culprit? In GenMoves, pawn promotion is handled differently than other moves, and then the "continue" statement is executed. The "captures" variable is not properly updated. Therefore the "ILLEGAL" taking of the King is not detected, and hilarity ensues!
===
I see you ran into a problem with my '#include "stdafx.h"'. That's for pre-compiled headers, a default when I created the project bricabrac on my pc. I will turn that build option off, so that neither of us needs stdafx.h.
===
Once you post your updated code, I will pick up your changes and continue, although I might continue a bit more with TOMDEBUG 3.
By the way, I see nothing wrong with the name Bricabrac. And it's way too early to list my name in the credits.
Have you thought about putting your code on Github (or similar) site? I'm not sure a forum like TalkChess is quite the right place to be tossing code back and forth to each other. I'm not really a user of Github, but this project wouldn't be a bad place to start.
Kind Regards,
Tommy
Please disregard my previous comment:
Since your code produces pseudo-legal moves, this is expected behavior.I've noticed at times that some moves are labelled as "illegal" that shouldn't be -- certainly not at the root. In one position, the first move searched (order = 0), showed "illegal" score.
===
Your change to "initial move priority" may have fixed a problem -- it at least changed the behavior.
I was testing "TOMDEBUG 3" version.
With search depth (sd) = 8, the "default" game (played by continuously entering "go") played relatively quickly on my pc, but with sd = 9, there were some positions that took over 2 hours (!) to complete the search.
Times are approximate.
1. a2a3 0:00:10 a7a5 0:00:06
2. b2b3 0:00:09 a5a4 0:00:05
3. b3a4 0:00:07 a8a4 0:08:28
4. c2c3 0:10:35 b7b5 0:04:58
5. d2d3 0:11:05 c7c5 0:35:49
6. e2e3 0:16:10 d7d5 0:37:52
7. f2f3 0:20:00 c5c4 1:10:00
8. d3c4 0:07:00 d5c4 2:10:00
9. d1d8 0:00:54
The first moves only took seconds, but after 8. d3c4, it took over 2 hours to complete the search and return a move.
To see more information, I found it useful to insert the following in Search just before the recursive call to Search:
Code: Select all
// "TOMDEBUGA 0" Don't display positions during search
// "TOMDEBUGA 1" Display "sd - 1" positions during search
// "TOMDEBUGA 2" Display "sd - 1" and "sd - 2" positions during search
#if TOMDEBUGA > 0
if (depth > (sd - 1 - TOMDEBUGA)) {
printf("Depth: %i\n", depth);
PrintBoard(t);
}
#endif
mov->score = -Search(t, m + n, -beta, -alpha, depth);
I restarted with sd = 8, and entered the moves including 8. d3c4 and typed "go". It only took 1 minute and 40 seconds to search and return 8...d5c4 as the best move!
Next I updated the "initial move priority" to your:
m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];
Sure enough, that changed things considerably! At sd = 9, it now took 21 seconds to find d5c4 as the best move! At least it now finds the proper move in a short period of time. If there is another bug out there, it will need to be found on another day.
===
Ok, so I now started to look at your "initial move priorty" and constructed the following chart.
Code: Select all
"from" piece (moving)
p n b r q k
100 300 300 500 900 2000
(empty) 0 -100 -300 -300 -500 -900 -2000
p 100 1500 1300 1300 1100 700 -400
"to" n 300 4700 4500 4500 4300 3900 2800
piece b 300 4700 4500 4500 4300 3900 2800
(captured) r 500 7900 7700 7700 7500 7100 6000
q 900 14300 14100 14100 13900 13500 12400
k 2000 31900 31700 31700 31500 31100 30000
A King capturing a pawn is less priority than:
- A pawn moving to a vacant square
- A Knight moving to a vacant square
- A Bishop moving to a vacant square
And....
===
A funny thing happened on the way to verifying that a King move is lower priority than a pawn move!
#define TOMDEBUG 3
#define TOMDEBUGA 2
sd 5
I entered the following moves: 1. e2e4 f7f5 2. e4f5 a7a6 3. f5f6 d7d6 4. f6f7
And then entered "go".
The first thing to notice is that indeed A6A5 was the first move searched and 20 other non-capture moves were examined before 4...e8f7 (Black King capturing a pawn).
You might think all is fine, since it eventually played 4...e8f7, but now look at the score for A6A5: -2000. This is NOT the value for ILLEGAL. This is the value for the Black King being knocked off the board!
If you scroll your screen up you will see that at search depth 3 there are positions being passed to "Search" that do not have a Black King!
The culprit? In GenMoves, pawn promotion is handled differently than other moves, and then the "continue" statement is executed. The "captures" variable is not properly updated. Therefore the "ILLEGAL" taking of the King is not detected, and hilarity ensues!
===
I see you ran into a problem with my '#include "stdafx.h"'. That's for pre-compiled headers, a default when I created the project bricabrac on my pc. I will turn that build option off, so that neither of us needs stdafx.h.
===
Once you post your updated code, I will pick up your changes and continue, although I might continue a bit more with TOMDEBUG 3.
By the way, I see nothing wrong with the name Bricabrac. And it's way too early to list my name in the credits.
Have you thought about putting your code on Github (or similar) site? I'm not sure a forum like TalkChess is quite the right place to be tossing code back and forth to each other. I'm not really a user of Github, but this project wouldn't be a bad place to start.
Kind Regards,
Tommy
-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
About speed, I am very optimistic. Bricabrac runs circles around TSCP, LOL!
I did say honorary. And I think you deserve at least that much for all that you have done!And it's way too early to list my name in the credits.
But I will remove that for now. 
I planned on putting it on Github but only after it is working properly.
Last couple of days prior to today. I put in at least 20 hours and got nowhere. Last night I had one of the worst fibro attacks that I have ever had. Today I did not do anything. I'm hoping to do some work tomorrow. But I'm going to have to stop trying so hard.
I'm going to revert back to your TOMDEBUG version (once again) and work on the things you mentioned.
One Idea is to make a RootSearch() and just keep track of the best move as each move is searched. Seems far simpler than the way it is now. But, it upsets me a bit that it means undoing that clever code that you spent so much time on. Do you think it sounds like a good idea, though?
Thanks again for all your effort!
Mike
-
Mike Sherwin
- Posts: 860
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: I don't want to give up
retracted