Guide me through building a chess program

[JVMerlino]

Right. Just wanted to make sure that, until I implement piece lists, I didn't have some quick way of making a small improvement.

[JVMerlino]

And it was an improvement indeed, and every little bit helps. Depending on the position, the speed increase is between 1.5% and 10%, obviously depending on how much wood is on the board.

Thanks, H.G.!

[Sapta]

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

Thanks for clearing that up, and sorry for the late reply.

[Sapta]

I am checking the Transposition table implementation given in Bruce Moreland's webpage and I am having a bit of trouble with the probehash function.

http://web.archive.org/web/200404200216 ... ashing.htm

The Probehash function checks the table and returns a value if the position is saved in the table and if the depth of it last time was more or equal to the current depth. But

1. What exactly are the last 2 "if" conditions doing? Ie for flags hashfALPHA and hashfBETA?

2. What is Rememberbestmove() ? I guess it's related to move ordering and gets the best move from the table entry but how exactly is it putting that move first? :/ Also, is best move saved only when we have a fail high?

[hgm]

I cannot see that page, but probably the flags indicate if the stored score is an upper bound, a lower bound or exact. (An alpha-beta search usually only provides bounds to the score.)

You get a best move each time you score above alpha (which need not be a fail-high yet). It does not seem to matter much if I also store 'best' moves that failed low, though. (These do not have to be best moves at all, of course. But I guess most of the time you visit an all-node it will still be an all-node, so the order does not matter anyway, and sorting a non-sensica hash move in front doesn't hurt any.)

Sorting the best move in front is a lot harder in real life than in pseudo-code. How to do it depends on your general strategy towards move generation. My new engine, for instance, does not even generate moes before it searched the hash move. So when I have a TT hit tht provides a move, I jst put that move in the move list of that node, and then it has a list of one. Only when the list runs out, I start looking if there still is a next stage of move generation I could use to expand the list. First with captures (and even that is done in stages, first all Queen captures, then all Rook captures), then killers, then other non-captures.

So I have the problem that a later stage might generate a move that has already been searched as hash move or killer. I solve this by comparing every move with hash and (if it is a non-capture) with killers just because I search it for the first time. (I do Internal Iterative Deepening and self-re-searching PVS and LMR, so I might run through the move list several times.) At the same time I check non-duplicate captures for being bad or dubious capture (high piece captures defended low), so I can postpone those. by copyng them to a separate list, and appending those to the main move list (as the final stage of move generation) after I am done searching the non-captures.

I don't take the trouble to compact the move list after I discover a move is a duplicate; I just zap the move by writing a zero there (which is invalid as move encoding), and always skip move entries that are zero.

In micro-Max I start searching the hash move, before I start the move-generator loop (which immediately searches the moves as they are generated). I don't even take the trouble of checking for duplicates there; I count on the second search getting a hash hit on the entry made the first time it was searched, so it would not take significant extra time to search it twice.

[Sven]

I am checking the Transposition table implementation given in Bruce Moreland's webpage and I am having a bit of trouble with the probehash function.

http://web.archive.org/web/200404200216 ... ashing.htm

The Probehash function checks the table and returns a value if the position is saved in the table and if the depth of it last time was more or equal to the current depth. But

1. What exactly are the last 2 "if" conditions doing? Ie for flags hashfALPHA and hashfBETA?

Code: Select all

if ((phashe->flags == hashfALPHA) &&
    (phashe->val <= alpha))
    return alpha;
if ((phashe->flags == hashfBETA) &&
    (phashe->val >= beta))
    return beta;

If the stored value is flagged as upper bound (hashfALPHA) and is at most equal to current alpha then probing returns alpha since you can be pretty sure that the exact value of the former search would have been below the current window, so you know enough to return from the current node and let the *parent* node fail high immediately.

If the stored value is flagged as lower bound (hashfBETA) and is at least equal to beta then probing returns beta since you can be pretty sure that the exact value of the former search would have been above the current window, so you know enough to return from the current node with a fail-high.

Both are directly applicable for a fail-hard alpha-beta framework. With fail-soft you may do the same but you can even return the stored value itself instead of alpha resp. beta.

Another point in this code is that the probing function does *not* return a value that causes the search to immediately return from the current node for any other cases different from "exact value" and the two cases above, so especially even a sufficient depth does not fire if the stored value + bounds information does not match the current window.

Sven

[Sapta]

^ Sorry but I am getting confused when I try to trace the algorithm. The basic alpha-beta seems easy but this negamax format is sort of difficult to follow So, I have decided to take it for granted that it's working just as alpha-beta should and all I need to do is store the best moves and sort them and that the other parts(probehash etc) are all perfect in Bruce Moreland's site. I'll return to this post and negamax alphabeta after I complete the ordering. Hopefully I shall be able to understand this quite easily then

Sorting the best move in front is a lot harder in real life than in pseudo-code. How to do it depends on your general strategy towards move generation. My new engine, for instance, ...

Thanks, this post was helpful.

[Fguy64]

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.

Interesting. Piecelists did give me a nice little improvement, but it was a royal pain in the ass to get it right, that is maintaining pieceLists during search.

I just use them to keep track of the locations of the pieces, I don't bother to keep track of what type each piece is, just where to find them. and I may try some "pre-ordering" also. What about you? any other uses for piece lists?

[Sapta]

For the creation of zobrist, why are there 4 random numbers for castling in each colour? Can't we just keep 2 for each colour?

Say, white_castling[0] represent Kside castling and [1] represents Qside castling. We only XOR the number when that castling right is lost. Is this wrong?

[Sven]

For the creation of zobrist, why are there 4 random numbers for castling in each colour? Can't we just keep 2 for each colour?

Say, white_castling[0] represent Kside castling and [1] represents Qside castling. We only XOR the number when that castling right is lost. Is this wrong?

It is sufficient to use two zobrist keys per colour. But if someone wants to implement it differently, e.g. by looking at four possible combinations of two castle rights per colour, and assigning one zobrist key to each combination, then he may do it this way, as long as he handles it correctly. It just adds more complexity than necessary.

Btw, to which source of information do you refer where four numbers are used?

Sven