book.c

一款运行在linux上的象棋游戏。用GTK/GNOME环境下用GLADE开发。

/* GNU Chess 5.0 - book.c - book code
   Copyright (c) 1999-2002 Free Software Foundation, Inc.

   GNU Chess is based on the two research programs 
   Cobalt by Chua Kong-Sian and Gazebo by Stuart Cracraft.

   GNU Chess is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   GNU Chess is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with GNU Chess; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.

   Contact Info: 
     [e-mail]
     [e-mail], [e-mail], [e-mail]
     [e-mail]
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>

#include "common.h"
#include "book.h"

#define MAXMOVES 200
#define MAXMATCH 100

static int bookcnt;
static HashType posshash[MAXMOVES];

/*
 * This is the only authoritative variable telling us
 * whether a book has been allocated or not. (Other
 * parts may mess around with bookloaded.)
 */
static int book_allocated = 0;

/*
 * The last byte of magic_str should be the version
 * number of the format, in case we have to change it.
 *
 * Format 0x01 had an index field which is now gone.
 *
 * Format 0x03 uses an additional size header, which 
 * comes directly after the magic string, and has the
 * number of entries as a big-endian encoded uint32_t
 * number. 
 */

#define MAGIC_LENGTH 5

static const char magic_str[] = "\x42\x23\x08\x15\x03";

static int check_magic(FILE *f)
{
  char buf[MAGIC_LENGTH];
  int r;

  r = fread(&buf, 1, MAGIC_LENGTH, f);
  return (r == MAGIC_LENGTH &&
	  memcmp(buf, magic_str, MAGIC_LENGTH) == 0);
}

static int write_magic(FILE *f)
{
  if (MAGIC_LENGTH != fwrite(&magic_str, 1, MAGIC_LENGTH, f)) {
    return BOOK_EIO;
  } else {
    return BOOK_SUCCESS;
  }
}

/* Write and read size information for the binary book */

static int write_size(FILE *f, uint32_t size)
{
  unsigned char sizebuf[4];
  int k;

  for (k = 0; k < 4; k++) {
    sizebuf[k] = (size >> ((3-k)*8)) & 0xff;
  }
  if (1 == fwrite(&sizebuf, sizeof(sizebuf), 1, f)) {
    return BOOK_SUCCESS;
  } else {
    return BOOK_EIO;
  }
}

/* Returns 0 if some read error occurs */

static uint32_t read_size(FILE *f)
{
  unsigned char sizebuf[4];
  uint32_t size = 0;
  int k;

  if (1 != fread(&sizebuf, sizeof(sizebuf), 1, f)) {
    return 0;
  }
  for (k = 0; k < 4; k++) {
    size = (size << 8) | sizebuf[k];
  }
  return size;
}

/*
 * We now allocate memory for the book dynamically,
 * according to the size field in the header of the binary
 * book. However, during book building the following value
 * is used.
 */

#define MAX_DIGEST_BITS 20

static int digest_bits;

#define DIGEST_SIZE (1UL << digest_bits)
#define DIGEST_MASK (DIGEST_SIZE - 1)

static struct hashtype {
  uint16_t wins;
  uint16_t losses;
  uint16_t draws;
  HashType key;
} *bookpos;

static inline int is_empty(uint32_t index)
{
  return 
    bookpos[index].key    == 0 &&
    bookpos[index].wins   == 0 &&
    bookpos[index].draws  == 0 &&
    bookpos[index].losses == 0;
}

/*
 * Initial hash function, relies on the quality of the lower
 * bits of the 64 bit hash function
 */
#define DIGEST_START(i,key) \
  ((i) = (key) & DIGEST_MASK)

/*
 * See if there is already a matching entry
 */
#define DIGEST_MATCH(i,the_key) \
  ((the_key) == bookpos[i].key)

/*
 * See if the entry is empty
 */
#define DIGEST_EMPTY(i) is_empty(i)

/*
 * Check for collision
 */
#define DIGEST_COLLISION(i,key) \
  (!DIGEST_MATCH(i,key) && !DIGEST_EMPTY(i))

/*
 * The next macro is used in the case of hash collisions.
 * We use double hashing with the higher bits of the key.
 * In order to have the shift relatively prime to the hash
 * size, we OR by 1.
 */
#define DIGEST_NEXT(i,key) \
  ((i) = ((i) + (((key) >> digest_bits) | 1)) & DIGEST_MASK)


/* Mainly for debugging purposes */
static int bookhashcollisions = 0;

/*
 * This is considered to be the limit for the hash, I chose
 * 95% because it is Monday... No, I am open for suggestions
 * for the right value, I just don't know.
 */
#define DIGEST_LIMIT (0.95 * DIGEST_SIZE)

/*
 * This is the record as it will be written in the binary
 * file in network byte order. HashType is uint64_t. To
 * avoid endianness and padding issues, we do not read or
 * write structs but put the values in an unsigned char array.
 */

static unsigned char buf[2+2+2+8];

/* Offsets */
static const int wins_off   = 0;
static const int losses_off = 2;
static const int draws_off  = 4;
static const int key_off    = 6;

static void buf_to_book(void)
{
  HashType key;
  uint32_t i;

  key = ((uint64_t)buf[key_off] << 56)
    | ((uint64_t)buf[key_off+1] << 48)
    | ((uint64_t)buf[key_off+2] << 40)
    | ((uint64_t)buf[key_off+3] << 32)
    | ((uint64_t)buf[key_off+4] << 24)
    | ((uint64_t)buf[key_off+5] << 16)
    | ((uint64_t)buf[key_off+6] << 8)
    | ((uint64_t)buf[key_off+7]);
  /*
   * This is an infinite loop if the hash is 100% full,
   * but other parts should check that this does not happen.
   */
  for (DIGEST_START(i, key);
       DIGEST_COLLISION(i, key);
       DIGEST_NEXT(i, key))
    /* Skip */
    bookhashcollisions++;

  bookpos[i].wins   += (buf[wins_off]   << 8) | buf[wins_off  +1];
  bookpos[i].draws  += (buf[draws_off]  << 8) | buf[draws_off +1];
  bookpos[i].losses += (buf[losses_off] << 8) | buf[losses_off+1];
  bookpos[i].key = key;
}

static void book_to_buf(uint32_t index)
{
  int k;

  for (k=0; k<2; k++) {
    buf[wins_off + k]   = ((bookpos[index].wins)   >> ((1-k)*8)) & 0xff;
    buf[draws_off + k]  = ((bookpos[index].draws)  >> ((1-k)*8)) & 0xff;
    buf[losses_off + k] = ((bookpos[index].losses) >> ((1-k)*8)) & 0xff;
  }
  for (k=0; k<8; k++) {
    buf[key_off + k] = ((bookpos[index].key) >> ((7-k)*8)) & 0xff;
  }
}

static int compare(const void *aa, const void *bb)
{
  const leaf *a = aa;
  const leaf *b = bb;
  
  if (b->score > a->score) return(1);
  else if (b->score < a->score) return(-1);
  else return(0);
}

/*
 * Reads an existing binary book from f. The header must
 * already be skipped, when you call this function. The
 * variable digest_bits must be set to the correct value
 * before calling this function. If any book was allocated
 * before, it will be lost.
 */
static int read_book(FILE *f)
{
  if (book_allocated) {
    free(bookpos);
    book_allocated = 0;
  }
  bookpos = calloc(DIGEST_SIZE, sizeof(struct hashtype));
  if (bookpos == NULL) {
    return BOOK_ENOMEM;
  }
  book_allocated = 1;
  bookcnt = 0;
  bookhashcollisions = 0;
  while ( 1 == fread(&buf, sizeof(buf), 1, f) ) {
    buf_to_book();
    bookcnt++;
  }
  return BOOK_SUCCESS;
}
  
/* 
 * Return values are defined in common.h
 */

int BookBuilderOpen(void)
{
  FILE *rfp, *wfp;
  int res;

  if ((rfp = fopen(BOOKRUN,"rb")) != NULL) {
    printf("Opened existing book!\n");
    if (!check_magic(rfp)) {
      fprintf(stderr, 
	      "File %s does not conform to the current format.\n"
	      "Consider rebuilding your book.\n",
	      BOOKRUN);
      return BOOK_EFORMAT;
    }
    /*
     * We have to read the size header, but in book building we
     * use the maximum-sized hash table, so we discard the value.
     */
    digest_bits = MAX_DIGEST_BITS;
    read_size(rfp);
    res = read_book(rfp);
    fclose(rfp);
    if (res != BOOK_SUCCESS) {
      fclose(rfp);
      return res;
    }
    printf("Read %d book positions\n", bookcnt);
    printf("Got %d hash collisions\n", bookhashcollisions);
  } else {
    wfp = fopen(BOOKRUN,"w+b");
    if (wfp == NULL) {
      fprintf(stderr, "Could not create %s file: %s\n",
		 BOOKRUN, strerror(errno));
      return BOOK_EIO;
    }
    if (write_magic(wfp) != BOOK_SUCCESS) {
      fprintf(stderr, "Could not write to %s: %s\n",
	      BOOKRUN, strerror(errno));
      return BOOK_EIO;
    }
    if (fclose(wfp) != 0) {
      fprintf(stderr, "Could not write to %s: %s\n",
	      BOOKRUN, strerror(errno));
      return BOOK_EIO;
    }
    printf("Created new book %s!\n", BOOKRUN);
    rfp = fopen(BOOKRUN, "rb");
    if (rfp == NULL) {
      fprintf(stderr, "Could not open %s for reading: %s\n",
	      BOOKRUN, strerror(errno));