mate detetion issue.

[adams161]

hi,

I reccently started programming a connect 4 bot that runs on icc. Starting fresh with alpha beta searching on connect 4 has given me a fresh perspective and allow me to better see how things work. Its a lot simpler model to work with than chess. you have 8 possible moves at most and there is only one type of move, the drop.

One thing i noticed was on mate, i was returning the mate score. I think i do the same in pulsar. If this score is greater than beta, there is no point in returning it as they wont play a score that is worse than their alpha. So you might as well return beta. I dont think returning a score higher than beta hurts.

the second thing i noticed does have a consequence i think. if the score is not greater than beta but is greater than alpha you want to return the mate score. but if the score is lower than alpha you would want to return alpha. I think i've been returning the mate score. The problem with this i think is that they could think they have found a better move. Not sure exactly.

So what i think should be done is only return an exact mate score if it would change alpha other wise return alpha or beta on mate. and the same could be said of draw scores.

the fresh perspective of connect 4 is helping a lot i think. it gives me a model to work on were i dont feel as invested with legacy code an ideas as i do with my chess program. much easier to just think about things.

thoughts welcome.

Mike

[hgm]

It sounds like you are trying to re-invent hard fail vs soft fail...

[adams161]

i noticed somethign else from my connect 4 program that makes me wonder about my chess program. my chess program quiescent search is kind of like this.

value=evaluate(side);
if(value>=beta)
return beta;
if(value>alpha)
alpha=value

for(a = 1 to macapture moves)
{
make move
searchquiescentagain
unmake move

if(value >=beta)
return beta;
if(value> alpha)
alpha =value;

} // end moves

return alpha



now here is the problem i see comparing to connect 4. i found that after the last move is made in connect 4 you want to return the evaluate score no matter what. no > alpha or > beta, just return it. its the score of the last move and the guy who made the last move can campare it to his alpha and beta at ply - 1.

here i call quiescent at the last ply of search and in quiescent alpha and beta are no longer the same as what existed for the person who makes the last move. lets say there areno captures in this stage of the game. i search to depht 3 in search. then i'm at kind of a depth 4 in quiescent. the way i got it set up is that if the guy to move on depth 4 doent move , he still gets to not return the score unless its > alpha or greater than beta **his** not the guy who made the last move on ply 3. if i made the last move it seems i should get my score? is there some way to do this properly?

mike

[hgm]

Being above your beta at ply, means that the other guy is below his alpha at ply-1, and vice versa. The seach-window limits do not really change from ply to ply. Only the fact that you use negamax, and thus change the score scale to the other POV, makes that you have to translate the previous alpha and beta to the new scale. But they really remain the same, if you look at what has to be on the board to exceed them.

[adams161]

i have no problem with the code:

score=evaluate(side)
if(score>=beta)
return beta

that is fine. you are correct he is below his alpha.

what i have a problem with is that with the psedo code, if at that ply ( counting the first quiescent as previous ply + 1) if he doesnt move, me at ply -1 doesnt get the score with my pseudo code unless ( well here is how the rest goes.

if(score>alpha)
alpha = score;

then the loop through moves but if no moves are found that can be made, i do this:

return alpha.

notice score is lost if its not > alpha. but that is the guy who didnt moves alpha. if score < alpha ( better for me who actually moved) the score is lost.

Mike

[hgm]

If score<=alpha in QS, you return alpha, which then still has the value it had when the routine was called, as indeed the evaluation score is discarded. Your alpha is, after negating the returned score, his beta. So the opponent will, at ply-1, see a score of beta, which is just enough for a cutoff. You fail low, he fails high.

Had you returned the true score despite the fact tat it was (much) below alpha, (soft fail), he would have seen a score (much) larget than beta. The result would have been the same: beta cutoff. So it does not matter.

[adams161]

i'm still not sure. what if alpha is 5 and beta is 9. if the score is 6 i play it, if its 7 i play it. if its > 9 its to good. but what if the score is -10. i dont play it. but if i played it the other guy would have 10 returned. the way i have it set up now the other guy on the previous ply cant see his score improve. whoever has teh grace of being the terminal node, sees his score improve, even if he didnt move. so once i make my first move on the previous ply, when i reach the terminal ply and the guy doesnt move, whatever he scores first becomes the score or if a score is better than that he scores it. but if the score gets worse asi try different moves, for the guy who doesnt move that is, i dont get the benefits of knowing i made better moves.

Mike

[hgm]

whoever has teh grace of being the terminal node, sees his score improve, even if he didnt move.

Indeed, that is how hard fail works. Your score improves, but not enough. In stead of the other guy seeing +10, he now sees minus you alpha, which is -5. But that was originally his beta.

So in stead of +10, he sees beta. And that is enough for a cutoff. He does not care if your score is +10 or -5, both are >= (his) beta, so he know that you will avoid this line by deviating earlier on the branch.

[adams161]

i thought about it last night and realied there should be no way that score less than alpha returned should not produce a beta cuttoff. but i was perlexed as fourbot seemed to be playing better with returning score < alpha, but today i discorved my data may have been skewed. i had a major evaluate bug. it was winning games against most everyone but this strong connect 4 player kept beating it. today with the evaluate bug fixed it has currently beat him 2 in a row, including a win were it went second.

Mike

[adams161]

looking fixed. its gone 8 1/2 vs 2 1/2 against this strong connect 4 player. it doesnt have a book ( anyone know where to get connect 4 books for first few moves ? ) so the player was able to explore the line playing both sides to see how the computer would move and get his wins.

Mike