Beginning hashtable question.

[Sven]

I would try it without the transposition table to make sure ID is working correctly.

Thanks, but I think I have found my problem. It ws a logic error in one of my hash writes.

My convention for numbering the plies is slightly non-standard I guess, although it is intuitive for me. I have a class variable iPly, and in my ID loop iPly goes from 1 to maxPly. At each iteration, 1 is passed to alphsBeta, then in my recursive alphaBeta method, ply goes from 1 to iPly inclusive, and evaluate() is called for ply > iPly.

The problem was, along with my call to evaluate, I was storing a draft (remaining depth) of 0, which is wrong since my stop condition is ply > iPly. By storing a depth of -1 for this exact hash write at the stop condition, all my problems appear to have been resolved. It's not clear to me why my straght up fixed depth searching appeared to work fine with this particular hash write error.

regards.

Sounds good. But that "-1" stuff is quite artificial now, isn't it? This is caused by your non-standard numbering. Your system goes:

"iPly" := number of current iteration, which is the intended maximum distance between root and horizon when ignoring extensions/reductions etc.

"ply" := local variable of alphaBeta() function describing the distance of current node to root + 1 (!!) since you start with ply=1 at the root; the range of "ply" within full search is therefore [1 .. iPly + 1]

"draft" := iPly - ply, which is in your case the distance of the current node to the horizon - 1

... and that is fine except that "ply" starts at 1, which automatically implies all the other special "off by one" conditions. You see that this has caused trouble now, although you are consistently saying that it were more intuitive for you. IMO you have proven yourself wrong regarding that intuition, so I propose that you consistently change to the standard numbering scheme. I think that it is far better because everyone (including yourself) can immediately understand when your search reaches the horizon, i.e. draft == 0 (not draft == -1). "No more moves left until horizon" is better expressed by a zero than by a "-1", isn't it?

Regarding your hash stores, I'd expect that you store search results at basically each node, not just at the leaves, and that you always store "iPly - ply" as the draft, which automatically leads to storing -1 at the leaves with your current implementation (or 0 if you switch). From your description I was not sure whether you really do this. If you don't then ... forget your hash table

Sven

[Fguy64]

I would try it without the transposition table to make sure ID is working correctly.

Thanks, but I think I have found my problem. It ws a logic error in one of my hash writes.

My convention for numbering the plies is slightly non-standard I guess, although it is intuitive for me. I have a class variable iPly, and in my ID loop iPly goes from 1 to maxPly. At each iteration, 1 is passed to alphsBeta, then in my recursive alphaBeta method, ply goes from 1 to iPly inclusive, and evaluate() is called for ply > iPly.

The problem was, along with my call to evaluate, I was storing a draft (remaining depth) of 0, which is wrong since my stop condition is ply > iPly. By storing a depth of -1 for this exact hash write at the stop condition, all my problems appear to have been resolved. It's not clear to me why my straght up fixed depth searching appeared to work fine with this particular hash write error.

regards.

Sounds good. But that "-1" stuff is quite artificial now, isn't it? This is caused by your non-standard numbering. Your system goes:

"iPly" := number of current iteration, which is the intended maximum distance between root and horizon when ignoring extensions/reductions etc.

"ply" := local variable of alphaBeta() function describing the distance of current node to root + 1 (!!) since you start with ply=1 at the root; the range of "ply" within full search is therefore [1 .. iPly + 1]

"draft" := iPly - ply, which is in your case the distance of the current node to the horizon - 1

... and that is fine except that "ply" starts at 1, which automatically implies all the other special "off by one" conditions. You see that this has caused trouble now, although you are consistently saying that it were more intuitive for you. IMO you have proven yourself wrong regarding that intuition, so I propose that you consistently change to the standard numbering scheme. I think that it is far better because everyone (including yourself) can immediately understand when your search reaches the horizon, i.e. draft == 0 (not draft == -1). "No more moves left until horizon" is better expressed by a zero than by a "-1", isn't it?

Regarding your hash stores, I'd expect that you store search results at basically each node, not just at the leaves, and that you always store "iPly - ply" as the draft, which automatically leads to storing -1 at the leaves with your current implementation (or 0 if you switch). From your description I was not sure whether you really do this. If you don't then ... forget your hash table

Sven

yes I could just store code iPly - ply for the one line of code that deals with a hash update at a leaf node. That would do the same thing, and be consistent with the code for all the other nodes. that are searched.

Honestly, I don't see the numbering scheme as the problem in and of itself. Six of one, half a dozen of the other. Maybe it makes hashng slightkly more error prone, but t makes other things easer. I originally chose this scheme because it was, and still is, easier to visualize and required less mental gymnastics when it came to dong the coding for my triangular array approach to collecting PV. And is still allows for a more natural correspondence in numbering between the plies and my arrays for storing possible moves, IMO. I might not feel the same way if I decide to do extensions or something like that, but that is a long way off.

But yeah, I can see a value with using standard schemes when it comes to discussing wth others, and I may yet change it. Part of the issue is that I'm a seat of the pants guy when it comes to this. Because I find the material at sites such as the chess programming wike difficult to absorb.

regards

p.s. It's not clear to me what you mean by "all those other one-off" conditions" ?

[hgm]

Now wait until you want to abandon fixed-depth search, and want to implement reductions and extensions...

[Fguy64]

Now wait until you want to abandon fixed-depth search, and want to implement reductions and extensions...

duly noted. I can see where I'd have to make some changes. I had thought about that. But really those things are a long way off. With the addition of Q, and hashing and iterative deepening I now feel like I have decent algorithm I can use for a while, touch wood, although maybe I will add some kind of null move prunng. Now I concentrate on evaluation. Then there is GUI enhancements, database, networking, UCI/Winboard. etc.. etc. I need to become a more well rounded programmer for career reasons.

[Sven]

yes I could just store code iPly - ply for the one line of code that deals with a hash update at a leaf node. That would do the same thing, and be consistent with the code for all the other nodes. that are searched.

Honestly, I don't see the numbering scheme as the problem in and of itself. Six of one, half a dozen of the other. Maybe it makes hashng slightkly more error prone, but t makes other things easer. I originally chose this scheme because it was, and still is, easier to visualize and required less mental gymnastics when it came to dong the coding for my triangular array approach to collecting PV. And is still allows for a more natural correspondence in numbering between the plies and my arrays for storing possible moves, IMO. I might not feel the same way if I decide to do extensions or something like that, but that is a long way off.

But yeah, I can see a value with using standard schemes when it comes to discussing wth others, and I may yet change it. Part of the issue is that I'm a seat of the pants guy when it comes to this. Because I find the material at sites such as the chess programming wike difficult to absorb.

regards

p.s. It's not clear to me what you mean by "all those other one-off" conditions" ?

It is not just about standards. My point is that it quickly becomes a pain if you always have to remember that "+1" or "-1" being implied by your numbering scheme. That is also what I meant with 'all the other special "off by one" conditions'. Read again my description of how I understood your iPly, ply, and draft, there you find some "+1" or -1" exceptions. These disappear immediately when starting with ply at 0 instead.

You say that starting ply at 1 were easier to visualize. That becomes irrelevant or even wrong as soon as you give your "ply" variable the meaning that it deserves: the distance of the current node to the root! So it is not a matter of better visualization but of semantics. In your case the semantics is currently "ply := distance to root + 1". Why make it more complex than necessary?

There is also the need to maintain certain search-related data for each ply, which is usually done in arrays. Here you have the same "+1" resp. "-1" problems with your approach. You have two choices if you stick with ply starting at 1:

a) define arrays one item larger than necessary, and keep item 0 unused since you start to access the array with index 1 (the "+1" case applied to the array size);

b) always subtract -1 from the ply when accessing the array, to get item 0 for ply 1 and item 1 for ply 2 ... (the "-1" case applied to the array index).

Both choices are simply bogus with C, C++, and Java as languages. In Pascal you can define arbitrary array bounds, e.g. myArray[1..N] : integer, but we simply don't have that in our chosen languages. The usual approach to access an array of size N by indices [0..N-1] perfectly applies to our needs for several decades.

Sven

[Fguy64]

yes I could just store code iPly - ply for the one line of code that deals with a hash update at a leaf node. That would do the same thing, and be consistent with the code for all the other nodes. that are searched.

Honestly, I don't see the numbering scheme as the problem in and of itself. Six of one, half a dozen of the other. Maybe it makes hashng slightkly more error prone, but t makes other things easer. I originally chose this scheme because it was, and still is, easier to visualize and required less mental gymnastics when it came to dong the coding for my triangular array approach to collecting PV. And is still allows for a more natural correspondence in numbering between the plies and my arrays for storing possible moves, IMO. I might not feel the same way if I decide to do extensions or something like that, but that is a long way off.

But yeah, I can see a value with using standard schemes when it comes to discussing wth others, and I may yet change it. Part of the issue is that I'm a seat of the pants guy when it comes to this. Because I find the material at sites such as the chess programming wike difficult to absorb.

regards

p.s. It's not clear to me what you mean by "all those other one-off" conditions" ?

It is not just about standards. My point is that it quickly becomes a pain if you always have to remember that "+1" or "-1" being implied by your numbering scheme. That is also what I meant with 'all the other special "off by one" conditions'. Read again my description of how I understood your iPly, ply, and draft, there you find some "+1" or -1" exceptions. These disappear immediately when starting with ply at 0 instead.

You say that starting ply at 1 were easier to visualize. That becomes irrelevant or even wrong as soon as you give your "ply" variable the meaning that it deserves: the distance of the current node to the root! So it is not a matter of better visualization but of semantics. In your case the semantics is currently "ply := distance to root + 1". Why make it more complex than necessary?

There is also the need to maintain certain search-related data for each ply, which is usually done in arrays. Here you have the same "+1" resp. "-1" problems with your approach. You have two choices if you stick with ply starting at 1:

a) define arrays one item larger than necessary, and keep item 0 unused since you start to access the array with index 1 (the "+1" case applied to the array size);

b) always subtract -1 from the ply when accessing the array, to get item 0 for ply 1 and item 1 for ply 2 ... (the "-1" case applied to the array index).

Both choices are simply bogus with C, C++, and Java as languages. In Pascal you can define arbitrary array bounds, e.g. myArray[1..N] : integer, but we simply don't have that in our chosen languages. The usual approach to access an array of size N by indices [0..N-1] perfectly applies to our needs for several decades.

Sven

OK I see what you mean, and yes, I suppose it would be better to start with 0 than 1.

I did not mean that starting at 1 was easier to visualize than starting at 0. I meant that incrementing my ply rather than decrementing made it easier for me to visualize some things. As far as I can see, you don't have issues wth that aspect. corrrect?

That being said, I am giving consideration to reversing my numbering scheme anyways, so that my recursion variable is depth remaining. My understanding now is much better, and I should be able get my head around issues that I previously couldn't.

regards.

[hgm]

Once you will have extensions and reductions (so already with null-move pruning), the distance from the root ('ply') and the distance to the leaves ('depth') are no longer complementary variables that contain the same info. They become independent variables. At some point you will be forced to maintain the both, ply to index your PV arrays, and depth to decide when you reach QS. Life would become very awkward if you didn't. So you might as well design it from the start, even now you do not strictly need it. Then you can aready get used to it.

[Sven]

Once you will have extensions and reductions (so already with null-move pruning), the distance from the root ('ply') and the distance to the leaves ('depth') are no longer complementary variables that contain the same info. They become independent variables. At some point you will be forced to maintain the both, ply to index your PV arrays, and depth to decide when you reach QS. Life would become very awkward if you didn't. So you might as well design it from the start, even now you do not strictly need it. Then you can aready get used to it.

100% agreed!

Sven

[Sven]

OK I see what you mean, and yes, I suppose it would be better to start with 0 than 1.

I did not mean that starting at 1 was easier to visualize than starting at 0. I meant that incrementing my ply rather than decrementing made it easier for me to visualize some things. As far as I can see, you don't have issues wth that aspect. corrrect?

Not quite. Decrementing the ply would give it a totally different semantics. What you probably mean is something like: "using a 'ply' parameter for recursion that is being incremented made it easier for me to visualize some things than using a 'draft' parameter that is being decremented." But you will need both, "ply" and "draft". In your current implementation you can still derive "draft := iPly - ply" but that no longer holds as soon as extensions/reductions/advanced pruning enter the scene.

That being said, I am giving consideration to reversing my numbering scheme anyways, so that my recursion variable is depth remaining. My understanding now is much better, and I should be able get my head around issues that I previously couldn't.

As HGM has already commented, consider a search function like in this simple example:

Code: Select all

int alphaBeta(int alpha, int beta, int ply, int draft)
{
    if (isInCheck()) ++draft; // here 'draft' is no longer 'iPly - ply' !!
    ...
    if (draft == 0) return qSearch(alpha, beta, ply);
    ...
    for (Move m = pickNextMove(); m != NoMove; m = pickNextMove()) {
        makeMove(m);
        int modifiedDraft = APPLY_EXTENSIONS_OR_REDUCTIONS(draft);
        int v = -alphaBeta(-beta, -alpha, ply+1, modifiedDraft-1);
        unmakeMove(m);
        if (v > alpha) {
            ...
        }
    }
    return ...
}

Note that in this example "ply" is never changed within the same node while "draft" may change according to search strategies.

Sven

[Fguy64]

OK I see what you mean, and yes, I suppose it would be better to start with 0 than 1.

I did not mean that starting at 1 was easier to visualize than starting at 0. I meant that incrementing my ply rather than decrementing made it easier for me to visualize some things. As far as I can see, you don't have issues wth that aspect. corrrect?

Not quite. Decrementing the ply would give it a totally different semantics. What you probably mean is something like: "using a 'ply' parameter for recursion that is being incremented made it easier for me to visualize some things than using a 'draft' parameter that is being decremented." But you will need both, "ply" and "draft". In your current implementation you can still derive "draft := iPly - ply" but that no longer holds as soon as extensions/reductions/advanced pruning enter the scene.

...

Sven

OK, point taken. Anyways, in anticipation of more advanced search techniques, I decided to try and change my scheme so that the recursion variable (draft) is decremented, and evaluate ( Q ) is called at ply (or depth or whatever you call it) equal to zero. It was easy enough to do.

That still leaves the question of whether to actually use array index 0, no? I guess I find it simpler to have the recursion variable (in my case ply) equal the array index, which as I see implies an array dimension of maxDepth+1. And a little unused space. And my PV array updates look like this...

Code: Select all

if( eval > alpha ) { 
    alpha = eval;
    PV[ply][ply] = m;
    if( ply > 1 ) System.arraycopy( PV[ply-1], 1, PV[ply], 1, ply-1 );
}

Note that this block does not include the hashing code. I'm thinking at some point that I should be able to do away with this PV[][] array, which is a holdover from pre-hashing days and strictly for display, and get any information I need directly from the hash table.