Guide me through building a chess program

[Richard Allbert]

[jwes]

Nice Thanks Allbert and hgm.

I was reading Transposition table and Zobrist keys. Bruce Moreland, in his website, says to use [Zobristkey()%Table size] as index in an array. What size of array is he using?

Typically, this is a power of 2 and configurable by the user. 2^20 is a reasonable value.

In java there's Hashmap class for hash tables. But I feel that the get(key) function used to retrieve entries searches the table. If that's the case, then it would be very slow. So, do I use array for transposition table? Can anyone confirm if my fear is correct or not?

You use an array. Hashmap would be slow, but a bigger problem is that it would be automatically grown when it is nearly full.

Also it's said everywhere that lots of bugs creep in when implementing hash tables. I really wonder if it's worth the effort. How much important is TT for a chess program's performance?

It is very important. It is almost essential for move ordering, and can be very useful for blocked positions and endgames.

[Sapta]

It is very important. It is almost essential for move ordering, and can be very useful for blocked positions and endgames.

Ok, I have started coding for this. I am wondering about the random numbers needed to generate zobrist keys. Do i need to randomly generate them every time program starts? Or if I just copy values used by someone else that is alright?

[Richard Allbert]

It's better probably to write a small separate program that prints out an array of random numbers for you that you can paste into your program, so you can always use the same keys.

This will be useful later e.g when making an opening book indexed by hash keys.

[hgm]

It is simpler to generate them every time you start the program. You would only need one line of code for that, while the table is nearly thousand elements. By the time you need a fixed set of keys to communicate with the outside world, you can aways switch to an initialized table.

In the latter case, I would recommend using the table defined in the Polygot book format: then you could use the key not only to access books of your own, but also to access books in Polyglot format. (So you could use polyglot as a tool to prepare your books.)

[Sapta]

It is simpler to generate them every time you start the program. You would only need one line of code for that, while the table is nearly thousand elements. By the time you need a fixed set of keys to communicate with the outside world, you can aways switch to an initialized table.

Ok, I am creating all the values, but you said the table would have "nearly thousand elements" whereas JWC said, just 2-3 posts back, that 2^20 is a reasonable size. That is more than a million. Am I understanding something wrongly here?

[Roman Hartmann]

Ok, I am creating all the values, but you said the table would have "nearly thousand elements" whereas JWC said, just 2-3 posts back, that 2^20 is a reasonable size. That is more than a million. Am I understanding something wrongly here?

2^20 would be a reasonable number for the hash table entries while the nearly thousand elements would be the number of zobrist-keys you need.

Roman

[Sven]

It is simpler to generate them every time you start the program. You would only need one line of code for that, while the table is nearly thousand elements. By the time you need a fixed set of keys to communicate with the outside world, you can aways switch to an initialized table.

Ok, I am creating all the values, but you said the table would have "nearly thousand elements" whereas JWC said, just 2-3 posts back, that 2^20 is a reasonable size. That is more than a million. Am I understanding something wrongly here?

These are two different tables. The "2^20" example is about the hash table itself which is filled and used during search. The "nearly thousand elements" is about the table of zobrist keys which is created once at program start, either by generating new random numbers or by using fixed numbers, and is used to calculate/update the hash key of the current position.

Sven

[JVMerlino]

Question. When making changes like this, on how you loop through the board, is it sufficient to just test if perft speeds increase in order to know if the new algorithm is better? Or do you need to test on various positions as well just to be sure?

Also, Myrddin does an embedded for loop, like this:

Code: Select all

for (nRow = 0; nRow < 8; nRow++)
{
	for (nCol = 0; nCol < 8; nCol++)
	{
		nSquare = RC2SQUARE(nRow, nCol);
	}
}

Is this slower than the [0...120] method?

Many thanks,
jm

[hgm]

Probably. But who cares? If you want speed, you should not loop over the board. Most squares will be empty, or not contain what you are looking for. Accessing those is a waste of time, no matter how fast and well-optimized you do it.