www.delorie.com/gnu/docs/gnugo/gnugo_172.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

14.2.3 Hash Structures

The basic hash structures are declared in `engine/hash.h' and `engine/cache.c'

 
typedef struct hashposition_t {
  Compacttype  board[COMPACT_BOARD_SIZE];
  int          ko_pos;
} Hashposition;

Represents the board and optionally the location of a ko, which is an illegal move. The player whose move is next is not recorded.

 
typedef struct {
  Hashvalue     hashval;
  Hashposition  hashpos;
} Hash_data;

Represents the return value of a function (hashval) and the board state (hashpos).

 
typedef struct read_result_t {
  unsigned int data1;	
  unsigned int data2;

  struct read_result_t *next;
} Read_result;

The data1 field packs into 32 bits the following fields:

 
komaster:  2 bits (EMPTY, BLACK, WHITE, or GRAY)
kom_pos : 10 bits (allows MAX_BOARD up to 31)
routine :  4 bits (currently 10 different choices)
str1    : 10 bits
stackp  :  5 bits

The data2 field packs into 32 bits the following fields:

 
status :   2 bits (0 free, 1 open, 2 closed)
result1:   4 bits
result2:   4 bits
move   :  10 bits
str2   :  10 bits

The komaster and (kom_pos) field are documented in See section 14.3 Ko Handling.

When a new result node is created, 'status' is set to 1 'open'. This is then set to 2 'closed' when the result is entered. The main use for this is to identify open result nodes when the hashtable is partially cleared. Another potential use for this field is to identify repeated positions in the reading, in particular local double or triple kos.

 
typedef struct hashnode_t {
  Hash_data            key;
  Read_result        * results;
  struct hashnode_t  * next;
} Hashnode;

The hash table consists of hash nodes. Each hash node consists of The hash value for the position it holds, the position itself and the actual information which is purpose of the table from the start.

There is also a pointer to another hash node which is used when the nodes are sorted into hash buckets (see below).

 
typedef struct hashtable {
  size_t         hashtablesize;	/* Number of hash buckets */
  Hashnode    ** hashtable;	/* Pointer to array of hashnode lists */

  int            num_nodes;	/* Total number of hash nodes */
  Hashnode     * all_nodes;	/* Pointer to all allocated hash nodes. */
  int            free_node;	/* Index to next free node. */

  int            num_results;	/* Total number of results */
  Read_result  * all_results;	/* Pointer to all allocated results. */
  int            free_result;	/* Index to next free result. */
} Hashtable;

The hash table consists of three parts:


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003