View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Problem in C with NegaMax / Alpha-Beta (Connect 4)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

59 replies to this topic

### #21Giustino  Members

Posted 24 May 2012 - 01:31 PM

Ok i'll have a look.

For my example, here is a cleaner explanation:
Test column 3
FREE column 3 / SCORE: 1000
BEST column 3 (score 1000)
Test column 2
FREE column 2 / SCORE: 1000
Test column 4
FREE column 4 / SCORE: 1000
Test column 1
FREE column 1 / SCORE: 1000
Test column 5
FREE column 5 / SCORE: 1000
Test column 0
FREE column 0 / SCORE: 3
Test column 6
FREE column 6 / SCORE: 1000


produced by:

Can you see the problem ? It always happened in those cases.

This is weird...

Initial call for negamax:
When i changed the code you've shown above, goes wrong.
But like this, it works (except the problem i've told before):

y = InsererJeton(grille, emplacements, x, joueur^1);
scoreCoup = IA_NegaMaxAlphaBeta(4, -1000000000, 1000000000, grille, emplacements, colonne, emplacement, joueur);


Is it normal that i've to write "!joueur" and not simply "joueur" ?

Edited by Giustino, 24 May 2012 - 02:15 PM.

### #22Álvaro  Members

Posted 24 May 2012 - 02:22 PM

I edited my previous post. It looks like your initial call to IA_NegaMaxAlphaBeta was pretty messed up. It should be virtually identical to the recursive call made inside of IA_NegaMaxAlphaBeta, except instead of beta you can use the fixed value 1000000000.

Edited by alvaro, 24 May 2012 - 02:22 PM.

### #23Giustino  Members

Posted 24 May 2012 - 02:41 PM

Think i tried that too, but i'm going to test it and i'll tell you.

Yep i already tested it. makes things worse (let's just say... not better).
Where can be the problem ?

Edited by Giustino, 24 May 2012 - 02:48 PM.

### #24Álvaro  Members

Posted 24 May 2012 - 03:45 PM

I would change the depth from 4 to 1 or even 0 and try to use a debugger to see what's going on.

### #25Giustino  Members

Posted 24 May 2012 - 04:27 PM

Ok, it works better since i've changed something in my eval function.
But there is still the same problem... When it can loose, it doesn't block the player (because the score of that column is the lower -> OK for the MIN but should be the biggest value to make things right).
Do you understand what i mean ? It's the same thing i told you above, just look at the image and the debug code to help you if it's not clear in your mind.
I really don't know what could be crap in all of that

### #26Álvaro  Members

Posted 24 May 2012 - 04:37 PM

At this point it's not clear to me exactly what code you are running. Please, post your code, the position on which you think it's doing the wrong thing, what it's doing, and what you think it should be doing.

### #27Giustino  Members

Posted 24 May 2012 - 05:03 PM

When AI can win, it does. But when it can lose, it doesn't block me.
Here are 2 examples:

1) When it can win

Scores returned by columns:
Test column 3
FREE column 3 / SCORE: 107
BEST column 3 (score 107)
Test column 2
FREE column 2 / SCORE: 105
Test column 4
FREE column 4 / SCORE: 105
Test column 1
FREE column 1 / SCORE: 103
Test column 5
FREE column 5 / SCORE: 1000
BEST column 5 (score 1000)
Test column 0
FREE column 0 / SCORE: 102
Test column 6
FREE column 6 / SCORE: 102


It's ok because if you look on the screenshot, AI (in yellow) wins it in column 5.

2) When it can lose

Scores returned by columns:
Test column 3
FREE column 3 / SCORE: 1000
BEST column 3 (score 1000)
Test column 2
FREE column 2 / SCORE: 105
Test column 4
FREE column 4 / SCORE: 1000
Test column 1
FREE column 1 / SCORE: 1000
Test column 5
FREE column 5 / SCORE: 1000
Test column 0
FREE column 0 / SCORE: 1000
Test column 6
FREE column 6 / SCORE: 1000


As you can see, it should have play in column 2 to block me. But it didn't because column 2 has the lower score (and it's everytime like that )
So the first highest score it sees is: column 3 (with 1000).

Can you see the problem ?

### #28Álvaro  Members

Posted 24 May 2012 - 07:25 PM

I think I've found the problem:
if (check(grille, emplacements, colonne, emplacement, joueur) == 4)
{
if (joueur == 0)
{
return -1000;
}

return 1000;
}


That code should just be

if (check(grille, emplacements, colonne, emplacement, joueur) == 4)
{
return -1000;
}


If the previous player just won, you lost, regardless of whether you are player 0 or 1.

### #29Giustino  Members

Posted 25 May 2012 - 04:30 AM

Still the same.
Here is all my code, maybe you'll find something wrong:

Negamax function (think it's all good for this one)
int IA_NegaMaxAlphaBeta(int profondeur, int alpha, int beta, int grille[LIGNES][COLONNES], int emplacements[COLONNES], int colonne, int emplacement, int joueur)
{
int x = COLONNES/2, y, i, k = 1, nbAlign;

nbAlign = check(grille, emplacements, colonne, emplacement, joueur);
if (nbAlign == 4)
{
return -1000;
}

if (GrillePleine(emplacements))
{
return SCORE_NUL;
}

if (profondeur == 0)
{
return IA_Evaluation(grille, joueur, nbAlign);
}

for(i = 0; i < COLONNES && alpha < beta; i++)
{
x += i*k;
k = -k;

if (emplacements[x] > -1)
{
y = InsererJeton(grille, emplacements, x, joueur);
alpha = max(alpha, -IA_NegaMaxAlphaBeta(profondeur-1, -beta, -alpha, grille, emplacements, x, y, joueur^1));
AnnulerJeton(grille, emplacements, y, x);
}
}

return alpha;
}


The eval function (maybe the way i've returned the score is wrong ?)
int IA_Evaluation(int grille[LIGNES][COLONNES], int joueur, int nbAlign)
{
int x, y, colscore, rowscore, score = 0;

for(y = 0; y < LIGNES; y++)
{
rowscore = abs((LIGNES/2) - y);
rowscore = (LIGNES/2) - rowscore;

for(x = 0; x < COLONNES; x++)
{
colscore = abs((COLONNES/2) - x);
colscore = (COLONNES/2) - colscore;

if (grille[y][x] == 0)
{
score -= (rowscore + colscore);
}
else
{
if (grille[y][x] == 1)
{
score += (rowscore + colscore);
}
}
}
}

if (nbAlign == 3)
{
if (joueur == 0)
{
score -= SCORE_3J;
}
else
{
score += SCORE_3J;
}
}
else
{
if (nbAlign == 2)
{
if (joueur == 0)
{
score -= SCORE_2J;
}
else
{
score += SCORE_2J;
}
}
else
{
if (nbAlign == 1)
{
if (joueur == 0)
{
score -= SCORE_1J;
}
else
{
score += SCORE_1J;
}
}
}
}

if (joueur == 0)
{
return score;
}

return -score;
}


And the initial call to negamax (you've suggested a minus sign on negamax but i can't find that anywhere, it's every time without minus sign when it's initial call).
However, i have to make something strange just before calling negamax (insert coin "joueur^1" instead of "joueur" and that's not logic).
This is the initial code as right now:
int x = COLONNES/2, y, i, k = 1, scoreCoup, scoreMeilleur = -INFINI, col = -1;

for(i = 0; i < COLONNES; i++)
{
x += i*k;
k = -k;
if (emplacements[x] > -1)
{
y = InsererJeton(grille, emplacements, x, joueur^1);
scoreCoup = IA_NegaMaxAlphaBeta(MAXPROFONDEUR, -INFINI, INFINI, grille, emplacements, colonne, emplacement, joueur);
if (scoreCoup > scoreMeilleur)
{
scoreMeilleur = scoreCoup;
col = x;
}
AnnulerJeton(grille, emplacements, y, x);
}
}


Edited by Giustino, 25 May 2012 - 04:39 AM.

### #30Álvaro  Members

Posted 25 May 2012 - 07:16 AM

Your initial call is obviously broken, and even you recognize that there's something wrong with it. So write it correctly:
• The call to InsererJeton should use joueur without the "^1".
• The return value of IA_NegaMaxAlphaBeta should be negated.
• The initial call to IA_NegaMaxAlphaBeta should have "joueur^1" and -scoreCoup as beta, instead of INFINI.
• Also, why are you not passing x and y to IA_NegaMaxAlphaBeta as you do in the recursive call? Fix that too.
If all that doesn't work, find an easy position where it does the wrong thing (you already had a good one earlier, but I don't know if that one will still fail), try to reduce MAXPROFONDEUR as much as possible while still showing the problem, and then use a debugger. If you don't know how to use a debugger effectively, this is about the best opportunity you'll find.

### #31Álvaro  Members

Posted 25 May 2012 - 07:17 AM

By the way, we discussed the negation of the return value of the initial call to the search function in this forum a while back: http://www.gamedev.net/topic/586896-starting-call-to-negamax/

### #32Giustino  Members

Posted 25 May 2012 - 07:28 AM

• The initial call to IA_NegaMaxAlphaBeta should have "joueur^1" and -scoreCoup as beta, instead of INFINI.

You mean -scoreMeilleur no ?

• Also, why are you not passing x and y to IA_NegaMaxAlphaBeta as you do in the recursive call? Fix that too.

I do. "colonne" is x and "emplacement" is y.

By the way, we discussed the negation of the return value of the initial call to the search function in this forum a while back: http://www.gamedev.n...all-to-negamax/

Yep i've read it. But every connect 4 i saw work with a positive initial call for negamax, so what's the best solution ?

### #33Álvaro  Members

Posted 25 May 2012 - 07:40 AM

• The initial call to IA_NegaMaxAlphaBeta should have "joueur^1" and -scoreCoup as beta, instead of INFINI.

You mean -scoreMeilleur no ?

Yes, I do. Sorry about that.

• Also, why are you not passing x and y to IA_NegaMaxAlphaBeta as you do in the recursive call? Fix that too.

I do. "colonne" is x and "emplacement" is y.

I am afraid that is incorrect. "colonne" and "emplacement" are probably "x" and "y" of the previous move. At least in the code you have provided, there is nothing that sets colonne and emplacement to x and y.

By the way, we discussed the negation of the return value of the initial call to the search function in this forum a while back: http://www.gamedev.n...all-to-negamax/

Yep i've read it. But every connect 4 i saw work with a positive initial call for negamax, so what's the best solution ?

It's not a matter of what option is best. First of all, your program needs to be correct.

You either make a single call to negamax for the root (but then you have to do something to extract the best move) or you write a function that searches the root and remembers the best move. If you use the first option, you don't negate the return value (you don't do much with the value, actually). If you use the second option -as you have-, then you negate the return value.

### #34Giustino  Members

Posted 25 May 2012 - 07:50 AM

Yes, I do. Sorry about that.

It doesn't matter, don't be sorry, i'm glag you help me.

I am afraid that is incorrect. "colonne" and "emplacement" are probably "x" and "y" of the previous move. At least in the code you have provided, there is nothing that sets colonne and emplacement to x and y.

Oh i see what you mean, sorry. Actually, my initial call is in a function, which is called after a player move.
So "colonne" contains the last column played by the player, and "emplacement" the line in the colonne.

### #35Álvaro  Members

Posted 25 May 2012 - 08:16 AM

Oh i see what you mean, sorry. Actually, my initial call is in a function, which is called after a player move.
So "colonne" contains the last column played by the player, and "emplacement" the line in the colonne.

I am afraid something still hasn't clicked in your head and that's why you are having trouble with this. The coordinates that you are passing to your search function are the location of the last move, and when you are calling it in the initial call, the last move performed is the one described in the InsererJeton' call of the previous line. So that's what you should be passing.

Does that make sense?

### #36Giustino  Members

Posted 25 May 2012 - 08:45 AM

Oops yes, you're totally right ! My bad, sorry !

So it would be logically like that:
y = InsererJeton(grille, emplacements, x, joueur);
scoreCoup = -IA_NegaMaxAlphaBeta(MAXPROFONDEUR, -INFINI, -scoreMeilleur, grille, emplacements, x, y, joueur^1);


But it doens't work. The only code that works is this one (and it's not logic):
y = InsererJeton(grille, emplacements, x, joueur^1);
scoreCoup = IA_NegaMaxAlphaBeta(MAXPROFONDEUR, -INFINI, INFINI, grille, emplacements, x, y, joueur);


Have you seen something similar to this before ?
I tried a lot to debug but can't find the crap.

### #37Álvaro  Members

Posted 25 May 2012 - 08:51 AM

What doesn't work?What happens when you do what we both agree is the right thing to do?

### #38Giustino  Members

Posted 25 May 2012 - 09:02 AM

y = InsererJeton(grille, emplacements, x, joueur);
scoreCoup = -IA_NegaMaxAlphaBeta(MAXPROFONDEUR, -INFINI, -scoreMeilleur, grille, emplacements, x, y, joueur^1);


With that code, i get some negatives scores.
So the one who should be chosen won't be because the biggest value is the lower with minus.
You feel me ? I know it's not so clear

Let's try an example:
I get -198 and -150 --> it should choose 198 (if it was positive) but the biggest here (because of minus sign) is 150.

Edited by Giustino, 25 May 2012 - 09:03 AM.

### #39Álvaro  Members

Posted 25 May 2012 - 09:48 AM

No, I don't follow. I want to see a position and the wrong move being picked.

### #40Giustino  Members

Posted 25 May 2012 - 10:52 AM

Ok let's do this step by step. The debug is with my initial call to negamax.

1) I'm the red one, and i play first in column 4.

2) AI plays in column 1

and here is the debug produced:
Test column 4
FREE column 4 / SCORE: -199
BEST column 4 (score -199)
Test column 3
FREE column 3 / SCORE: -198
BEST column 3 (score -198)
Test column 5
FREE column 5 / SCORE: -198
Test column 2
FREE column 2 / SCORE: -198
Test column 6
FREE column 6 / SCORE: -198
Test column 1
FREE column 1 / SCORE: -196
BEST column 1 (score -196)
Test column 7
FREE column 7 / SCORE: -196
`

As you can see, the best column to choose would have been column 4.
But all scores are negatives. So the biggest score (with no minus sign) becomes the lower score (with minus sign).
So it chooses column 1 (first column with lower value) because -198 < -196.

Is it clearer ?

And it continues like that for next steps.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.