Hi everyone,

I'm facing a problem with negamax. Think it comes from my eval function but i'm not sure at all.
First, can you tell me if my negamax and his call are ok ?
Because i don't find any solution, even if i read a lot about it these days.

Before showing you the code, i have to tell you that my verification function is based on (x,y) position (correspond to the last coin inserted with X = column and Y = line). Is this a portable method with negamax/alpha-beta or do i have to check the entire grid ?

Here is my negamax function:

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;

if (profondeur == 0)
{
return IA_Evaluation(grille, emplacements, colonne, emplacement, joueur);
}

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

return 1000;
}

if (GrillePleine(emplacements))
{
return 0;
}
for(i = 0; i < COLONNES && alpha < beta; i++)
{
// EFFICACITE: Balayer les colonnes du milieu vers l'extérieur (alternativement gauche/droite)
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;
}


Is there something wrong in it ?


And here comes my negamax call:

int x = COLONNES/2, y, i, k = 1, scoreCoup, scoreMeilleur = -1000000, col = -1;

for(i = 0; i < COLONNES; i++)
{
// EFFICACITE: Balayer les colonnes du milieu vers l'extérieur (alternativement gauche/droite)
x += i*k;
k = -k;
if (emplacements[x] > -1)
{
y = InsererJeton(grille, emplacements, x, joueur);
scoreCoup = IA_NegaMaxAlphaBeta(4, -100000, 100000, grille, emplacements, colonne, emplacement, joueur);
if (scoreCoup > scoreMeilleur)
{
scoreMeilleur = scoreCoup;
col = x;
}
AnnulerJeton(grille, emplacements, y, x);
}
}


If you want to see my eval function, just ask. I don't show it right now because there are maybe errors in my negamax.


Oh and by the way... Sorry for my english if i made mistakes ! I'm from Belgium
Thanks in advance for your help !

x += i*k;
k = -k;
That's cute, but probably incorrect. You may want to add (i+1)*k to x instead.

Or even better, you may want to wait until you have a working search before you add any embelishments of this type.

EDIT: Nevermind, I now think that is correct. I still would take it out until you know your search is working.

I totally agree with your point of view, but my grid (columns) is [0,6] so grid[7] is overflow.

See with my code:

- explore column 3
- explore column 2
- explore column 4
- explore column 1
- explore column 5
- explore column 0
- explore column 6


But if i add 1 to i like you said before, it's going to be wrong:



- explore column 4
- explore column 2
- explore column 5
- explore column 1
- explore column 6
- explore column 0
- explore column 7


Any other error except that one ?

I can't find any flaws in your code. Perhaps you should try debugging a depth-1 search first and see how that goes.

Don't you think that the problem may come from my grid's verification method ?
Because it doesn't scan the entire grid, but just all the directions from the last coin inserted.
I can see there is a big problem with all of it but can't find it

About my eval function, i know it's not good at all so it's maybe the problem. Anyway, do you want me to show that function ?

Almost regardless of what the evaluation function returns, your program should be able to find forced victories and avoid tactical losses. Looking only at the last toekn inserted should work just fine to check if the game was won by the player that just played.

But feel free to post the code and I'll take a look.

Also, could you describe what the actual problem is? Perhaps you can show us a position that you think shows the program is not working well.

If you don't see any problem in my negamax, it probably comes from the eval function.

Have a look (debug function):


Test column 3
Test column 2
Test column 4
Test column 1
FREE column 1 / SCORE: 1000
BEST column 1 (score 1000)
Test column 5
FREE column 5 / SCORE: 900
Test column 0
FREE column 0 / SCORE: 1000
Test column 6
FREE column 6 / SCORE: 1000


Seems to be OK except for scores so i guess it comes from eval.
In this example, it's not the case here, but almost every time i've the same score for all the columns... So it cannot work.

Here is my eval crap:


int IA_Evaluation(int grille[LIGNES][COLONNES], int emplacements[COLONNES], int colonne, int emplacement, int joueur)
{
int score = 0, flag = check(grille, emplacements, colonne, emplacement, joueur);

if (flag == 4)
{
if (joueur == 0)
{
return -1000;
}

return 1000;
}

if (flag == 3)
{
if (joueur == 0)
{
return -900;
}

return 900;
}

if (flag == 2)
{
if (joueur == 0)
{
return -600;
}

return 600;
}

if (flag == 1)
{
if (joueur == 0)
{
return -300;
}

return 300;
}

return 0;
}


While it is perfectly OK to use your `check' function to detect the victory condition of the game, it is not OK to use if for evaluation purposes. But I would just start with an evaluation function that returns 0 every time and see if you program can find quick tactical wins in easy cases.

And I would still like to see a position together with a description of what the program does and what you think it should do. It's hard to diagnose a disease without knowing any of the symptoms.

You're right. When i posted, i thought it was a problem with my negamax so i didn't continue with deep tests.
I'm going to have a closer look to it and test it just like you said.

I'll let you know as soon as possible (like tomorrow if i can).
Thank you