From 5fed4d946f3a347713e604fe009a17952b90da76 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Tue, 22 Jan 2013 17:18:14 +0100 Subject: [PATCH 1/1] Initial checkin for move to Git (no prior version history available). --- common.h | 15 ++ evaluator.c | 343 ++++++++++++++++++++++++ evaluator.h | 9 + hash.c | 240 +++++++++++++++++ hash.h | 50 ++++ position.c | 364 ++++++++++++++++++++++++++ position.h | 75 ++++++ stupid.c | 742 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 1838 insertions(+) create mode 100644 common.h create mode 100644 evaluator.c create mode 100644 evaluator.h create mode 100644 hash.c create mode 100644 hash.h create mode 100644 position.c create mode 100644 position.h create mode 100644 stupid.c 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); +} -- 2.39.2