Initial checkin for move to Git (no prior version history available). master
authorSteinar H. Gunderson <sgunderson@bigfoot.com>
Tue, 22 Jan 2013 16:18:14 +0000 (17:18 +0100)
committerSteinar H. Gunderson <sgunderson@bigfoot.com>
Tue, 22 Jan 2013 16:18:14 +0000 (17:18 +0100)
common.h [new file with mode: 0644]
evaluator.c [new file with mode: 0644]
evaluator.h [new file with mode: 0644]
hash.c [new file with mode: 0644]
hash.h [new file with mode: 0644]
position.c [new file with mode: 0644]
position.h [new file with mode: 0644]
stupid.c [new file with mode: 0644]

diff --git a/common.h b/common.h
new file mode 100644 (file)
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 (file)
index 0000000..f179f30
--- /dev/null
@@ -0,0 +1,343 @@
+#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;
+}
+
diff --git a/evaluator.h b/evaluator.h
new file mode 100644 (file)
index 0000000..4a67dd0
--- /dev/null
@@ -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 (file)
index 0000000..d061ec8
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,240 @@
+#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) */
diff --git a/hash.h b/hash.h
new file mode 100644 (file)
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 (file)
index 0000000..a3d24fb
--- /dev/null
@@ -0,0 +1,364 @@
+#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);
+}
+
diff --git a/position.h b/position.h
new file mode 100644 (file)
index 0000000..23c0c14
--- /dev/null
@@ -0,0 +1,75 @@
+#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) */
diff --git a/stupid.c b/stupid.c
new file mode 100644 (file)
index 0000000..0c4c28f
--- /dev/null
+++ b/stupid.c
@@ -0,0 +1,742 @@
+#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);
+}