Guide me through building a chess program

[Sapta]

Implemented and seems to be working fine. Now going back to transposition tables and move ordering, I have 2 questions:

1. The replacement scheme to use. Bruce Moreland's site says this at one point-

If you use the "replace if deeper or same depth" scheme, your table might eventually fill up with outdated deep nodes. The solution to this is either to clear the table each time you move, or add a "sequence" field to your element, so the replacement scheme becomes, "replace if same depth, deeper, or the element pertains to an ancient search".

What's the problem with "outdated" nodes? If the hash key matches, it means the position is same(in most cases) and a deeper search should be better always? Also, how do I define "ancient" ?

2. The move ordering. Currently, what I'm trying to do is put the best move from TT in front of moveslist and then sort the remaining moves using (score of each move - moving piece value).

Score of each move is a variable in the move object and it's set like

10 if target blank
20 if target pawn
40 if target bishop/knight
60 if target rook
100 if target queen

This seems okay for higher valued targets. So, pawn capturing queen comes first, then bishop or knight capturing queen etc. But towards the end, it seems bad.
A pawn capturing pawn comes before queen capturing pawn or a pawn moving forward comes before queen moving. What should be the way to sort these moves?

[hgm]

The bad thing about outdated nodes is that they waste space in the table. If the root has ony 6 white Pawns on the board, any stored position with 7 or 8 white Pawns will for sure not cause any hits. So your table might get filled up with useless positions, that will stay there forever because they happened to have been searched at a large depth.

A very simple way to handle this is to allow an entry of depth N to replace any entry of depth N+1 ('under-cut replacement'). In any other case you replace the the entry only if its neighbor has a higher or equal depth, and otherwise you replace that neighbor. (So on probing you will aways have to check the neighbor too.)

QxP captures can be good if the Pawn is undefended. Man engines do a 'Static Exchange Evaluation', taking into account only captures to the target square, to see if it is good to capture or not. Even when you only do it on Higher-takes-Lower captures, this can cause a significant slowdown, (in terms of nodes per second), however.

My new engine does not do a complete SEE (which would be unreliable anyway, as many of the captures could have side effects). When I encounter a HxL capture as the next move to search, I test if there is a defender, in such a way that I will find the lowest defender first. If there is, I postpone the search until after all LxH, equal and L x undefended H have been searched. When I get to those postponed moves, I test if the value of the victim and its defender together exceed that of the capturer. On such a 'dubious' capture I could conceivably come out on top, and I search the move. If not, I postpone it a second time, until after the non-captures.

[Sapta]

My new engine does not do a complete SEE (which would be unreliable anyway, as many of the captures could have side effects). When I encounter a HxL capture as the next move to search, I test if there is a defender, in such a way that I will find the lowest defender first. If there is, I postpone the search until after all LxH, equal and L x undefended H have been searched. When I get to those postponed moves, I test if the value of the victim and its defender together exceed that of the capturer. On such a 'dubious' capture I could conceivably come out on top, and I search the move. If not, I postpone it a second time, until after the non-captures.

Hm interesting method. I'll think if I can implement this although checking for a defender means going 1 ply deeper. Will see.

A very simple way to handle this is to allow an entry of depth N to replace any entry of depth N+1 ('under-cut replacement'). In any other case you replace the the entry only if its neighbor has a higher or equal depth, and otherwise you replace that neighbor. (So on probing you will aways have to check the neighbor too.)

Sorry but can you please elaborate this? Why would I allow all lower depth entries replace higher depth entries when the usual simplest way is just the opposite? Also, what exactly are "neighbors" ?

Sorry for all these constant questioning

[hgm]

The usual way to protect higher depths in a hash table, is to derive a primary table index A from the hash key (e.g. by taking the M least signifiant bits of it, by taking the bitwise AND with a mask of M one bits), and then replace the entry at either address A or A+1, depending on which of the two had the lowest depth. In this case 'neighbor' of A would mean A+1. With this scheme you keep both the entry with the largest depth and the most recent one.

After some time the deep entry of each pair would become nearly immune to replacement, and at some point in the game it would go stale (not reachable from the root anymore). The depth of the deepest of the (A,A+1) pair can only go up. By sometimes replacing depth N by depth N-1 it can also go down, and in stead of perpetually increasing depth you will get an equilibrium population.

With this method the deep entries are disappearing randomly, when the happen to be hit by an entry with one-lower depth. This is not optimal; it would be better to make the oldest disappear selectively. But in that case you would have to store some aging counter in the entry to keep track of the age, and this is not free: it takes space, so that you can fit fewer entries in the same amount of memory, and this might offset any gain from the more complicated replacement scheme. So you might as well start with the simpler scheme, that would not require you to keep track of any additional information on the aging.

[Sapta]

The usual way to protect higher depths in a hash table, is to derive a primary table index A from the hash key (e.g. by taking the M least signifiant bits of it, by taking the bitwise AND with a mask of M one bits), and then replace the entry at either address A or A+1, depending on which of the two had the lowest depth. In this case 'neighbor' of A would mean A+1. With this scheme you keep both the entry with the largest depth and the most recent one.

Confirming 1 thing. So this is "always replace" without considering if the lower of the 2 pair's depths is less than the current depth and this ensures a recent and an old entry pair. Right?

After some time the deep entry of each pair would become nearly immune to replacement, and at some point in the game it would go stale (not reachable from the root anymore). The depth of the deepest of the (A,A+1) pair can only go up. By sometimes replacing depth N by depth N-1 it can also go down, and in stead of perpetually increasing depth you will get an equilibrium population.

I check for both neighbors satisfying the condition one after the other. Only if none does, I go to the method of replacing the lower depth one from the pair. Right?

[Sapta]

Strange I can't edit my post after 15 minutes of posting it :O

Anyway, I was gonna add that the way I understand it, a recent entry will always replace one of the neighbors in each Recordhash call. Is that right?

[Sapta]

Darn, I misunderstood it seems. Because if I don't compare the depths when replacing the lower one, the table would get filled with too low entries and become useless.

So, if curr_depth > any of the 2 neighbors depth, replace the lower depth one. if curr_depth = stored depth -1, replace it. Do I finally get it?

[hgm]

To avoid misunderstanding, let me give some pseudo-code:

Code: Select all

index = hashKey & 0xFFFFFF; // take lowest 24 bits (16M entries)
if(table[index+1].lock == hashKey) index++; // present in A+1; write there
else if(table[index].lock != hashKey) { // not present yet; replace
  if(table[index].depth != depth+1) { // no under-cut; replace least deep
    if(table[index+1].depth < table[index].depth) index++;
  }
}
// write hash entry
table[index].depth = depth;
table[index].lock = hashKey;
table[index].score = score;

[Sapta]

Thank you for the pseudo code hgm. I have some basic questions about evaluation:

1. From whose perspective should the board be evaluated in negamax alphabeta? the current side to move ? or the maximizing player in the game tree(so I have to save the side or get it from ply number)?

2. Each aspect that we consider in evaluation, do we need to consider for both sides and then subtract? eg- pawn shield? In other words does the initial position NEED to evaluate to zero?

3. Is there some database where positions and their relative evaluated scores are given for testing purposes?

[hgm]

In negamax evaluation is always from the perspective of the side to move.

Indeed, usually the evaluation is completely symmetric. Some programs use a 'side-to-move bonus' of a few centi-Pawn.

I don't know of any such database. I know someone proposed it recently.