Next steps for my engine?

[Aleks Peshkov]

I doubt that your alpha-beta implementation is correct.
Here should be two variables: alpha and beta. The key point is that beta became -alpha when we switch side to move.

[Fguy64]

I doubt that your alpha-beta implementation is correct.
Here should be two variables: alpha and beta. The key point is that beta became -alpha when we switch side to move.

I gave some thought as how I could prove that my algorithm is correct, without going into a big explanation of the algorithm. I still believe that it works out the same in the end, based on the following results...

1. Given sufficient ply and time, my program has been able to solve any forced mate that I could throw at it.
2. I was able to work through the WAC suite without a lot of difficulty. Always I found the right solution, though I didn't pay a lot of attention to the time it took, but for the most part it used the correct ply.
3. When my eval was based strictly on material, I found that implementing move ordering by doing captures first dramatically speeded up the process, without changing the result.
4. Evaluating checks first tends to speed up the process of finding forced mate, often significantly speeded up.

Correct me if I'm wrong, but 3 & 4 in particular suggests the alpha-beta pruning is correct. I still think it works out the same in the end.

Anyways, in a way this is kind of beside the point, the idea is for me to express the algorithm conventionally, so your remark about beta becoming -alpha looks useful. Thanks.

[xsadar]

I doubt that your alpha-beta implementation is correct.
Here should be two variables: alpha and beta. The key point is that beta became -alpha when we switch side to move.

I gave some thought as how I could prove that my algorithm is correct, without going into a big explanation of the algorithm. I still believe that it works out the same in the end, based on the following results...

1. Given sufficient ply and time, my program has been able to solve any forced mate that I could throw at it.
2. I was able to work through the WAC suite without a lot of difficulty. Always I found the right solution, though I didn't pay a lot of attention to the time it took, but for the most part it used the correct ply.
3. When my eval was based strictly on material, I found that implementing move ordering by doing captures first dramatically speeded up the process, without changing the result.
4. Evaluating checks first tends to speed up the process of finding forced mate, often significantly speeded up.

Correct me if I'm wrong, but 3 & 4 in particular suggests the alpha-beta pruning is correct. I still think it works out the same in the end.

Anyways, in a way this is kind of beside the point, the idea is for me to express the algorithm conventionally, so your remark about beta becoming -alpha looks useful. Thanks.

Like Aleks says, you are indeed missing the alpha part of alpha-beta. From what I can see, and based on the testing you said you've done, your code probably works (meaning it gives the same move and score as negamax), but it won't go as fast as alpha-beta. It does do some pruning though, which will make it faster than plain old nega-max.

The reason alpha is important is that the worst you can do also happens to be the negative of the best your opponent can do. Suppose you enter a node with alpha=-5, then even on the first move from that node you know the best your opponent can do is +5. So you pass that as beta (maxEval). But with your code, you don't know that -5 is the worst you can do, so you pass infinity (10000 in your case) as beta on the first move, and you can't make beta cutoffs with a beta of infinity.

To add alpha, make sure that your prototype looks something like this (where minVal is your alpha and maxVal is your beta):

Code: Select all

private int evaluate( String pStr, int ply, int minVal, int maxEval )

and your function call looks something like this:

Code: Select all

evaluate( p1Str, ply-1, -maxVal, -minVal )

I'll let you figure out the rest of the changes, but feel free to ask if you have more questions.

[Fguy64]

Thanks Mike. I'll take some time to think this through. One of the biggest hurdles I've faced in moving forward is a lack of a fluent understanding of the words alpha and beta when they get tossed around in more advanced literature. I sort of understand them at a basic level, but once I can use the words fluently without having to stop and think about them all the time, I'm sure things will come easier.

OK, I let it rest on the subject of whether or not my algorithm is equivalent to alpha/beta. I'm sure it will become clear to me one way or another soon enough.

I wonder: am I correct in saying that my code constitutes negamax, even though it is not really alpha-beta? I've always thought of alpha beta as a refinement to negamax, not a requirement for negamax.

No doubt there will be questions once i start to dig in. Thanks again.

[Dann Corbit]

Thanks Mike. I'll take some time to think this through. One of the biggest hurdles I've faced in moving forward is a lack of a fluent understanding of the words alpha and beta when they get tossed around in more advanced literature. I sort of understand them at a basic level, but once I can use the words fluently without having to stop and think about them all the time, I'm sure things will come easier.

OK, I let it rest on the subject of whether or not my algorithm is equivalent to alpha/beta. I'm sure it will become clear to me one way or another soon enough.

I wonder: am I correct in saying that my code constitutes negamax, even though it is not really alpha-beta? I've always thought of alpha beta as a refinement to negamax, not a requirement for negamax.

No doubt there will be questions once i start to dig in. Thanks again.

Normally, negamax is applied to either using mini-max or alpha-beta and negating the next level and calling the same routine. See (for instance):
http://www.hamedahmadi.com/gametree/#negamax

Alpha-beta specifically avoids extra searching. If we found out that there is a finger biting weasel in the second bag and there are no bad things in the first bag, then we don't have to completely search the second bag to discover that it also contains a wolverine and an angry bengal tiger. As soon as we see than nasty little weasel, we go on to the next bag.

[xsadar]

Thanks Mike. I'll take some time to think this through. One of the biggest hurdles I've faced in moving forward is a lack of a fluent understanding of the words alpha and beta when they get tossed around in more advanced literature. I sort of understand them at a basic level, but once I can use the words fluently without having to stop and think about them all the time, I'm sure things will come easier.

OK, I let it rest on the subject of whether or not my algorithm is equivalent to alpha/beta. I'm sure it will become clear to me one way or another soon enough.

I wonder: am I correct in saying that my code constitutes negamax, even though it is not really alpha-beta? I've always thought of alpha beta as a refinement to negamax, not a requirement for negamax.

No doubt there will be questions once i start to dig in. Thanks again.

Yes, the terms alpha and beta are a bit confusing. That's why I prefer terms like min and max, and when I see alpha or beta written I do a mental substitution (although not as often as I used to).
For alpha, I mentally substitute the word min, because it is the minimum (or worst) evaluation the moving side (for the position we're considering) is willing to accept, because he/she/it can do at least that well on a previously searched line.
For beta, I mentally substitute the word max, because it is the maximum (or best) evaluation the moving side will be allowed, because the other player can limit the score to beta on a previously searched line.

Yes, alpha-beta is a refined negamax. Your code also appears to be a refined negamax, just not as refined as alpha-beta.

[Sven]

I doubt that your alpha-beta implementation is correct.
Here should be two variables: alpha and beta. The key point is that beta became -alpha when we switch side to move.

I gave some thought as how I could prove that my algorithm is correct, without going into a big explanation of the algorithm. I still believe that it works out the same in the end, based on the following results...

1. Given sufficient ply and time, my program has been able to solve any forced mate that I could throw at it.
2. I was able to work through the WAC suite without a lot of difficulty. Always I found the right solution, though I didn't pay a lot of attention to the time it took, but for the most part it used the correct ply.
3. When my eval was based strictly on material, I found that implementing move ordering by doing captures first dramatically speeded up the process, without changing the result.
4. Evaluating checks first tends to speed up the process of finding forced mate, often significantly speeded up.

Correct me if I'm wrong, but 3 & 4 in particular suggests the alpha-beta pruning is correct. I still think it works out the same in the end.

Anyways, in a way this is kind of beside the point, the idea is for me to express the algorithm conventionally, so your remark about beta becoming -alpha looks useful. Thanks.

The fact that changing the move ordering has any effect at all does only show that you have *some* kind of pruning, it does not tell us whether Alphabeta is implemented correctly.

Alphabeta is nothing but an optimization, although a heavy and therefore very important one. Negamax and Alphabeta, when given the same maximum search depth without time constraints and without using any not perfectly deterministic elements (hash table could be one example), will return the same value for the root node, and under the assumption of identical move ordering they should also return the same best move. But while Negamax needs N^D nodes to search a tree with branching factor N (possible moves per node) to depth D, Alphabeta only needs 2*sqrt(N^D) with perfect move ordering.

So you should define what you mean by "correct alpha-beta pruning":

If you mean a correct tree search that returns the same result as Negamax (or even Minimax), regardless whether it is efficient or not, then your algorithm is probably o.k. in this sense, although I think it is not obvious for the reader.

However, if you mean "correct application of the Alphabeta algorithm itself" to achieve the same level of pruning that this algorithm has been designed for, then I have to say that your algorithm is not correct. The essential part of your tree search is as follows:

Code: Select all

int evaluate(..., int ply, int maxEval)
{
    if (ply==1) return evalPos(...);
    int max = -10000;
    ...
    for (all moves) {
        int eval = evaluate(..., ply-1, max);
        if (eval > max) max = eval;
        if (-max < maxEval) return -max;
    }
    ...
    return -max;
}

I can transform this algorithm into something that is closer to common standards by applying these changes:
- rename "evaluate" into "search";
- rename "ply" into "depth";
- rename "max" into "alpha";
- rename "maxEval" into "beta";
- invert the sign of the return value of "search" at the point where the function is called, not where it returns (no functional change);
- replace the expression "-alpha < beta" by the logically equivalent expression "alpha > -beta";
- invert the sign of the "beta" parameter at the point where the function is called, not where the value is used (again, no functional change).

Please apply these changes step by step and look at the intermediate form of the algorithm before trying and understanding the next steps.

Finally the algorithm would look like this:

Code: Select all

int search(..., int depth, int beta)
{
    if (depth==1) return evalPos(...);
    int alpha = -10000;
    ...
    for (all moves) {
        int eval = -search(..., depth-1, -alpha);
        if (eval > alpha) alpha = eval;
        if (alpha > beta) return alpha;
    }
    ...
    return alpha;
}

This has several flaws which I would like to point out.

1. The original Alphabeta algorithm uses alpha and beta as a window that is narrowed from both sides during search. But in your algorithm only beta is used while alpha always starts at "-10000", so you lose the effect of searching the next subtrees with a narrower window after having found a move that improves over the previous best move. At the root node you will probably search all possible moves with a window (-10000/+10000) which is quite inefficient since as a result you get fewer cutoffs.

The "alpha" parameter will get "-beta" as initial value from the caller:
"... = -search(..., depth-1, -beta, -alpha);"

2. The condition "if (alpha > beta) return alpha;" is not wrong but sub-optimal. You can already prune on "alpha >= beta" (in your original algorithm: "-max <= maxEval). In this case the current move refutes the opponent's previous move by showing that it can't be good enough to be an improvement. The real value of the previous move might even turn out to be worse than at the time of pruning when continuing without pruning, but at least you know that it will have no influence on the value of the root node.

3. Also unusual is the termination condition "depth == 1" which lets you stop one ply too early unless you call the search() function with something like "maxDepth+1" as depth parameter. Better use "depth == 0" to determine a leaf.

I hope this helps you to advance a little bit.

Sven

(EDIT: Sorry for missing all the other answers in the meantime, I took a long break while writing my answer but did not check again for new answers when resuming.)

[Fguy64]

...
3. Also unusual is the termination condition "depth == 1" which lets you stop one ply too early unless you call the search() function with something like "maxDepth+1" as depth parameter. Better use "depth == 0" to determine a leaf.

I hope this helps you to advance a little bit.

Sven

(EDIT: Sorry for missing all the other answers in the meantime, I took a long break while writing my answer but did not check again for new answers when resuming.)

Thanks Sven, it will take some time to do your post justice. I hope to get back to you this weekend sometime. By the weekend I expect to have found the time to look closely at your post. Maybe sooner.

At this point, Just one comment about my termination condition. You are not the first to mention this, so I am aware of the issue, I'll definitely give it some thought, but I wonder if we are not just talking semantics. What I call ply=1 may really be ply=0 to someone else.

Would it shed any light if I were to tell you that in order to solve mate in n (full moves, not half moves), I have to set the ply to 2*n. That is because mate is only determined at the 2*nth play because there are no legal responses, at which point I do an isSquareAttacked() on the king position to determine mate or stalemate.

[Fguy64]

...
3. Also unusual is the termination condition "depth == 1" which lets you stop one ply too early unless you call the search() function with something like "maxDepth+1" as depth parameter. Better use "depth == 0" to determine a leaf.

I hope this helps you to advance a little bit.

Sven

(EDIT: Sorry for missing all the other answers in the meantime, I took a long break while writing my answer but did not check again for new answers when resuming.)

Thanks Sven, it will take some time to do your post justice. I hope to get back to you this weekend sometime. By the weekend I expect to have found the time to look closely at your post. Maybe sooner.

At this point, Just one comment about my termination condition. You are not the first to mention this, so I am aware of the issue, I'll definitely give it some thought, but I wonder if we are not just talking semantics. What I call ply=1 may really be ply=0 to someone else.

Would it shed any light if I were to tell you that in order to solve mate in n (full moves, not half moves), I have to set the ply to 2*n. That is because mate is only determined at the 2*nth play because there are no legal responses, at which point I do an isSquareAttacked() on the king position to determine mate or stalemate.

OK one other issue is the difference between a min-max algorithm and a negamax algorithm. On his introductory page Moreland describes negamax as "min-max with an optimization". It's not clear to me what he means by "an optimization". It really does look like the same thing, just expressed a little differently. Here is the link for your convenience.
http://web.archive.org/web/200404270153 ... minmax.htm

[Aaron Becker]

The optimization he's referring to is the fact that negamax as he presents it requires much less code than separate min and max functions. They do exactly the same thing, with the same efficiency.