• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Giustino

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

59 posts in this topic

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.
0

Share this post


Link to post
Share on other sites
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:
[CODE]
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
[/CODE]

It's ok because if you look on the screenshot, AI (in yellow) wins it in column 5.
[img]http://img109.imageshack.us/img109/9349/p41.png[/img]


2) When it can lose

Scores returned by columns:
[CODE]
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
[/CODE]

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 [img]http://public.gamedev.net//public/style_emoticons/default/mellow.png[/img] )
So the first highest score it sees is: column 3 (with 1000).
[img]http://img560.imageshack.us/img560/893/p42.png[/img]


Can you see the problem ?
0

Share this post


Link to post
Share on other sites
I think I've found the problem:
[code]if (check(grille, emplacements, colonne, emplacement, joueur) == 4)
{
if (joueur == 0)
{
return -1000;
}

return 1000;
}
[/code]

That code should just be

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

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

Share this post


Link to post
Share on other sites
Still the same.
Here is all my code, maybe you'll find something wrong:

Negamax function (think it's all good for this one)
[CODE]
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;
}
[/CODE]


The eval function (maybe the way i've returned the score is wrong ?)
[CODE]
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;
}
[/CODE]


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:
[CODE]
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);
}
}
[/CODE] Edited by Giustino
0

Share this post


Link to post
Share on other sites
Your initial call is obviously broken, and even you recognize that there's something wrong with it. So write it correctly:[list]
[*]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.
[/list]
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.
0

Share this post


Link to post
Share on other sites
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: [url="http://www.gamedev.net/topic/586896-starting-call-to-negamax/"]http://www.gamedev.net/topic/586896-starting-call-to-negamax/[/url]
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1337951767' post='4943224'][list]
[*]The initial call to IA_NegaMaxAlphaBeta should have "joueur^1" and -scoreCoup as beta, instead of INFINI.
[/list]
[/quote]

You mean -scoreMeilleur no ?



[quote name='alvaro' timestamp='1337951767' post='4943224'][list]
[*]Also, why are you not passing x and y to IA_NegaMaxAlphaBeta as you do in the recursive call? Fix that too.
[/list]
[/quote]

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



[quote name='alvaro' timestamp='1337951835' post='4943225']
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: [url="http://www.gamedev.net/topic/586896-starting-call-to-negamax/"]http://www.gamedev.n...all-to-negamax/[/url]
[/quote]

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 ?
0

Share this post


Link to post
Share on other sites
[quote name='Giustino' timestamp='1337952515' post='4943228']
[quote name='alvaro' timestamp='1337951767' post='4943224'][list]
[*]The initial call to IA_NegaMaxAlphaBeta should have "joueur^1" and -scoreCoup as beta, instead of INFINI.
[/list]
[/quote]

You mean -scoreMeilleur no ?[/quote]

Yes, I do. Sorry about that.

[quote][quote name='alvaro' timestamp='1337951767' post='4943224'][list]
[*]Also, why are you not passing x and y to IA_NegaMaxAlphaBeta as you do in the recursive call? Fix that too.
[/list]
[/quote]

I do. "colonne" is x and "emplacement" is y.
[/quote]

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.

[quote][quote name='alvaro' timestamp='1337951835' post='4943225']
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: [url="http://www.gamedev.net/topic/586896-starting-call-to-negamax/"]http://www.gamedev.n...all-to-negamax/[/url]
[/quote]

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 ?
[/quote]

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.
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1337953210' post='4943231']
Yes, I do. Sorry about that.
[/quote]

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


[quote name='alvaro' timestamp='1337953210' post='4943231']
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.
[/quote]

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.
0

Share this post


Link to post
Share on other sites
[quote name='Giustino' timestamp='1337953825' post='4943236']
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.
[/quote]

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?
0

Share this post


Link to post
Share on other sites
Oops yes, you're totally right ! My bad, sorry !

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

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

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

Share this post


Link to post
Share on other sites
[CODE]
y = InsererJeton(grille, emplacements, x, joueur);
scoreCoup = -IA_NegaMaxAlphaBeta(MAXPROFONDEUR, -INFINI, -scoreMeilleur, grille, emplacements, x, y, joueur^1);
[/CODE]

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 [img]http://public.gamedev.net//public/style_emoticons/default/laugh.png[/img]


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
0

Share this post


Link to post
Share on other sites
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

[b][img]http://img11.imageshack.us/img11/7594/p41h.png[/img][/b]

and here is the debug produced:
[CODE]
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
[/CODE]

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.
0

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 [img]http://public.gamedev.net//public/style_emoticons/default/mellow.png[/img]

[CODE]
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)
[/CODE]

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 [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img] Edited by Giustino
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
Ok but what is the way i have to return score from the eval function ?
Maybe that's why it doesn't work as expected.
0

Share this post


Link to post
Share on other sites
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'.
0

Share this post


Link to post
Share on other sites
Like that ? Because still doesn't work.

[CODE]
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;
[/CODE]
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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:

[CODE]
if (joueur == 0)
{
return score;
}
return -score;
[/CODE]

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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):
[CODE]
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
[/CODE]

And here is the debug code for all columns:
[CODE]
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
[/CODE]


Debug in my C code:
[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;
}
[/CODE]


Yeah i can upload it but there are parts in ASM, do you mind? Edited by Giustino
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0