Giustino

Members
  • Content count

    30
  • Joined

  • Last visited

Community Reputation

107 Neutral

About Giustino

  • Rank
    Member
  1. [quote name='alvaro' timestamp='1338127631' post='4943711'] So you have an Italian-sounding name, write your code in French and yet you are a Yankees fan? That's a strange combo. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] [/quote] Yep, it is a strange mix. But a good one [img]http://public.gamedev.net//public/style_emoticons/default/laugh.png[/img] [quote name='alvaro' timestamp='1338127631' post='4943711'] I never got into baseball and my wife is a Mets fan. [/quote] Damn... a Mets fan ! Condolences [quote name='alvaro' timestamp='1338127631' post='4943711'] 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! [/quote] I think so. But you are comfortable with alphabeta too, so don't worry [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Thanks again.
  2. 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 [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] And by the way... Hope you're a Yankee fan like i am [img]http://public.gamedev.net//public/style_emoticons/default/biggrin.png[/img] Come on Yankees !
  3. [quote name='alvaro' timestamp='1338044057' post='4943492'] That's a really strange notion of portability. [/quote] 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).
  4. [img]http://public.gamedev.net//public/style_emoticons/default/biggrin.png[/img] i totally agree with you [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img] 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.
  5. 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?
  6. 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.
  7. 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]
  8. 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.
  9. 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]
  10. 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.
  11. [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.
  12. 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.
  13. [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.
  14. [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 ?
  15. 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]