--- /dev/null
+#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) */
--- /dev/null
+#include <stdlib.h>
+#include <assert.h>
+#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;
+}
+
--- /dev/null
+#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) */
--- /dev/null
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+#include <sys/time.h>
+#include <ctype.h>
+#include <math.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#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) */
--- /dev/null
+#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
--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#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);
+}
+
--- /dev/null
+#ifndef _POSITION_H
+#define _POSITION_H 1
+
+#include <stdbool.h>
+
+/*
+ * 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) */
--- /dev/null
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+#include <sys/time.h>
+#include <ctype.h>
+#include <math.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <unistd.h>
+#include <stdarg.h>
+#include <signal.h>
+
+#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);
+}
projects / stupid / commitdiff