Terra Help and Information

bullet1 Help!

bullet2 Hash Tables

bullet3 What is hash tables

A hash table is a way to store things in memory with fast access. In order to have an effective hash table one need a good Key. The key is ideally unique for each element in the table and is used to compute the exact index or address to the wanted table item. To find an algorithm that gives unique keys and indices for each of the table items and to handle collisions is a science itself. Often the case is that the hash table is smaller than than the number of items to store and then you have to use some kind of priority scheme to decide which item to keep and which to drop. The chess program hash tables has all the above attributes.

bullet3 Terra's Hash tables

Four types of hash tables are used in Terra. The main table is the really memory consuming one. The others are much smaller.

  • Main Hash table
    During the search Terra will reach x positions/sec. On my P4 2540 MHz that is about 700000 positions/sec. This is far away from the normal human thinking procedure and most of the positions reached in the search tree are really weird and would not occupy normal peoples mind!

    There are mainly 2 reasons why hash tables are useful in chess programs:

    1. Fact is that the same position will show up in different places during the search due to different move series leading to the same position. This is very common.
    2. Another reason why the same position is revisited many times is the 'iterative search' heuristic used by most of todays chess programs.The program first search 1 ply deep, after that the same search 2 ply deep and 3 ply and 4 ply etc. (ply is one move from white or black). It seems ridiculous at first sight but it is effective for reasons not described here.

    By storing positions in the hash tables it is possible to reuse earlier computed best answer and/or evaluation value for that position.

    The hash key is computed right out of the position and translated into an index to the hash table. A lot of collisions will occur but in these cases the program just will continues the search as nothing happened. The bigger hash table we have the fewer collisions will occur.

    Even opening books can use the same hash keys to store and find stored opening moves in the book file.

    Read about how to set hash table parameters .


     
  • Other hash tables
    Except for the main hash table Terra is using 3 other types of hash tables for different reasons all indexed by the same or a similar key as the main hash table. Their size can be individually set  by the user but it's better to let Terra decide by itself how to use it's storage and just enter the total size available.

    Read more about setting hash table parameters .



     

bullet3 How to set Hash tables

The parameters in Terra.ini:

Parameter
Recommended Value
Hash=0 or 1
1 (you should never use 0 for normal play unless testing purposes)
Evalhash=0 or 1
1 (you should never use 0 for normal play unless testing purposes)
Hashsize=h [x y z]
hash size in bytes (or Kilobytes if the figure is immediately followed by K or Megabytes if the figure is immediately followed by M).
Recommended:
Give only one value. It will be used as the total hash size and be automatically distributed among the different hashtables used. Example:
Hashsize 14M
will allocate in total 14 Mb for all 4 hash tables with the distribution best fit for Terra.
Otherwise you have to enter all 4 values:
Hashsize 7M 4M 2M 700K
will allocate 7 Mb for the main hash table, 4 Mb for hash table2, 2M for hash table3 and 700 Kb for hash table4.


The same with commands:

Command
Recommended Value
Hash on/off
on
Evalhash on/off
on
Hashsize h [x y z]
see above.


A few more words about how to control the size of hash tables in Terra

The hash table size is no longer constrained to some fixed values. More is better in any time control and on any machine. There is just one important issue to deal with. If the total size for hash tables, EGTB cashe and internal tables exceeds what is available on your machine Windows will start to swap memory with the hard disk and this is a disaster for a chess program! You will notice how the Nodes/second figure becomes lower because the programs time will be occupied by waiting for Windows reading and writing memory to and from the harddisk. If you notice the harddisk working heavily this is probably the reason.

There is no reason trying to be as close to the limits as possible, the gain is very small. Better to keep a fairly good marginal up to what you think is the maximum available RAM. Don't forget that Windows and other programs also occupies quite a lot of RAM.

Please give your comments in WinBoard Forum or email me. This document was updated 2004-08-02.