From: Steinar H. Gunderson Date: Tue, 22 Jan 2013 16:18:14 +0000 (+0100) Subject: Initial checkin for move to Git (no prior version history available). X-Git-Url: https://git.sesse.net/?p=stupid;a=commitdiff_plain;h=HEAD Initial checkin for move to Git (no prior version history available). --- 5fed4d946f3a347713e604fe009a17952b90da76 diff --git a/common.h b/common.h new file mode 100644 index 0000000..27b20d5 --- /dev/null +++ b/common.h @@ -0,0 +1,15 @@ +#ifndef _COMMON_H +#define _COMMON_H 1 + +#include "position.h" + +#define POSSIBLY_INVERT(x, inverseflag) (((x) ^ (inverseflag)) - (inverseflag)) + +// #define PROFILE_HASHES + +extern unsigned total_nodes; +struct killer_move { + unsigned from, to; +}; + +#endif /* !defined(_COMMON_H) */ diff --git a/evaluator.c b/evaluator.c new file mode 100644 index 0000000..f179f30 --- /dev/null +++ b/evaluator.c @@ -0,0 +1,343 @@ +#include +#include +#include "evaluator.h" +#include "hash.h" + +int material_values[NUM_PIECES][NUM_SQUARES]; + +// simple material counter for now, improve later :-) +void init_evaluator(void) +{ + unsigned i, x, y; + + for (i = 0; i < NUM_SQUARES; ++i) { + material_values[PIECE_EMPTY ][i] = 0; + material_values[PIECE_KNIGHT][i] = 280; + material_values[PIECE_BISHOP][i] = 320; + material_values[PIECE_ROOK ][i] = 500; + material_values[PIECE_QUEEN ][i] = 900; + material_values[PIECE_KING ][i] = 20000; // more than all else combined + } + + // pawns are better off near the other side, and better close to the middle + for (y = 0; y < 8; ++y) { + for (x = 0; x < 8; ++x) { + unsigned value = 100; + + switch (x) { + case 0: + case 7: + break; + case 1: + case 6: + value += 5; + break; + case 2: + case 5: + value += 7; + if (y >= 3) + value += 10; // central pawns ftw + break; + case 3: + case 4: + value += 10; + if (y >= 3) + value += 10; // central pawns ftw + break; + } + + switch (y) { + case 4: + value += 10; + break; + case 5: + value += 20; + break; + case 6: + value += 40; + break; + case 7: + value += 80; + break; + } + + material_values[PIECE_PAWN][SQUARE_TO_NUM(x,y)] = value; + } + } + + // knights hate the edges + for (y = 0; y < 8; ++y) { + for (x = 0; x < 8; ++x) { + if (x == 0 || x == 7 || y == 0 || y == 7) + material_values[PIECE_KNIGHT][SQUARE_TO_NUM(x,y)] -= 40; + else if (x == 1 || x == 6 || y == 1 || y == 6) + material_values[PIECE_KNIGHT][SQUARE_TO_NUM(x,y)] -= 15; + } + } +} + +void count_pawns(const struct piece * const pieces, unsigned *pawns) +{ + unsigned i; + for (i = 0; i < 8; ++i) { + if (pieces[i].type == PIECE_PAWN) { + assert(NUM_TO_FILE(pieces[i].square) >= 0); + assert(NUM_TO_FILE(pieces[i].square) < 8); + ++pawns[NUM_TO_FILE(pieces[i].square)]; + } + } +} + +unsigned find_doubled_pawns(const unsigned * const pawns) +{ + unsigned i; + unsigned num = 0; + + for (i = 0; i < 8; ++i) { + if (pawns[i] > 1) { + ++num; + } + } + + return num; +} + +unsigned find_isolated_pawns(const unsigned * const pawns) +{ + unsigned i; + unsigned num = 0; + + for (i = 0; i < 8; ++i) { + if (pawns[i] == 0) + continue; + if (i > 0 && pawns[i - 1] > 0) + continue; + if (i < 8 && pawns[i + 1] > 0) + continue; + ++num; + } + + return num; +} + +unsigned find_passed_pawns(const struct piece * const pieces, const struct piece * const opp_pieces, unsigned *pawns, unsigned *opp_pawns, int inverse) +{ + unsigned i, j; + unsigned num = 0; + + for (i = 0; i < 8; ++i) { + unsigned file, rank; + + // could be empty, or promoted (although the latter is unlikely) + if (pieces[i].type != PIECE_PAWN) + continue; + + file = NUM_TO_FILE(pieces[i].square); + + // usual heuristic: blocked by "the same pawn" on the same file + if (file == NUM_TO_FILE(opp_pieces[i].square) && + POSSIBLY_INVERT(opp_pieces[i].square - pieces[i].square, inverse) >= 0) + continue; + + // ok, obviously not. let's see if there's anything can indeed block it. + if (opp_pawns[file] > 0 || (file > 0 && opp_pawns[file - 1] > 0) || (file < 7 && opp_pawns[file + 1] > 0)) { + rank = NUM_TO_RANK(pieces[i].square); + for (j = 0; j < 8; ++j) { + unsigned ofile; + + if (opp_pieces[j].type != PIECE_PAWN) + continue; + + // needs to be in front to block + if (POSSIBLY_INVERT(NUM_TO_RANK(opp_pieces[j].square) - rank, inverse) <= 0) + continue; + + ofile = NUM_TO_FILE(opp_pieces[j].square); + if (file == ofile || file == ofile - 1 || file == ofile + 1) + goto not_this_one; + } + } + + ++num; + +not_this_one: + 1; + } + + return num; +} + +// very crude, but hey +int king_safe(const struct piece * const pieces) +{ + unsigned square = pieces[0].square; + unsigned full_safety = 3; + + // c1, f1, c6, f6 are "half-safe", and are judged as the more cornered ones, only slightly + // more harshly + if (square == SQUARE_TO_NUM(2, 0) || square == SQUARE_TO_NUM(5, 0) || square == SQUARE_TO_NUM(2, 7) || square == SQUARE_TO_NUM(5, 7)) + full_safety = 2; + + if (square == SQUARE_TO_NUM(0, 0) || square == SQUARE_TO_NUM(1, 0)) { + if (pieces[8].type != PIECE_PAWN || pieces[9].type != PIECE_PAWN || pieces[10].type != PIECE_PAWN) + return 0; + + // king on a1 or b1, just need three good pawns for full safety (ignore threats down there for now) + if (pieces[8].square == SQUARE_TO_NUM(0, 1) && pieces[9].square == SQUARE_TO_NUM(1, 1) && pieces[10].square == SQUARE_TO_NUM(2, 1)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 2) && pieces[9].square == SQUARE_TO_NUM(1, 1) && pieces[10].square == SQUARE_TO_NUM(2, 1)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 1) && pieces[9].square == SQUARE_TO_NUM(1, 2) && pieces[10].square == SQUARE_TO_NUM(2, 1)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 3) && pieces[9].square == SQUARE_TO_NUM(1, 2) && pieces[10].square == SQUARE_TO_NUM(2, 1)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 1) && pieces[9].square == SQUARE_TO_NUM(1, 1) && pieces[10].square == SQUARE_TO_NUM(2, 2)) + return 1; + } else if (square == SQUARE_TO_NUM(6, 0) || square == SQUARE_TO_NUM(7, 0)) { + if (pieces[15].type != PIECE_PAWN || pieces[14].type != PIECE_PAWN || pieces[13].type != PIECE_PAWN) + return 0; + + // king on g1 or h1, just need three good pawns for full safety (ignore threats down there for now) + if (pieces[15].square == SQUARE_TO_NUM(7, 1) && pieces[14].square == SQUARE_TO_NUM(6, 1) && pieces[13].square == SQUARE_TO_NUM(5, 1)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 2) && pieces[14].square == SQUARE_TO_NUM(6, 1) && pieces[13].square == SQUARE_TO_NUM(5, 1)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 1) && pieces[14].square == SQUARE_TO_NUM(6, 2) && pieces[13].square == SQUARE_TO_NUM(5, 1)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 3) && pieces[14].square == SQUARE_TO_NUM(6, 2) && pieces[13].square == SQUARE_TO_NUM(5, 1)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 1) && pieces[14].square == SQUARE_TO_NUM(6, 1) && pieces[13].square == SQUARE_TO_NUM(5, 2)) + return 1; + } else if (square == SQUARE_TO_NUM(0, 7) || square == SQUARE_TO_NUM(1, 7)) { + if (pieces[8].type != PIECE_PAWN || pieces[9].type != PIECE_PAWN || pieces[10].type != PIECE_PAWN) + return 0; + + // king on a8 or b8, just need three good pawns for full safety (ignore threats down there for now) + if (pieces[8].square == SQUARE_TO_NUM(0, 6) && pieces[9].square == SQUARE_TO_NUM(1, 6) && pieces[10].square == SQUARE_TO_NUM(2, 6)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 5) && pieces[9].square == SQUARE_TO_NUM(1, 6) && pieces[10].square == SQUARE_TO_NUM(2, 6)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 6) && pieces[9].square == SQUARE_TO_NUM(1, 5) && pieces[10].square == SQUARE_TO_NUM(2, 6)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 3) && pieces[9].square == SQUARE_TO_NUM(1, 5) && pieces[10].square == SQUARE_TO_NUM(2, 6)) + return full_safety; + if (pieces[8].square == SQUARE_TO_NUM(0, 6) && pieces[9].square == SQUARE_TO_NUM(1, 6) && pieces[10].square == SQUARE_TO_NUM(2, 5)) + return 1; + } else if (square == SQUARE_TO_NUM(6, 7) || square == SQUARE_TO_NUM(7, 7)) { + if (pieces[15].type != PIECE_PAWN || pieces[14].type != PIECE_PAWN || pieces[13].type != PIECE_PAWN) + return 0; + + // king on g1 or h1, just need three good pawns for full safety (ignore threats down there for now) + if (pieces[15].square == SQUARE_TO_NUM(7, 6) && pieces[14].square == SQUARE_TO_NUM(6, 6) && pieces[13].square == SQUARE_TO_NUM(5, 6)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 5) && pieces[14].square == SQUARE_TO_NUM(6, 6) && pieces[13].square == SQUARE_TO_NUM(5, 6)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 6) && pieces[14].square == SQUARE_TO_NUM(6, 5) && pieces[13].square == SQUARE_TO_NUM(5, 6)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 3) && pieces[14].square == SQUARE_TO_NUM(6, 5) && pieces[13].square == SQUARE_TO_NUM(5, 6)) + return full_safety; + if (pieces[15].square == SQUARE_TO_NUM(7, 6) && pieces[14].square == SQUARE_TO_NUM(6, 6) && pieces[13].square == SQUARE_TO_NUM(5, 5)) + return 1; + } + + return 0; +} + +int pawn_and_king_evaluation(const struct position * const p, unsigned total_material) +{ + // this is rather expensive, so we hash it + unsigned long long phash = hash_position_pk(p); + unsigned bucket = phash % PHASH_BUCKETS; + struct hash_pawn_entry *he = pawn_eval_table[bucket]; + int pawn_score = 0, king_safety; +#ifdef PROFILE_HASHES + unsigned chain = 0; +#endif + + while (he != NULL) { + if (he->phash == phash) { +#ifdef PROFILE_HASHES + record_lookup(2, true, ++chain); +#endif + return he->pawn_score + ((he->king_safety * (int)total_material) >> 8); + } + he = he->next; +#ifdef PROFILE_HASHES + ++chain; +#endif + } +#ifdef PROFILE_HASHES + record_lookup(2, false, chain); +#endif + + // ok, need to calculate + { + unsigned white_pawns[8] = { 0 }, black_pawns[8] = { 0 }; + count_pawns(p->white_pieces + 8, white_pawns); + count_pawns(p->black_pieces + 8, black_pawns); + + // doubled pawns are bad + pawn_score += 20 * find_doubled_pawns(white_pawns); + pawn_score -= 20 * find_doubled_pawns(black_pawns); + + // so are isolated pawns + pawn_score += 40 * find_isolated_pawns(white_pawns); + pawn_score -= 40 * find_isolated_pawns(black_pawns); + + // but passed pawns are extraordinarily good + pawn_score += 80 * find_passed_pawns(p->white_pieces + 8, p->black_pieces + 8, white_pawns, black_pawns, 0); + pawn_score -= 80 * find_passed_pawns(p->black_pieces + 8, p->white_pieces + 8, black_pawns, white_pawns, -1); + } + + king_safety = king_safe(p->white_pieces) - king_safe(p->black_pieces); + + // insert into the hash + he = (struct hash_pawn_entry *)malloc(sizeof(struct hash_pawn_entry)); + he->phash = phash; + he->pawn_score = pawn_score; + he->king_safety = king_safety; + + assert(bucket < PHASH_BUCKETS); + + he->next = pawn_eval_table[bucket]; + pawn_eval_table[bucket] = he; + + return pawn_score + ((king_safety * (int)total_material) >> 8); +} + +int evaluate(const struct position * const p) +{ + unsigned i; + int score = 0; + unsigned white_material = 0, black_material = 0; + + for (i = 0; i < 16; ++i) { + white_material += material_values[p->white_pieces[i].type][p->white_pieces[i].square]; + } + for (i = 0; i < 16; ++i) { + black_material += material_values[p->black_pieces[i].type][NUM_SQUARES - 1 - p->black_pieces[i].square]; + } + + // bishop pair is good + if (p->white_pieces[4].type == PIECE_BISHOP && p->white_pieces[5].type == PIECE_BISHOP) + score += 50; + if (p->black_pieces[4].type == PIECE_BISHOP && p->black_pieces[5].type == PIECE_BISHOP) + score -= 50; + + // ability to castle is good + if (p->wc_short) + score += 25; + if (p->wc_long) + score += 20; + if (p->bc_short) + score -= 25; + if (p->bc_long) + score -= 20; + + score += pawn_and_king_evaluation(p, white_material + black_material - 40000); + + ++total_nodes; + + return score + white_material - black_material; +} + diff --git a/evaluator.h b/evaluator.h new file mode 100644 index 0000000..4a67dd0 --- /dev/null +++ b/evaluator.h @@ -0,0 +1,9 @@ +#ifndef _EVALUATOR_H +#define _EVALUATOR_H 1 + +#include "position.h" + +void init_evaluator(void); +int evaluate(const struct position * const p); + +#endif /* !defined(_EVALUATOR_H) */ diff --git a/hash.c b/hash.c new file mode 100644 index 0000000..d061ec8 --- /dev/null +++ b/hash.c @@ -0,0 +1,240 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "hash.h" + +unsigned hash_used; +struct hash_entry *transposition_table[HASH_BUCKETS], *repeat_table[RHASH_BUCKETS]; +struct hash_pawn_entry *pawn_eval_table[PHASH_BUCKETS]; +unsigned long long zobrist_values[16][NUM_SQUARES]; + +#ifdef PROFILE_HASHES +unsigned num_lookups[3], num_hits[3], total_chain_length[3]; +#endif + +void clear_hash(void) +{ + unsigned i; + for (i = 0; i < HASH_BUCKETS; ++i) { + while (transposition_table[i] != NULL) { + struct hash_entry *he = transposition_table[i]; + transposition_table[i] = he->next; + free(he); + } + } + +#ifdef PROFILE_HASHES + num_lookups[0] = num_hits[0] = total_chain_length[0] = 0; +#endif + + hash_used = 0; +} + +void init_hash(void) +{ + unsigned i, j; + for (i = 0; i < 16; ++i) + for (j = 0; j < NUM_SQUARES; ++j) + zobrist_values[i][j] = (unsigned long long)rand() ^ ((unsigned long long)(rand()) << 15L) ^ ((unsigned long long)(rand()) << 32L); + + for (i = 0; i < HASH_BUCKETS; ++i) + transposition_table[i] = NULL; + + for (i = 0; i < RHASH_BUCKETS; ++i) + repeat_table[i] = NULL; + + for (i = 0; i < PHASH_BUCKETS; ++i) + pawn_eval_table[i] = NULL; + +#ifdef PROFILE_HASHES + num_lookups[0] = num_hits[0] = total_chain_length[0] = 0; + num_lookups[1] = num_hits[1] = total_chain_length[1] = 0; + num_lookups[2] = num_hits[2] = total_chain_length[2] = 0; +#endif + + hash_used = 0; +} + +unsigned hash_position(const struct position * const p) +{ + unsigned i; + unsigned hash = (p->white_to_move) ? 0 : 0xbb248d0861beb593ULL; + if (p->wc_short) + hash ^= 0x4fba418408778d3bULL; + if (p->wc_long) + hash ^= 0xcb15fc4e648baac4ULL; + if (p->bc_short) + hash ^= 0xdd6c4ebe58a96ef4ULL; + if (p->bc_long) + hash ^= 0x9a60651c19fb5c53ULL; + + // 4 is unused, use that for en passant square + if (p->ep_square) + hash ^= zobrist_values[4][p->ep_square]; + + for (i = 0; i < 16; ++i) { + if (p->white_pieces[i].type != PIECE_EMPTY) + hash ^= zobrist_values[p->white_pieces[i].type][p->white_pieces[i].square]; + } + for (i = 0; i < 16; ++i) { + if (p->black_pieces[i].type != PIECE_EMPTY) + hash ^= zobrist_values[p->black_pieces[i].type + 8][p->black_pieces[i].square]; + } + + return hash; +} + +// same as hash_position, but pawn and king placement only +unsigned long long hash_position_pk(const struct position * const p) +{ + unsigned i; + unsigned hash = 0; + + hash ^= zobrist_values[PIECE_KING][p->white_pieces[0].square]; + hash ^= zobrist_values[PIECE_KING + 8][p->black_pieces[0].square]; + + for (i = 8; i < 16; ++i) { + if (p->white_pieces[i].type == PIECE_PAWN) + hash ^= zobrist_values[PIECE_PAWN][p->white_pieces[i].square]; + } + for (i = 8; i < 16; ++i) { + if (p->black_pieces[i].type == PIECE_PAWN) + hash ^= zobrist_values[PIECE_PAWN + 8][p->black_pieces[i].square]; + } + + return hash; +} + +bool lookup_hash(const struct position * const pos, unsigned long long phash, unsigned min_depth, unsigned min_seldepth, unsigned *ret_from, unsigned *ret_to, int *ret_score) +{ + unsigned bucket = phash % HASH_BUCKETS; + struct hash_entry *he = transposition_table[bucket]; +#ifdef PROFILE_HASHES + unsigned chain = 0; +#endif + + while (he != NULL) { + if (he->phash == phash && (he->depth > min_depth || (he->depth == min_depth && he->seldepth >= min_seldepth))) { + if (ret_from) + *ret_from = he->best_from; + if (ret_to) + *ret_to = he->best_to; + *ret_score = he->score; +#ifdef PROFILE_HASHES + record_lookup(0, true, ++chain); +#endif + return true; + } + + he = he->next; +#ifdef PROFILE_HASHES + ++chain; +#endif + } + +#ifdef PROFILE_HASHES + record_lookup(0, false, chain); +#endif + + // not found, sorry + return false; +} + +void insert_hash(const struct position * const pos, unsigned long long phash, unsigned depth, unsigned seldepth, unsigned from, unsigned to, int score) +{ + unsigned bucket = phash % HASH_BUCKETS; + struct hash_entry *he = (struct hash_entry *)malloc(sizeof(struct hash_entry)); + + he->phash = phash; + he->depth = depth; + he->seldepth = seldepth; + he->score = score; + he->best_from = from; + he->best_to = to; + + he->next = transposition_table[bucket]; + transposition_table[bucket] = he; + + // FIXME: prune the hash table here + ++hash_used; +} + +int lookup_record(unsigned long long phash) +{ + unsigned bucket = phash % RHASH_BUCKETS; + struct hash_entry *he = repeat_table[bucket]; +#ifdef PROFILE_HASHES + unsigned chain = 0; +#endif + + while (he != NULL) { + if (he->phash == phash) { +#ifdef PROFILE_HASHES + record_lookup(1, true, ++chain); +#endif + return he->score; + } + he = he->next; +#ifdef PROFILE_HASHES + ++chain; +#endif + } + +#ifdef PROFILE_HASHES + record_lookup(1, false, chain); +#endif + + return 0; +} + +void record_move(const struct position * const pos) +{ + // see if this has happened before + unsigned long long phash = hash_position(pos); + unsigned bucket = phash % RHASH_BUCKETS; + struct hash_entry *he = repeat_table[bucket]; + + while (he != NULL) { + if (he->phash == phash) { + // record another repeat + ++he->score; + return; + } + he = he->next; + } + + // not found before, let's insert it + he = (struct hash_entry *)malloc(sizeof(struct hash_entry)); + he->phash = phash; + he->score = 1; + he->next = repeat_table[bucket]; + repeat_table[bucket] = he; +} + +#ifdef PROFILE_HASHES + +void record_lookup(unsigned hash_num, bool hit, unsigned chain_length) +{ + ++num_lookups[hash_num]; + if (hit) + ++num_hits[hash_num]; + total_chain_length[hash_num] += chain_length; +} + +void print_profile(unsigned hash_num) +{ + printf("Profiling hash %u:\n", hash_num); + printf(" Total lookups = %u\n", num_lookups[hash_num]); + printf(" Hit rate = %.3f\n", (double)num_hits[hash_num] / (double)num_lookups[hash_num]); + printf(" Avg chain = %.2f\n\n", (double)total_chain_length[hash_num] / (double)num_lookups[hash_num]); +} + +#endif /* defined(PROFILE_HASHES) */ diff --git a/hash.h b/hash.h new file mode 100644 index 0000000..5a59b85 --- /dev/null +++ b/hash.h @@ -0,0 +1,50 @@ +#ifndef _HASH_H +#define _HASH_H 1 + +#include "common.h" + +/* Simple Zobrist hashing in a classic hash table */ +struct hash_entry { + unsigned long long phash; + int score; + unsigned char depth, seldepth, best_from, best_to; + struct hash_entry *next; +}; +struct hash_pawn_entry { + unsigned long long phash; + int pawn_score, king_safety; + struct hash_pawn_entry *next; +}; + +extern unsigned hash_used; + +/* The inserter will never have more elements in the hash table than this (approx. 32MB) */ +#define HASH_MAX_ELEMS (32000000 / sizeof(struct hash_entry)) +// #define HASH_BUCKETS (HASH_MAX_ELEMS / 16) +#define HASH_BUCKETS 16384 /* better to have a power of two */ +#define RHASH_BUCKETS 64 +#define PHASH_BUCKETS 262144 + +extern struct hash_entry *transposition_table[HASH_BUCKETS]; +extern struct hash_pawn_entry *pawn_eval_table[PHASH_BUCKETS]; + +void clear_hash(void); +void init_hash(void); + +unsigned hash_position(const struct position * const p); +unsigned long long hash_position_pk(const struct position * const p); + +// transposition table +bool lookup_hash(const struct position * const pos, unsigned long long phash, unsigned min_depth, unsigned min_seldepth, unsigned *ret_from, unsigned *ret_to, int *ret_score); +void insert_hash(const struct position * const pos, unsigned long long phash, unsigned depth, unsigned seldepth, unsigned from, unsigned to, int score); + +// history table (threefold repetition code) +int lookup_record(unsigned long long phash); +void record_move(const struct position * const pos); + +#ifdef PROFILE_HASHES +void record_lookup(unsigned hash_num, bool hit, unsigned chain_length); +void print_profile(unsigned hash_num); +#endif + +#endif diff --git a/position.c b/position.c new file mode 100644 index 0000000..a3d24fb --- /dev/null +++ b/position.c @@ -0,0 +1,364 @@ +#include +#include +#include +#include "position.h" +#include "evaluator.h" + +void place_piece(struct position *pos, unsigned file, unsigned rank, unsigned char piece) +{ + struct piece *ptr = IS_WHITE(piece) ? pos->white_pieces : pos->black_pieces; + unsigned i; + + for (i = 0; i < 16; ++i) { + if (ptr[i].type == PIECE_EMPTY) { + ptr[i].type = MAKE_COLORLESS(piece); + ptr[i].square = SQUARE_TO_NUM(file, rank); + + pos->board[ptr[i].square] = piece | (i << 4); + + return; + } + } + + assert(0); +} + +void init_position(struct position *pos) +{ + unsigned i, y, x; + + // clear the board + for (i = 0; i < NUM_SQUARES; ++i) { + pos->board[i] = PIECE_EMPTY; + } + for (i = 0; i < 16; ++i) { + pos->white_pieces[i].type = pos->black_pieces[i].type = PIECE_EMPTY; + } + + // mark off the invalid squares + for (x = 0; x < 10; ++x) { + pos->board[x + 0 * 10] = PIECE_INVALID; + pos->board[x + 1 * 10] = PIECE_INVALID; + pos->board[x + 10 * 10] = PIECE_INVALID; + pos->board[x + 11 * 10] = PIECE_INVALID; + } + for (y = 2; y < 10; ++y) { + pos->board[0 + y * 10] = PIECE_INVALID; + pos->board[9 + y * 10] = PIECE_INVALID; + } + + // kings + place_piece(pos, 4, 0, MAKE_WHITE(PIECE_KING)); + place_piece(pos, 4, 7, MAKE_BLACK(PIECE_KING)); + + // queens + place_piece(pos, 3, 0, MAKE_WHITE(PIECE_QUEEN)); + place_piece(pos, 3, 7, MAKE_BLACK(PIECE_QUEEN)); + + // rooks + place_piece(pos, 0, 0, MAKE_WHITE(PIECE_ROOK)); + place_piece(pos, 7, 0, MAKE_WHITE(PIECE_ROOK)); + place_piece(pos, 0, 7, MAKE_BLACK(PIECE_ROOK)); + place_piece(pos, 7, 7, MAKE_BLACK(PIECE_ROOK)); + + // bishops + place_piece(pos, 2, 0, MAKE_WHITE(PIECE_BISHOP)); + place_piece(pos, 5, 0, MAKE_WHITE(PIECE_BISHOP)); + place_piece(pos, 2, 7, MAKE_BLACK(PIECE_BISHOP)); + place_piece(pos, 5, 7, MAKE_BLACK(PIECE_BISHOP)); + + // knights + place_piece(pos, 1, 0, MAKE_WHITE(PIECE_KNIGHT)); + place_piece(pos, 6, 0, MAKE_WHITE(PIECE_KNIGHT)); + place_piece(pos, 1, 7, MAKE_BLACK(PIECE_KNIGHT)); + place_piece(pos, 6, 7, MAKE_BLACK(PIECE_KNIGHT)); + + // pawns + for (x = 0; x < 8; ++x) { + place_piece(pos, x, 1, MAKE_WHITE(PIECE_PAWN)); + place_piece(pos, x, 6, MAKE_BLACK(PIECE_PAWN)); + } + + // non-piece information + pos->wc_short = pos->wc_long = pos->bc_short = pos->bc_long = true; + pos->ep_square = 0; + pos->white_to_move = true; +} + +// checks various internal structures -- not a complete check, but useful +// to safeguard against corruption +void validate_position(const struct position * const pos) +{ + unsigned i, j, k; + +#if 0 + // both sides need kings + assert(pos->white_pieces[0].type == PIECE_KING); + assert(pos->black_pieces[0].type == PIECE_KING); +#endif + + // check that all material is on the board, with correct indexes + for (i = 0; i < 2; ++i) { + bool white = (i == 0); + const struct piece * const pieces = (white ? pos->white_pieces : pos->black_pieces); + + for (j = 0; j < 16; ++j) { + if (pieces[j].type == PIECE_EMPTY) + continue; + + // valid piece type + assert(pieces[j].type >= PIECE_PAWN); + assert(pieces[j].type <= PIECE_QUEEN); + assert(pieces[j].type != PIECE_INVALID); + + // on a valid square + assert(pieces[j].square >= SQUARE_TO_NUM(0, 0)); + assert(pieces[j].square <= SQUARE_TO_NUM(7, 7)); + assert(NUM_TO_FILE(pieces[j].square) >= 0); + assert(NUM_TO_FILE(pieces[j].square) <= 7); + assert(NUM_TO_RANK(pieces[j].square) >= 0); + assert(NUM_TO_RANK(pieces[j].square) <= 7); + + // the board matches + assert(MAKE_COLORLESS(pos->board[pieces[j].square]) == pieces[j].type); + + if (white) + assert(IS_WHITE(pos->board[pieces[j].square])); + else + assert(IS_BLACK(pos->board[pieces[j].square])); + + assert(FIND_INDEX(pos->board[pieces[j].square]) == j); + } + } + + // check that there's no phantom material + for (i = 0; i < 8; ++i) { + for (j = 0; j < 8; ++j) { + unsigned square = SQUARE_TO_NUM(i, j); + + if (MAKE_COLORLESS(pos->board[square]) == PIECE_EMPTY) + continue; + + if (IS_WHITE(pos->board[square])) { + assert(pos->white_pieces[FIND_INDEX(pos->board[square])].type == MAKE_COLORLESS(pos->board[square])); + assert(pos->white_pieces[FIND_INDEX(pos->board[square])].square == square); + } else { + assert(pos->black_pieces[FIND_INDEX(pos->board[square])].type == MAKE_COLORLESS(pos->board[square])); + assert(pos->black_pieces[FIND_INDEX(pos->board[square])].square == square); + } + } + } + + // TODO: check castling sanity +} + +char piece_to_char(int piece) +{ + switch (piece & 0x0f) { + case PIECE_EMPTY: + return ' '; + case MAKE_WHITE(PIECE_PAWN): + return 'P'; + case MAKE_BLACK(PIECE_PAWN): + return 'p'; + case MAKE_WHITE(PIECE_ROOK): + return 'R'; + case MAKE_BLACK(PIECE_ROOK): + return 'r'; + case MAKE_WHITE(PIECE_KNIGHT): + return 'N'; + case MAKE_BLACK(PIECE_KNIGHT): + return 'n'; + case MAKE_WHITE(PIECE_BISHOP): + return 'B'; + case MAKE_BLACK(PIECE_BISHOP): + return 'b'; + case MAKE_WHITE(PIECE_QUEEN): + return 'Q'; + case MAKE_BLACK(PIECE_QUEEN): + return 'q'; + case MAKE_WHITE(PIECE_KING): + return 'K'; + case MAKE_BLACK(PIECE_KING): + return 'k'; + default: + return '?'; + } +} + +void print_position(struct position *pos) +{ + unsigned x, y; + + printf("Position:\n\n"); + + for (y = 8; y --> 0; ) { + printf(" "); + for (x = 0; x < 8; ++x) { + int piece = pos->board[SQUARE_TO_NUM(x, y)]; + + if (piece == PIECE_EMPTY) { + if (SQUARE_TO_NUM(x, y) == pos->ep_square) { + printf("x"); + } else { + printf(" "); + } + } else { + putchar(piece_to_char(pos->board[SQUARE_TO_NUM(x, y)])); + } + } + printf("\n"); + } + + if (pos->white_to_move) { + printf("White to move\n"); + } else { + printf("Black to move\n"); + } + +#if 0 + { + unsigned i; + printf("Black pieces:"); + for (i = 0; i < 16; ++i) { + int type = pos->black_pieces[i].type; + int square = pos->black_pieces[i].square; + if (type != PIECE_EMPTY) + printf(" %c%u(%c)", "abcdefgh"[NUM_TO_FILE(square)], NUM_TO_RANK(square) + 1, piece_to_char(type)); + } + printf("\n"); + } +#endif + + printf("\nStatic evaluation: %.2f\n", 0.01f * evaluate(pos)); +} + +void real_make_move(struct position *pos, unsigned from, unsigned to, struct piece *from_ptr, struct piece *to_ptr) +{ + unsigned piece = pos->board[from]; + unsigned new_ep_square = 0; + + validate_position(pos); + + if (pos->board[to] != PIECE_EMPTY) { + // capture + to_ptr = &to_ptr[FIND_INDEX(pos->board[to])]; + to_ptr->type = PIECE_EMPTY; + to_ptr->square = 0; + + // see if the rook was captured + if (to == 28) + pos->wc_short = false; + else if (to == 21) + pos->wc_long = false; + else if (to == 98) + pos->bc_short = false; + else if (to == 91) + pos->bc_long = false; + } + + // update castling, and possibly castle + if (MAKE_COLORLESS(piece) == PIECE_KING) { + if (IS_WHITE(piece)) { + // whoa, hardcoded =) + if (from == 25 && to == 27) { + assert(from_ptr[3].square == 28); + from_ptr[3].square = 26; + pos->board[26] = pos->board[28]; + pos->board[28] = PIECE_EMPTY; + } else if (from == 25 && to == 23) { + assert(from_ptr[2].square == 21); + from_ptr[2].square = 24; + pos->board[24] = pos->board[21]; + pos->board[21] = PIECE_EMPTY; + } + + pos->wc_short = pos->wc_long = false; + } else { + if (from == 95 && to == 97) { + assert(from_ptr[3].square == 98); + from_ptr[3].square = 96; + pos->board[96] = pos->board[98]; + pos->board[98] = PIECE_EMPTY; + } else if (from == 95 && to == 93) { + assert(from_ptr[2].square == 91); + from_ptr[2].square = 94; + pos->board[94] = pos->board[91]; + pos->board[91] = PIECE_EMPTY; + } + + pos->bc_short = pos->bc_long = false; + } + } else if (MAKE_COLORLESS(piece) == PIECE_ROOK) { + if (IS_WHITE(piece)) { + if (from == 28) + pos->wc_short = false; + else if (from == 21) + pos->wc_long = false; + } else { + if (from == 98) + pos->bc_short = false; + else if (from == 91) + pos->bc_long = false; + } + } + + // en passant and promotion handling + if (MAKE_COLORLESS(piece) == PIECE_PAWN) { + if (to == pos->ep_square) { + // en passant capture + if (IS_WHITE(piece)) { + to_ptr = &to_ptr[FIND_INDEX(pos->board[to - 10])]; + pos->board[to - 10] = PIECE_EMPTY; + } else { + to_ptr = &to_ptr[FIND_INDEX(pos->board[to + 10])]; + pos->board[to + 10] = PIECE_EMPTY; + } + to_ptr->type = PIECE_EMPTY; + to_ptr->square = 0; + } else if (abs(to - from) == 20) { + // double move + if (IS_WHITE(piece)) { + new_ep_square = to - 10; + } else { + new_ep_square = to + 10; + } + } else if (NUM_TO_RANK(to) == 0 || NUM_TO_RANK(to) == 7) { + // promotion + from_ptr->type = PIECE_QUEEN; + piece = (piece & 0xf8) | PIECE_QUEEN; + } + } + + // move the piece + from_ptr->square = to; + + // and update the board + pos->board[to] = piece; + pos->board[from] = PIECE_EMPTY; + pos->ep_square = new_ep_square; + + pos->white_to_move = !pos->white_to_move; + + validate_position(pos); +} + +// not used in the move generator, real_make_move() is what's used there +void make_move(struct position *pos, unsigned from, unsigned to) +{ + struct piece *from_ptr, *to_ptr; + + validate_position(pos); + + if (IS_WHITE(pos->board[from])) { + from_ptr = pos->white_pieces; + to_ptr = pos->black_pieces; + } else { + from_ptr = pos->black_pieces; + to_ptr = pos->white_pieces; + } + + from_ptr = &from_ptr[FIND_INDEX(pos->board[from])]; + real_make_move(pos, from, to, from_ptr, to_ptr); +} + diff --git a/position.h b/position.h new file mode 100644 index 0000000..23c0c14 --- /dev/null +++ b/position.h @@ -0,0 +1,75 @@ +#ifndef _POSITION_H +#define _POSITION_H 1 + +#include + +/* + * 12x10 board notation: + * + * xx xx xx xx xx xx xx xx xx xx + * xx xx xx xx xx xx xx xx xx xx + * xx a1 b1 c1 d1 e1 f1 g1 h1 xx + * xx a2 b2 c2 d2 e2 f2 g2 h2 xx + * xx a3 b3 c3 d3 e3 f3 g3 h3 xx + * xx a4 b4 c4 d4 e4 f4 g4 h4 xx + * xx a5 b5 c5 d5 e5 f5 g5 h5 xx + * xx a6 b6 c6 d6 e6 f6 g6 h6 xx + * xx a7 b7 c7 d7 e7 f7 g7 h7 xx + * xx a8 b8 c8 d8 e8 f8 g8 h8 xx + * xx xx xx xx xx xx xx xx xx xx + * xx xx xx xx xx xx xx xx xx xx + * + * Lower three bits (0x07) encode piece type, fourth bit (0x08) color, + * upper four bits (0xf0) the piece index number. + */ +#define SQUARE_TO_NUM(file, rank) ((file) + (rank) * 10 + 21) +#define NUM_TO_FILE(x) ((x-1) % 10) /* -1 might be faster than -21 */ +#define NUM_TO_RANK(x) ((x-21) / 10) + +#define NUM_PIECES 8 +#define NUM_SQUARES (12*10) + +#define PIECE_EMPTY 0 +#define PIECE_PAWN 1 +#define PIECE_KNIGHT 2 +#define PIECE_KING 3 +#define PIECE_INVALID 4 +#define PIECE_BISHOP 5 +#define PIECE_ROOK 6 +#define PIECE_QUEEN 7 + +#define IS_WHITE(x) (((x) & 0x08) == 0) +#define IS_BLACK(x) (((x) & 0x08) != 0) + +#define SAME_COLOR(x,y) ((((x)^(y)) & 0x08) == 0) +#define OPPOSITE_COLOR(x,y) ((((x)^(y)) & 0x08) != 0) +#define CAN_GOTO(x,y) ((y) == PIECE_EMPTY || ((y) != PIECE_INVALID && OPPOSITE_COLOR((x),(y)))) + +#define MAKE_WHITE(x) ((x) & 0x07) +#define MAKE_BLACK(x) ((x) | 0x08) +#define MAKE_COLORLESS(x) ((x) & 0x07) +#define FIND_INDEX(x) (((x) & 0xf0) >> 4) + +#define SLIDES_STRAIGHT(x) (((x) & 0x06) == 0x06) +#define SLIDES_DIAGONALLY(x) (((x) & 0x05) == 0x05) + +struct piece { + unsigned char type; // colorless + unsigned char square; +}; +struct position { + signed char board[NUM_SQUARES]; + struct piece black_pieces[16], white_pieces[16]; + bool white_to_move; + bool wc_short, wc_long, bc_short, bc_long; + unsigned char ep_square; // 0 if none +}; + +void init_position(struct position *pos); +void validate_position(const struct position * const pos); +char piece_to_char(int piece); +void print_position(struct position *pos); +void real_make_move(struct position *pos, unsigned from, unsigned to, struct piece *from_ptr, struct piece *to_ptr); +void make_move(struct position *pos, unsigned from, unsigned to); + +#endif /* !defined(_POSITION_H) */ diff --git a/stupid.c b/stupid.c new file mode 100644 index 0000000..0c4c28f --- /dev/null +++ b/stupid.c @@ -0,0 +1,742 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "common.h" +#include "hash.h" +#include "evaluator.h" + +FILE *ucilog; + +unsigned total_nodes, min_depth; +unsigned move_num; + +struct killer_move killer_moves[64][2]; // two for each depth +unsigned killer_currdepth; // easier to have as a global :-/ +unsigned max_depth, max_selective_depth; // my oh my +bool abort_search; + +int find_best_move(const struct position * const pos, unsigned long long phash, unsigned *ret_from, unsigned *ret_to, unsigned depth, unsigned seldepth, int alpha, int beta, bool search_castling); + +void uciprintf(const char *format, ...) +{ + va_list ap; + char buf[4096]; + + va_start(ap, format); + vsnprintf(buf, 4096, format, ap); + va_end(ap); + + fputs(buf, stdout); + fputs("=> ", ucilog); + fputs(buf, ucilog); + + fflush(stdout); + fflush(ucilog); +} + +int estimate_score(struct position *pos, unsigned depth) +{ + unsigned long long phash, bucket; + struct hash_entry *he; + + // hack -- looking up the hash table is too expensive just to get + // a good estimate, so we don't do it except at a certain level + if (depth > 3) { + bool found_any = false; + unsigned best_depth = 10000; + int best_depth_score; + + // see if we have something in the hash -- we don't really care at what + // depth, _anything_ is better than the static evaluation, really + phash = hash_position(pos); + bucket = phash % HASH_BUCKETS; + he = transposition_table[bucket]; + + while (he != NULL) { + if (he->phash == phash) + return he->score; + + if (he->phash == phash && he->depth < best_depth) { + found_any = true; + best_depth = he->depth; + best_depth_score = he->score; + } + he = he->next; + } + + if (found_any) + return best_depth_score; + } + + return (pos->white_to_move) ? evaluate(pos) : -evaluate(pos); +} + +#define ADD_MOVE(newsquare) \ + do { \ + assert(IS_WHITE(pos->board[square]) == pos->white_to_move); \ + moves[num_moves].pos = *pos; \ + moves[num_moves].from = square; \ + moves[num_moves].to = newsquare; \ + if (pos->white_to_move) \ + real_make_move(&moves[num_moves].pos, square, newsquare, &moves[num_moves].pos.white_pieces[i], moves[num_moves].pos.black_pieces); \ + else \ + real_make_move(&moves[num_moves].pos, square, newsquare, &moves[num_moves].pos.black_pieces[i], moves[num_moves].pos.white_pieces); \ + moves[num_moves].estimate_score = -estimate_score(&moves[num_moves].pos, depth); \ + indexes[num_moves] = num_moves; \ + heapify(moves, indexes, num_moves); \ + ++num_moves; \ + } while (0) + +struct binheap_node { + int estimate_score; + struct position pos; + unsigned char from, to; +}; + +bool bh_greaterthan(struct binheap_node *moves, unsigned *indexes, unsigned i1, unsigned i2) +{ + bool killer1 = (killer_moves[killer_currdepth][0].from == moves[indexes[i1]].from && + killer_moves[killer_currdepth][0].to == moves[indexes[i1]].to) || + (killer_moves[killer_currdepth][1].from == moves[indexes[i1]].from && + killer_moves[killer_currdepth][1].to == moves[indexes[i1]].to); + bool killer2 = (killer_moves[killer_currdepth][0].from == moves[indexes[i2]].from && + killer_moves[killer_currdepth][0].to == moves[indexes[i2]].to) || + (killer_moves[killer_currdepth][1].from == moves[indexes[i2]].from && + killer_moves[killer_currdepth][1].to == moves[indexes[i2]].to); + + if (killer1 && !killer2) + return true; + if (killer2 && !killer1) + return false; + + return (moves[indexes[i1]].estimate_score > moves[indexes[i2]].estimate_score); +} + +void heapify(struct binheap_node *moves, unsigned *indexes, unsigned i) +{ + unsigned parent; + + if (i == 0) + return; + + parent = (i-1)/2; + if (bh_greaterthan(moves, indexes, i, parent)) { + unsigned tmp = indexes[i]; + indexes[i] = indexes[parent]; + indexes[parent] = tmp; + + heapify(moves, indexes, parent); + } +} + +void downheapify(struct binheap_node *moves, unsigned *indexes, unsigned i, unsigned num_elem) +{ + unsigned child1 = 2 * i + 1; + unsigned child2 = 2 * i + 2; + unsigned compare_ind; + + // no children + if (child1 >= num_elem) + return; + + if (child2 >= num_elem) { + // one child + compare_ind = child1; + } else { + // two children -- find the largest one + if (bh_greaterthan(moves, indexes, child1, child2)) { + compare_ind = child1; + } else { + compare_ind = child2; + } + } + + // see if we should swap + if (bh_greaterthan(moves, indexes, compare_ind, i)) { + unsigned tmp = indexes[i]; + indexes[i] = indexes[compare_ind]; + indexes[compare_ind] = tmp; + + downheapify(moves, indexes, compare_ind, num_elem); + } +} + +// generate all possible moves, stick them in a binary heap based on estimated score, and then try +// them in the estimated order +int find_best_move(const struct position * const pos, unsigned long long phash, unsigned *ret_from, unsigned *ret_to, unsigned depth, unsigned seldepth, int alpha, int beta, bool search_castling) +{ + unsigned i; + const struct piece * const ptr = (pos->white_to_move) ? pos->white_pieces : pos->black_pieces; + int score; + unsigned best_from = 21, best_to = 21; // a1-a1 (easy to pick out visually) + + struct binheap_node moves[128]; // should be plenty? + unsigned indexes[128]; // much cheaper to move around + unsigned num_moves = 0; + + assert(depth > 0); + + if (abort_search) + return 0; + if (depth + seldepth < min_depth) + min_depth = depth + seldepth; + + // see if we can find this position in our hash tables + if (lookup_hash(pos, phash, depth, seldepth, ret_from, ret_to, &score)) { + return score; + } + + killer_currdepth = depth + seldepth; + + for (i = 0; i < 16; ++i) { + unsigned piece, type, square; + + type = ptr[i].type; // without color + if (type == PIECE_EMPTY) + continue; + + square = ptr[i].square; + piece = pos->board[square]; // with color + + if (type == PIECE_PAWN) { + int pawn_step = IS_WHITE(piece) ? 10 : -10; + + // could it move forwards one step? + if (pos->board[ptr[i].square + pawn_step] == PIECE_EMPTY) { + ADD_MOVE(square + pawn_step); + + // so that's OK, what about two? + if (pos->board[square + pawn_step * 2] == PIECE_EMPTY && + ((IS_WHITE(piece) && NUM_TO_RANK(square) == 1) || + (IS_BLACK(piece) && NUM_TO_RANK(square) == 6))) { + ADD_MOVE(square + pawn_step * 2); + } + } + + // could it capture left? + if ((pos->board[square + pawn_step - 1] == PIECE_EMPTY && (square + pawn_step - 1 == pos->ep_square)) || + (pos->board[square + pawn_step - 1] != PIECE_EMPTY && NUM_TO_FILE(square) != 0 && OPPOSITE_COLOR(piece, pos->board[square + pawn_step - 1]))) { + ADD_MOVE(square + pawn_step - 1); + } + + // could it capture right? + if ((pos->board[square + pawn_step + 1] == PIECE_EMPTY && (square + pawn_step + 1 == pos->ep_square)) || + (pos->board[square + pawn_step + 1] != PIECE_EMPTY && NUM_TO_FILE(square) != 7 && OPPOSITE_COLOR(piece, pos->board[square + pawn_step + 1]))) { + ADD_MOVE(square + pawn_step + 1); + } + + continue; + } + + if (type == PIECE_KNIGHT) { + // these are all the possible knight moves + if (CAN_GOTO(piece, pos->board[square + 12])) + ADD_MOVE(square + 12); + if (CAN_GOTO(piece, pos->board[square - 12])) + ADD_MOVE(square - 12); + if (CAN_GOTO(piece, pos->board[square - 21])) + ADD_MOVE(square - 21); + if (CAN_GOTO(piece, pos->board[square + 21])) + ADD_MOVE(square + 21); + if (CAN_GOTO(piece, pos->board[square + 19])) + ADD_MOVE(square + 19); + if (CAN_GOTO(piece, pos->board[square - 19])) + ADD_MOVE(square - 19); + if (CAN_GOTO(piece, pos->board[square + 8])) + ADD_MOVE(square + 8); + if (CAN_GOTO(piece, pos->board[square - 8])) + ADD_MOVE(square - 8); + + continue; + } + + if (type == PIECE_KING) { + // these are all the possible king moves + if (CAN_GOTO(piece, pos->board[square + 1])) + ADD_MOVE(square + 1); + if (CAN_GOTO(piece, pos->board[square - 1])) + ADD_MOVE(square - 1); + if (CAN_GOTO(piece, pos->board[square + 11])) + ADD_MOVE(square + 11); + if (CAN_GOTO(piece, pos->board[square - 11])) + ADD_MOVE(square - 11); + if (CAN_GOTO(piece, pos->board[square + 10])) + ADD_MOVE(square + 10); + if (CAN_GOTO(piece, pos->board[square - 10])) + ADD_MOVE(square - 10); + if (CAN_GOTO(piece, pos->board[square + 9])) + ADD_MOVE(square + 9); + if (CAN_GOTO(piece, pos->board[square - 9])) + ADD_MOVE(square - 9); + + // evaluate if white can castle or not; quite ugly, but OK + if (search_castling) { + bool c_short, c_long; + if (pos->white_to_move) { + c_short = pos->wc_short; + c_long = pos->wc_long; + } else { + c_short = pos->bc_short; + c_long = pos->bc_long; + } + + if (pos->board[square + 1] != PIECE_EMPTY || + pos->board[square + 2] != PIECE_EMPTY) + c_short = false; + if (pos->board[square - 1] != PIECE_EMPTY || + pos->board[square - 2] != PIECE_EMPTY || + pos->board[square - 3] != PIECE_EMPTY || + pos->board[square - 4] != PIECE_EMPTY) + c_long = false; + + if (c_short || c_long) { + struct position npos = *pos; + npos.white_to_move = !npos.white_to_move; + npos.ep_square = 0; + + // score -20000 => our king is in check + score = find_best_move(&npos, hash_position(&npos), NULL, NULL, 1, 0, -40000, 40000, false); + + if (score >= 14500) + continue; + + if (c_short) { + // check if the middle square is in check + npos = *pos; + if (pos->white_to_move) + real_make_move(&npos, square, square + 1, &npos.white_pieces[i], npos.black_pieces); + else + real_make_move(&npos, square, square + 1, &npos.black_pieces[i], npos.white_pieces); + score = find_best_move(&npos, hash_position(&npos), NULL, NULL, 1, 0, -40000, 40000, false); + + if (score < 14500) + ADD_MOVE(square + 2); + } + if (c_long) { + // check if the middle square is in check + npos = *pos; + if (pos->white_to_move) + real_make_move(&npos, square, square - 1, &npos.white_pieces[i], npos.black_pieces); + else + real_make_move(&npos, square, square - 1, &npos.black_pieces[i], npos.white_pieces); + score = find_best_move(&npos, hash_position(&npos), NULL, NULL, 1, 0, -40000, 40000, false); + + if (score < 14500) + ADD_MOVE(square - 2); + } + } + } + + continue; + } + + if (SLIDES_STRAIGHT(type)) { + // slide to the right for as long we can + int nsq = square + 1; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + ++nsq; + } + + // to the left + nsq = square - 1; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + --nsq; + } + + // up + nsq = square + 10; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + nsq += 10; + } + + // and down + nsq = square - 10; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + nsq -= 10; + } + } + + if (SLIDES_DIAGONALLY(type)) { + // slide to the upper-right for as long as we can + int nsq = square + 11; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + nsq += 11; + } + + // to the upper-left + nsq = square + 9; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + nsq += 9; + } + + // lower-right + nsq = square - 9; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + nsq -= 9; + } + + // and lower-left + nsq = square - 11; + for ( ;; ) { + if (CAN_GOTO(piece, pos->board[nsq])) + ADD_MOVE(nsq); + if (pos->board[nsq] != PIECE_EMPTY) + break; + nsq -= 11; + } + } + } + + // null-move heuristic + if (depth > 6) { + struct position npos = *pos; + unsigned long long nphash; + npos.white_to_move = !npos.white_to_move; + npos.ep_square = 0; + + nphash = hash_position(&npos); + score = -find_best_move(&npos, nphash, NULL, NULL, depth - 1, seldepth, alpha, beta, true); + + if (score > alpha) { + alpha = score; + best_from = moves[indexes[0]].from; + best_to = moves[indexes[0]].to; + + if (alpha >= beta) + goto early_exit; + } + } + + // now go through all the moves + while (num_moves > 0) { + unsigned tmp; + const struct position * const npos = &moves[indexes[0]].pos; + unsigned long long nphash; + + /* + * If this move estimated way too good score, it means we just captured + * the king, and this position is definitely not legal. Stop the search, + * since there's no point of searching illegal positions. + */ + if (moves[indexes[0]].estimate_score < -15000) { + alpha = -15000 + (max_depth + max_selective_depth - depth - seldepth); + best_from = moves[indexes[0]].from; + best_to = moves[indexes[0]].to; + + killer_moves[depth][phash & 1].from = best_from; + killer_moves[depth][phash & 1].to = best_to; + + goto early_exit; + } + if (moves[indexes[0]].estimate_score > 15000) { + alpha = 15000 - (max_depth + max_selective_depth - depth - seldepth); + best_from = moves[indexes[0]].from; + best_to = moves[indexes[0]].to; + + killer_moves[depth][phash & 1].from = best_from; + killer_moves[depth][phash & 1].to = best_to; + + goto early_exit; + } + + nphash = hash_position(&moves[indexes[0]].pos); + if (lookup_record(nphash) >= 1) { + // ouch, move repetition, it's going to be a draw + score = -50; + } else if (depth == 1) { + // terminal node: static evaluation + score = (pos->white_to_move) ? evaluate(npos) : -evaluate(npos); + } else { + // non-terminal node: consider the opponent's best move + + // if we're close to the end, and this is a capture, make a move extension + if (depth <= 1 && seldepth > 0 && pos->board[moves[indexes[0]].to] != PIECE_EMPTY) + score = -find_best_move(npos, nphash, NULL, NULL, depth, seldepth - 1, -beta, -alpha, true); + else + score = -find_best_move(npos, nphash, NULL, NULL, depth - 1, seldepth, -beta, -alpha, true); + } + + if (score > alpha) { + alpha = score; + best_from = moves[indexes[0]].from; + best_to = moves[indexes[0]].to; + + if (alpha >= beta) { + // replace a random killer move + killer_moves[depth][phash & 1].from = best_from; + killer_moves[depth][phash & 1].to = best_to; + + goto early_exit; + } + } + + // swap this element with the last one + tmp = indexes[num_moves - 1]; + indexes[num_moves - 1] = indexes[0]; + indexes[0] = tmp; + --num_moves; + + downheapify(moves, indexes, 0, num_moves); + } + + if ((best_from != 21 || best_to != 21) && search_castling) + insert_hash(pos, phash, depth, seldepth, best_from, best_to, alpha); + +early_exit: + if (ret_from) + *ret_from = best_from; + if (ret_to) + *ret_to = best_to; + return alpha; +} + +void alarm_sounded(int signal) +{ + abort_search = true; + fprintf(ucilog, "Aborting search due to signal %u\n", signal); +} + +void ai_move(struct position *pos, unsigned think_time) +{ + unsigned from, to, best_from, best_to; + int score, depth, seldepth; + struct timeval think_start, now; + + total_nodes = 0; + gettimeofday(&think_start, NULL); + + depth = 2; + seldepth = depth; + clear_hash(); + + signal(SIGALRM, alarm_sounded); + alarm(think_time); + abort_search = false; + + for ( ;; ) { + struct position npos; + int pdepth = depth; + double time_spent; + + // set the globals + max_depth = depth; + max_selective_depth = seldepth; + + //fprintf(stderr, "\n\n\nThinking at depth %u:\n\n", depth); + min_depth = depth + seldepth; + score = find_best_move(pos, hash_position(pos), &from, &to, depth, seldepth, -40000, 40000, true); + + if (abort_search) + break; + + best_from = from; + best_to = to; + + gettimeofday(&now, NULL); + time_spent = (now.tv_sec - think_start.tv_sec) + + 1e-6 * (now.tv_usec - think_start.tv_usec); + + uciprintf("info depth %u seldepth %u score cp %d time %u hashfull %u nodes %u nps %u pv", + depth, depth + seldepth - min_depth + 1, score, + (unsigned)(time_spent * 1000.0), + 100 * hash_used / HASH_MAX_ELEMS, + total_nodes, (unsigned)(total_nodes / time_spent + 0.5)); + uciprintf(" %c%u%c%u", + "abcdefgh"[NUM_TO_FILE(from)], NUM_TO_RANK(from) + 1, + "abcdefgh"[NUM_TO_FILE(to)], NUM_TO_RANK(to) + 1); + + // reconstruct the pv (hopefully from the hash table!) + npos = *pos; + make_move(&npos, from, to); + + while (pdepth > 1) { + unsigned pvf, pvt; + + --pdepth; + find_best_move(&npos, hash_position(&npos), &pvf, &pvt, pdepth, seldepth, -40000, 40000, true); + + uciprintf(" %c%u%c%u", + "abcdefgh"[NUM_TO_FILE(pvf)], NUM_TO_RANK(pvf) + 1, + "abcdefgh"[NUM_TO_FILE(pvt)], NUM_TO_RANK(pvt) + 1); + + //print_position(&npos); + make_move(&npos, pvf, pvt); + } + + uciprintf("\n"); + fflush(stdout); + + // this was a much better idea before we had selective search :-) +#if 0 + if (score > 15000 || score < -15000) + break; +#endif + + if (seldepth < depth * 2) + seldepth += (depth+1)/2; + else { + ++depth; + seldepth = depth; + } + } + + make_move(pos, best_from, best_to); + + uciprintf("bestmove %c%u%c%u\n", + "abcdefgh"[NUM_TO_FILE(best_from)], NUM_TO_RANK(best_from) + 1, + "abcdefgh"[NUM_TO_FILE(best_to)], NUM_TO_RANK(best_to) + 1); + fflush(stdout); +} + +int main(void) +{ + struct position curr_pos; + ucilog = fopen("ucilog.txt", "w"); + + move_num = 0; + + init_evaluator(); + init_hash(); + + for ( ;; ) { + char buf[4096], *ptr; + fgets(buf, 4096, stdin); + + // strip newlines + ptr = strchr(buf, '\n'); + if (ptr != NULL) + *ptr = 0; + + ptr = strchr(buf, '\r'); + if (ptr != NULL) + *ptr = 0; + + fprintf(ucilog, "<= %s\n", buf); + fflush(ucilog); + + if (strcmp(buf, "uci") == 0) { + uciprintf("id name stupid\n"); + uciprintf("id author Steinar H. Gunderson\n"); + uciprintf("uciok\n"); + fflush(stdout); + continue; + } + if (strcmp(buf, "isready") == 0) { + uciprintf("readyok\n"); + fflush(stdout); + continue; + } + if (strcmp(buf, "ucinewgame") == 0) { + // TODO: clear history and possibly pawn structure stuff? + continue; + } + if (strncmp(buf, "position", 8) == 0) { + ptr = buf + 9; + if (strncmp(ptr, "startpos", 8) == 0) { + init_position(&curr_pos); + ptr += 9; + } + if (strncmp(ptr, "fen", 3) == 0) { + // no fen handling yet + ptr = strchr(ptr, ' ') + 1; + } + if (strncmp(ptr, "moves", 5) == 0) { + ptr = strchr(ptr, ' '); + while (ptr != NULL) { + unsigned from_file, from_rank, to_file, to_rank; + from_file = tolower(ptr[1]) - 'a'; + from_rank = ptr[2] - '1'; + to_file = tolower(ptr[3]) - 'a'; + to_rank = ptr[4] - '1'; + + make_move(&curr_pos, SQUARE_TO_NUM(from_file, from_rank), SQUARE_TO_NUM(to_file, to_rank)); + record_move(&curr_pos); + ++move_num; + ptr = strchr(ptr + 1, ' '); + } + } + continue; + } + if (strncmp(buf, "go", 2) == 0) { + // see if there's a clock for us -- if not, use ten seconds + unsigned thinking_time = 10; + + if (curr_pos.white_to_move) + ptr = strstr(buf, "wtime "); + else + ptr = strstr(buf, "btime "); + + if (ptr != NULL) { + unsigned total_ms = atoi(ptr + 6); + unsigned moves = 40; + ptr = strstr(buf, "movestogo "); + if (ptr != NULL) + moves = atoi(ptr + 10); + + thinking_time = ((total_ms - 5000) / (moves + 2) + 500) / 1000; + + // also allocate 90% of the increment, if there's any + if (curr_pos.white_to_move) + ptr = strstr(buf, "winc "); + else + ptr = strstr(buf, "binc "); + if (ptr != NULL) + thinking_time += atoi(ptr + 5) * 9 / 10000; + + if (thinking_time < 1) + thinking_time = 1; + + fprintf(ucilog, "Allocating %u seconds to think for this move.\n", thinking_time); + } + + ai_move(&curr_pos, thinking_time); + record_move(&curr_pos); + ++move_num; + continue; + } + + fprintf(ucilog, "Unknown UCI command '%s'!\n", buf); + fflush(ucilog); + } + + exit(0); +}