If the program thinks that it is losing, it makes sense to pick the move with the least negative score. Now, why moving in the center seems to have a lower score is a different issue. The first thing to get right is the winning conditions. Evaluation comes later.
So, if you set up positions with easy wins or where the program should block you, does it do the right thing?
0
Problem in C with NegaMax / Alpha-Beta (Connect 4)
Started by Giustino, May 23 2012 12:49 PM
59 replies to this topic
Sponsor:
#42 Members - Reputation: 105
Posted 25 May 2012 - 01:13 PM
The problem is that it picks up MAX score every time (in the list of scores - see the debug). If there wasn't a minus sign with all scores, it would be good.
I don't understand why negamax should return a negative score ?
The initial call to negamax doesn't make sense to me.
It is said that's the opposite
Or if i call it with joueur^1 (knowing that AI = joueur 1) it would call it with "0" and not "1".
I don't even talk about the minus sign to negamax.
I'm lost
I don't understand why negamax should return a negative score ?
The initial call to negamax doesn't make sense to me.
It is said that's the opposite
When called, the arguments α and β should be set to the lowest and highest values possible for any node [b]and color should be set to 1[/b]. (* Initial call *) negamax(origin, depth, -inf, +inf, 1)
Or if i call it with joueur^1 (knowing that AI = joueur 1) it would call it with "0" and not "1".
I don't even talk about the minus sign to negamax.
I'm lost
Edited by Giustino, 25 May 2012 - 01:23 PM.
#43 Members - Reputation: 6189
Posted 25 May 2012 - 01:48 PM
A score of 0 means that the game looks even. A positive score means that the player to move is ahead. A negative score means that the player to move is behind. Of course negamax can return negative values.
I don't know where you got that description of the arguments to negamax, but it is roughly correct (except I don't know what color=1 means).
Let me explain what your code is trying to do. The function that picks a move for the AI consists of a loop over all possible moves. For each move, you play it on the board and now you use negamax to compute a score for this move. When you call negamax, you are giving it a position where the opponent is about to move (hence `joueur^1') and the score returned will be positive if the opponent is happy with the situation and negative if he is unhappy. You flip the sign (as you do in the recursive call to negamax) to convert to the convention that positive means good for the player to move, not the opponent.
I don't know where you got that description of the arguments to negamax, but it is roughly correct (except I don't know what color=1 means).
Let me explain what your code is trying to do. The function that picks a move for the AI consists of a loop over all possible moves. For each move, you play it on the board and now you use negamax to compute a score for this move. When you call negamax, you are giving it a position where the opponent is about to move (hence `joueur^1') and the score returned will be positive if the opponent is happy with the situation and negative if he is unhappy. You flip the sign (as you do in the recursive call to negamax) to convert to the convention that positive means good for the player to move, not the opponent.
#45 Members - Reputation: 6189
Posted 25 May 2012 - 02:06 PM
You need to return a positive score if the player to move is ahead. You seem to be trying to reward having pieces around the center of the board, but I think you got the sign wrong: You are subtracting from the score when you find a `0' piece and adding when you find a `1' piece, but then you return score if `0' is to move and you flip the sign if `1' is to move, which seems to indicate that the meaning of score was from the point of view of player 0.
Try adding to the score when you find a `0' and subtracting when you find a `1'.
Try adding to the score when you find a `0' and subtracting when you find a `1'.
#46 Members - Reputation: 105
Posted 25 May 2012 - 02:13 PM
Like that ? Because still doesn't work.
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;
}
}
}
}
return score;
#47 Members - Reputation: 6189
Posted 25 May 2012 - 02:39 PM
I was talking about the first part of the evaluation function, where you give points for having pieces near the center. The part with nbAlign makes no sense to me. Actually, you probably shouldn't pass anything to the evaluation function than the position and the player to move.
And please don't just say it "doesn't work". What doesn't work? In what position? What did you expect it to do? What did it do instead? It's very frustrating. Imagine you are a doctor and a patient keeps coming back and telling you "I am still sick", and will not describe any symptoms.
And please don't just say it "doesn't work". What doesn't work? In what position? What did you expect it to do? What did it do instead? It's very frustrating. Imagine you are a doctor and a patient keeps coming back and telling you "I am still sick", and will not describe any symptoms.
#48 Members - Reputation: 105
Posted 26 May 2012 - 04:05 AM
Sorry about that but if i didn't tell you anything else it's because it was exactly the same problem i've shown you before.
I want to be sure about something...
How should i return the score from eval function ?
Currently it's:
Because if it's the right way to do, it looks like it does not block me anymore.
If my way of return a score is good, tell me and i'll show you what happened.
Just forget it. I force my eval function to return 0 by default because i'm debugging with a depth=1 and it looks like there is something strange.
I'll let you know as soon as possible.
I want to be sure about something...
How should i return the score from eval function ?
Currently it's:
if (joueur == 0)
{
return score;
}
return -score;
Because if it's the right way to do, it looks like it does not block me anymore.
If my way of return a score is good, tell me and i'll show you what happened.
Just forget it. I force my eval function to return 0 by default because i'm debugging with a depth=1 and it looks like there is something strange.
I'll let you know as soon as possible.
Edited by Giustino, 26 May 2012 - 04:45 AM.
#49 Members - Reputation: 6189
Posted 26 May 2012 - 05:35 AM
Yes, that way of returning the score is correct, assuming you write the rest of the evaluation function with the convention that positive scores are good for player 0 and negative ones are good for player 1. But you shouldn't get distracted by this if your search is still not working.
Could you just put the whole code somewhere I can download it? I have a bit of time this morning and I think I can fix it quickly.
Could you just put the whole code somewhere I can download it? I have a bit of time this morning and I think I can fix it quickly.
#50 Members - Reputation: 105
Posted 26 May 2012 - 06:07 AM
I found a problem but don't know yet where it could come from.
This debug is with depth=1 and eval function returns 0 by default.
You can see here something wrong happened (seems it's doing the same thing twice sometimes):
And here is the debug code for all columns:
Debug in my C code:
Yeah i can upload it but there are parts in ASM, do you mind?
This debug is with depth=1 and eval function returns 0 by default.
You can see here something wrong happened (seems it's doing the same thing twice sometimes):
INSERT COIN / AI (player 1) / column 4 CALL NEGAMAX: depth 1 / column 4 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) NEGAMAX INSERT COIN: column 3 (player 0) CALL NEGAMAX: depth 0 / column 3 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 3 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 3 (player 0) NEGAMAX INSERT COIN: column 5 (player 0) CALL NEGAMAX: depth 0 / column 5 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 5 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 5 (player 0) NEGAMAX INSERT COIN: column 2 (player 0) CALL NEGAMAX: depth 0 / column 2 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 2 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 2 (player 0) NEGAMAX INSERT COIN: column 6 (player 0) CALL NEGAMAX: depth 0 / column 6 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 6 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 6 (player 0) NEGAMAX INSERT COIN: column 1 (player 0) CALL NEGAMAX: depth 0 / column 1 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 1 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 1 (player 0) NEGAMAX INSERT COIN: column 7 (player 0) CALL NEGAMAX: depth 0 / column 7 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 7 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 7 (player 0) DELETE COIN / AI (player 1) / column 4
And here is the debug code for all columns:
INSERT COIN / AI (player 1) / column 4 CALL NEGAMAX: depth 1 / column 4 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) NEGAMAX INSERT COIN: column 3 (player 0) CALL NEGAMAX: depth 0 / column 3 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 3 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 3 (player 0) NEGAMAX INSERT COIN: column 5 (player 0) CALL NEGAMAX: depth 0 / column 5 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 5 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 5 (player 0) NEGAMAX INSERT COIN: column 2 (player 0) CALL NEGAMAX: depth 0 / column 2 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 2 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 2 (player 0) NEGAMAX INSERT COIN: column 6 (player 0) CALL NEGAMAX: depth 0 / column 6 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 6 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 6 (player 0) NEGAMAX INSERT COIN: column 1 (player 0) CALL NEGAMAX: depth 0 / column 1 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 1 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 1 (player 0) NEGAMAX INSERT COIN: column 7 (player 0) CALL NEGAMAX: depth 0 / column 7 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 7 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 7 (player 0) DELETE COIN / AI (player 1) / column 4 INSERT COIN / AI (player 1) / column 3 CALL NEGAMAX: depth 1 / column 3 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) DELETE COIN / AI (player 1) / column 3 INSERT COIN / AI (player 1) / column 5 CALL NEGAMAX: depth 1 / column 5 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) DELETE COIN / AI (player 1) / column 5 INSERT COIN / AI (player 1) / column 2 CALL NEGAMAX: depth 1 / column 2 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) DELETE COIN / AI (player 1) / column 2 INSERT COIN / AI (player 1) / column 6 CALL NEGAMAX: depth 1 / column 6 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) DELETE COIN / AI (player 1) / column 6 INSERT COIN / AI (player 1) / column 1 CALL NEGAMAX: depth 1 / column 1 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) DELETE COIN / AI (player 1) / column 1 INSERT COIN / AI (player 1) / column 7 CALL NEGAMAX: depth 1 / column 7 / player 0 NEGAMAX INSERT COIN: column 4 (player 0) CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED CALL NEGAMAX: depth 0 / column 4 / player 1 MAX DEPTH REACHED NEGAMAX DELETE COIN: column 4 (player 0) DELETE COIN / AI (player 1) / column 7
Debug in my C code:
int IA_Jouer(int grille[LIGNES][COLONNES], int emplacements[COLONNES], int joueur)
{
int x = COLONNES/2, y, i, k = 1, scoreCoup, scoreMeilleur = -INFINI, col = -1;
FILE *fichier = NULL;
fichier = fopen("test.txt", "w");
for(i = 0; i < COLONNES; i++)
{
// EFFICACITE: Balayer les colonnes du milieu vers l'extérieur (alternativement gauche/droite)
x += i*k;
k = -k;
//fprintf(fichier, "Test column %d\n", x+1);
if (emplacements[x] > -1)
{
y = InsererJeton(grille, emplacements, x, joueur);
fprintf(fichier, "INSERT COIN / AI (player %d) / column %d\n", joueur, x+1);
scoreCoup = -IA_NegaMaxAlphaBeta(MAXPROFONDEUR, -INFINI, -scoreMeilleur, grille, emplacements, x, y, joueur^1, fichier);
//fprintf(fichier, "FREE column %d / SCORE: %d\n", x+1, scoreCoup);
if (scoreCoup > scoreMeilleur)
{
//fprintf(fichier, "BEST column %d (score %d)\n", x+1, scoreCoup);
scoreMeilleur = scoreCoup;
col = x;
}
AnnulerJeton(grille, emplacements, y, x);
fprintf(fichier, "DELETE COIN / AI (player %d) / column %d\n\n\n\n", joueur, x+1);
}
}
fclose(fichier);
return col;
}
int IA_NegaMaxAlphaBeta(int profondeur, int alpha, int beta, int grille[LIGNES][COLONNES], int emplacements[COLONNES], int colonne, int emplacement, int joueur, FILE *fp)
{
int x = COLONNES/2, y, i, k = 1, nbAlign;
fprintf(fp, "CALL NEGAMAX: depth %d / column %d / player %d\n", profondeur, colonne+1, joueur);
nbAlign = check(grille, emplacements, colonne, emplacement, joueur);
if (nbAlign == 4)
{
fprintf(fp, "WIN: depth %d (player %d)\n", profondeur, joueur);
return -1000;
}
if (GrillePleine(emplacements))
{
fprintf(fp, "FULL GRID\n");
return SCORE_NUL;
}
if (profondeur == 0)
{
fprintf(fp, "MAX DEPTH REACHED\n");
return IA_Evaluation(grille, joueur, nbAlign);
}
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);
fprintf(fp, "NEGAMAX INSERT COIN: column %d (player %d)\n", x+1, joueur);
alpha = max(alpha, -IA_NegaMaxAlphaBeta(profondeur-1, -beta, -alpha, grille, emplacements, x, y, joueur^1, fp));
AnnulerJeton(grille, emplacements, y, x);
fprintf(fp, "NEGAMAX DELETE COIN: column %d (player %d)\n", x+1, joueur);
}
}
return alpha;
}
Yeah i can upload it but there are parts in ASM, do you mind?
Edited by Giustino, 26 May 2012 - 06:28 AM.
#52 Members - Reputation: 105
Posted 26 May 2012 - 07:11 AM
i totally agree with you But it's for a project and some parts need to be in Assembly.
I use __asm { } in my C code and it's compiled with VC 2008 so it should be OK for you.
Anyway i can replace ASM parts by C code if you prefer.
It's portable on Windows.
Edited by Giustino, 26 May 2012 - 07:45 AM.
#53 Members - Reputation: 6189
Posted 26 May 2012 - 08:54 AM
Except I am not familiar with Visual C, which means more work for me.I use __asm { } in my C code and it's compiled with VC 2008 so it should be OK for you.
Yes, that shifts the work to you, which is the right place. It will also make your program portable, which is a good thing.Anyway i can replace ASM parts by C code if you prefer.
That's a really strange notion of portability.It's portable on Windows.
#54 Members - Reputation: 105
Posted 26 May 2012 - 09:19 AM
That's a really strange notion of portability.
Yep but it's because of the cursor positionning and color system (more simple to test it with windows.h on my windows OS and then make it portable).
I gave you the download link (private msg).
Edited by Giustino, 26 May 2012 - 09:20 AM.
#56 Members - Reputation: 6189
Posted 26 May 2012 - 11:58 AM
I first stripped the code of anything Windows related and any input or output. I then added a printf statement to show the move and score when a new best move is found at the root. I changed `main' to set up a position and then call the IA once. Once I did that, it took about 2 minutes to produce a position where it wouldn't do the right thing (it wouldn't find a victory after 32 31 30), then 1 minute to run the debugger and find that the victory detection wasn't working.
You should really learn how to use a debugger effectively.
I have many thoughts on the coding style, but I'll save them, since perhaps it's better for you to try to get things working in your own style for a while.
You should really learn how to use a debugger effectively.
I have many thoughts on the coding style, but I'll save them, since perhaps it's better for you to try to get things working in your own style for a while.
#57 Members - Reputation: 105
Posted 27 May 2012 - 04:54 AM
You're right and finally i have to admit i didn't understand at 100% alphabeta, because i haven't been able to debug it myself.
I've had hard times with that, i'm almost ashamed.
But you were a great helper, thanks a lot alvaro, i really appreciate your help and your patience.
Keep going this way
And by the way... Hope you're a Yankee fan like i am Come on Yankees !
I've had hard times with that, i'm almost ashamed.
But you were a great helper, thanks a lot alvaro, i really appreciate your help and your patience.
Keep going this way
And by the way... Hope you're a Yankee fan like i am
Come on Yankees !
#58 Members - Reputation: 6189
Posted 27 May 2012 - 08:07 AM
So you have an Italian-sounding name, write your code in French and yet you are a Yankees fan? That's a strange combo.
I never got into baseball and my wife is a Mets fan.
By the way, the other Belgian with an Italian name I know is Gian Carlo Pascutto, and he probably knows a lot more about alphabeta than I do!
I never got into baseball and my wife is a Mets fan.
By the way, the other Belgian with an Italian name I know is Gian Carlo Pascutto, and he probably knows a lot more about alphabeta than I do!
Edited by alvaro, 27 May 2012 - 08:08 AM.
#59 Members - Reputation: 105
Posted 27 May 2012 - 10:13 AM
So you have an Italian-sounding name, write your code in French and yet you are a Yankees fan? That's a strange combo.
Yep, it is a strange mix. But a good one
I never got into baseball and my wife is a Mets fan.
Damn... a Mets fan ! Condolences
By the way, the other Belgian with an Italian name I know is Gian Carlo Pascutto, and he probably knows a lot more about alphabeta than I do!
I think so. But you are comfortable with alphabeta too, so don't worry
Thanks again.
#60 Members - Reputation: 220
Posted 28 May 2012 - 02:33 AM
Hello,
This might be a bit late, but i finally got my version af a Connect Four AI working (in C#). The link to my code is here:
https://sourceforge.net/projects/connectfour85/
Maybe this can help you out a little bit. My code is currently very simple, without any heuristics or alpha-beta pruning, but it seems to work correctly!
This might be a bit late, but i finally got my version af a Connect Four AI working (in C#). The link to my code is here:
https://sourceforge.net/projects/connectfour85/
Maybe this can help you out a little bit. My code is currently very simple, without any heuristics or alpha-beta pruning, but it seems to work correctly!
Interested in participating in a programming competition? Check out all available programming competitions on www.programmingcompetitions.com!
