[défi n°9] Si ça vous gratte...

Version imprimable

Voir 40 message(s) de cette discussion en une page

17/06/2005, 08h10
javatwister

[défi n°9] Si ça vous gratte...

Je vous propose un morpion!

:arrow: carte blanche sur le design mais le plus simple sera le mieux;
:arrow: l'ordinateur ne doit pas commettre d'erreur;
:arrow: l'ordinateur et le visiteur commencent à tour de rôle : une nouvelle partie démarre dès que la précédente est finie, tant que la page n'est pas rechargée; on peut donc compter les points sur X parties;

voilà voilà... ce serait bien :)
17/06/2005, 09h53
denisC

Avec ou sasn IA? Parcequ'avec une IA qui vaille le coup, c'est plus cher :)

Ceci dit, les cas au morpions sont suffisamment peux nombreux (2 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 = 254 divisible par 4 pour raisons de symétrie... soit en gros moins d'un centaine de cas) pour pouvoir en faire un imbattable. Mais c'est plus cher :)

Voila une version basique du morpion. Il est moche (si quelqu'un veux faire la feuille de style, il est bienvenu) et débile (jouer au hasard, c'est limité comme stratégie...) mais il marche.

Pour l'IA, il suffit de réécrire la fonction ordinateurJoue() pour qu'il fasse quelque chose d'un peu mieux.

Le code n'est pas factorisé à 100% mais il est assez propre. Les noms des fonctions sont normalement suffisamment explicites.

J'ai pas de serveur web à dispo, si quelqu'un veux bien le mettre en ligne pour voir ce que ça donne :)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
<html>
<head>
    <title>Morpion par denisC</title>
<script type="text/javascript">
    var jeu = new Array(0,0,0,0,0,0,0,0,0);
    var fini = 0;
 
    var gagneJoueur = 0;
    var gagneOrdinateur = 0;
 
    function clickCase(idCase) {
        // DEBUG : alert("clickCase!! : " + idCase);
        // DEBUG : alert("fini : " + fini + "\n jeu : " + jeu);
        if (fini!=1&&jeu[idCase]==0) {
            jeu[idCase]=1;
            placePion(idCase,1);
            if (gagne(1)) {
                partieFini(1);
            } else if (jeuFini()) {
                partieFini(0);
            } else {
                ordinateurJoue();
            }
        }
    }
 
    function gagne(joueur) {
        var joueurBool = 0;
        if (jeu[4] == joueur) {
            if (jeu[0] == joueur && jeu[8] == joueur) {
                //premiere diagonale
                joueurBool = 1;
            } else if (jeu[2] == joueur && jeu[6] == joueur) {
                //deuxieme diagonale
                joueurBool = 1;
            } else if (jeu[3] == joueur && jeu[5] == joueur) {
                //deuxieme ligne
                joueurBool = 1;
            } else if (jeu[1] == joueur && jeu[7] == joueur) {
                //deuxieme colonne
                joueurBool = 1;
            }
        } else if (jeu[0]==joueur) {
            if (jeu[1] == joueur && jeu[2] == joueur) {
                //premiere ligne
                joueurBool = 1;
            } else if (jeu[3] == joueur && jeu[6] == joueur) {
                //premiere colonne
                joueurBool = 1;
            }
        } else if (jeu[8]==joueur) {
            if (jeu[6] == joueur && jeu[7] == joueur) {
                //troisieme ligne
                joueurBool = 1;
            } else if (jeu[2] == joueur && jeu[5] == joueur) {
                //troisieme colonne
                joueurBool = 1;
            }
        }
        return joueurBool;
    }
 
    function jeuFini() {
        var finiBool = 1;
        for (var i=0; i<9; i++) {
            finiBool = finiBool && (jeu[i]!=0);
        }
        return finiBool;
    }
 
    function ordinateurJoue() {
        var place = Math.round(9*Math.random());
        while (jeu[place]!=0) {
            place = Math.round(9*Math.random());
        }
        jeu[place]=2;
        placePion(place,2);
        if (gagne(2)) {
            partieFini(2);
        } else if (jeuFini()) {
            partieFini(0);
        }
    }
 
    function placePion(idCase,joueur) {
        if (joueur==1) {
            document.getElementById('case'+idCase).firstChild.data = 'X';
        } else {
            document.getElementById('case'+idCase).firstChild.data = 'O';
        }
    }
 
    function partieFini(joueur) {
        fini = 1;
        if (joueur==1) {
            document.getElementById('message').firstChild.data = 'Vous avez Gagné';
            gagneJoueur++;
        } else if (joueur==2) {
            document.getElementById('message').firstChild.data = 'Vous avez Perdu';
            gagneOrdinateur++;
        } else {
            document.getElementById('message').firstChild.data = 'La partie est terminée : égalité';
        }
        document.getElementById('scoreJoueur').firstChild.data = gagneJoueur;
        document.getElementById('scoreOrdinateur').firstChild.data = gagneOrdinateur;
        document.getElementById('rejouer').style.display='block';
    }
 
    function rejouer() {
        for (var i=0; i<9; i++) {
            document.getElementById('case'+i).innerHTML = "&nbsp;";
            jeu[i]=0;
        }
        document.getElementById('message').firstChild.data = 'Partie en cours.....';
        document.getElementById('rejouer').style.display='none';
        fini = 0;
    }
</script>
<style  type="text/css">
    td {
        width: 100px;
        height: 100px;
    }
</style>
</head>
<body>
    <table border='1'>
        <tr>
            <td onclick='clickCase(0);' id='case0'>&nbsp;</td>
            <td onclick='clickCase(1);' id='case1'>&nbsp;</td>
            <td onclick='clickCase(2);' id='case2'>&nbsp;</td>
        </tr>
        <tr>
            <td onclick='clickCase(3);' id='case3'>&nbsp;</td>
            <td onclick='clickCase(4);' id='case4'>&nbsp;</td>
            <td onclick='clickCase(5);' id='case5'>&nbsp;</td>
        </tr>
        <tr>
            <td onclick='clickCase(6);' id='case6'>&nbsp;</td>
            <td onclick='clickCase(7);' id='case7'>&nbsp;</td>
            <td onclick='clickCase(8);' id='case8'>&nbsp;</td>
        </tr>
    </table>
    <div id='message'>Partie en cours.....</div>
    <div>
        Votre Score : <span id='scoreJoueur'>0</span> <br />
        Le Score de l'ordinateur :  <span id='scoreOrdinateur'>0</span>
    </div>
    <div id='rejouer' style='display:none;'>
        <a href='javascript:void(0);' onclick='rejouer();'>Recommencer une partie</a>
    </div>
</body>
</html>

17/06/2005, 11h30
javatwister

salut

attention, il faut que l'ordi soit "virtuellement" imbattable; finalement, c'est une sorte de moniteur pour apprendre à gagner au morpion;
j'ai pas le temps de tester ton code :cry:
à plus tard!
17/06/2005, 12h04
denisC

Bon, ben il faut que j'affine un peu mon IA. En jouant au hasard, il est pas vraiment imbattable :)
17/06/2005, 13h43
javatwister

ouais...

bon, prenez votre temps hein! comme d'habitude, je me réveille à l'approche du week-end et je sais que pas mal de membres sont HS jusqu'à lundi!
Pour une fois, comme le projet est plus complexe que les précédents, chacun peut tenter le coup, ce ne sera pas une course :wink:
17/06/2005, 15h05
fred777888999

Ptet que je vais pondre 1 ou 2 lignes ce WE, mais qu'est-ce que tu entends par morpion ? Un 3x3 ou un damier plus grand ? Un truc ou tu joue n'importe ou ou un 'puissance 4' ? un damier 3d 4x4x4 ou plus ?
17/06/2005, 20h12
Celelibi

fred777888999 à mon avis il parle du morpion classique, celui que tu fais (ou a fait) en cours en gravant la grille au compas sur la table pour jouer plusieurs fois avec ton voisin. :)

Je viens de finir ma dernière épreuve du BAC, je vais pouvoir vous coder ça.
rem : j'avais fait une AI pour un morpion sur ma casio. :)

Mais je ne suis pas sûr qu'une AI soit une bonne idée de challenge car il y a ceux qui ont fait des études d'informatique avec des cours d'algo qui vont être avantagés. Je suis sûr que beaucoup doivent connaitre l'algo alpha béta, ou A*. (perso je connais aucun des deux donc c'est réglé.) :)

ps : mon prochain message sera sûrement accompagné de mon code. ^^
Tant qu'on a pas de limite de lignes ça ira. :D
18/06/2005, 00h34
javatwister

allez, voilà mon essai:
http://javatwist.imingo.net/morpion.htm

je debuggerai ce week-end pour les finitions, hein;
18/06/2005, 01h29
Sub0

Joli boulot déjà! :ccool:
A tout hasard, ça serait compliqué d'obtenir une grille plus grande, 4x4 par exemple ?
J'aimerai bien arriver à en faire un Puissance 4 en me basant sur cette IA ...
Trop compliqué à ton avis ? Ça pourrait faire le défi n°10 éventuellement...
18/06/2005, 06h28
zebuman

salut
voici une proposition mais c'est pompé sur l'applet java tictactoe :wink:
Morpion
18/06/2005, 16h15
javatwister

pas mal... ça ressemble assez au mien d'un point de vue stratégique;

par contre le code est plutôt concis 8O
18/06/2005, 16h30
zebuman

Pour moi le défi a été de comprendre le code de l'applet :wink:
Avec les opérateurs bit à bit les positions sont représentées par un entier entre 0 et 2^9
En revanche je ne sais pas si l'idée peut être reprise pour un puissance 4, qui a plus de 32 cases...
18/06/2005, 17h15
javatwister

puissance 4, puissance 4... comme vous y allez!

pour moi, ça n'a pas grand chose à voir;
si j'avais à faire ça je remettrais la page à zéro et je réfléchirais dans une autre direction; à la limite, ça me semble plus facile :P
18/06/2005, 17h46
Sub0

ok, c'est ce que je voulais savoir : L'algo utilisé pour l'IA du morpion est difficilement utilisable pour une grille de taille différente... Il est probablement plus facile de faire l'inverse, c'est-à-dire, obtenir à partir d'une IA de P4, une IA pour le morpion... A part le fait qu'il n'est pas possible de poser le jeton sur n'importe quelle case, le principe reste le même -> Aligner un certain nombre de jetons (je pense que ce nombre devrait être une variable pour que le jeu soit un peu plus intéressant...), à+
18/06/2005, 17h55
javatwister

bon, déjà je vais essayer de passer en dessous de 200 lignes pour un morpion complet, je serai déjà content :?
18/06/2005, 18h26
Celelibi

sub0 en fait tu peux très bien adapter certains algo d'AI au puissance 4.
1) génération de l'ensemble des parties jouables
2) sélection du prochain coup à jouer dans l'ensemble des coups possibles tel que la probabilité de gagner soit la plus grande

Cet algo peut s'appliquer à n'importe quel jeu. même à un jeu d'échec :D
Par contre je vois mal JavaScript en train de générer un tableau de l'ensemble des parties jouables aux échec. :P
18/06/2005, 18h41
Sub0

Oui, je pense bien Celelibi, tu as raison. En fait, je supposais qu'il suffisait de modifier un paramètre, une variable de valeur égale à 3 pour pouvoir choisir les dimensions de la grille et en même temps du nombre de jetons à aligner... Voilà où je voulais en venir. Dans ce cas, il aurait été simple de modifier cet algo du morpion pour obtenir un autre jeu, le P4. Je pense que le fait de pouvoir choisir ce nombre est intéressant, même pour le jeu du morpion... Maintenant, c'est une simple idée, votre code actuel n'est pas remis en question, il est très bien. :ccool:
18/06/2005, 19h57
Celelibi

JT : ton AI je viens de lui mettre 5 - 0 en 10 parties. :)
Son jeu est trop prévisible, et quand on a gagné une fois il est très simple de reproduire la même partie plusieurs fois.

Au passage, tu as un problème avec ton setInterval : quand on gagne il n'est pas clearé. ^^

Sub0 tout dépend de l'algorithme utilisé. Si tu regarde celui de JT (le seul que j'ai regardé actuellement) il utilise certaines règles qui ne peuvent s'appliquer qu'à une grille 3*3.
18/06/2005, 21h28
javatwister

Citation:

Envoyé par Celelibi

JT : ton AI je viens de lui mettre 5 - 0 en 10 parties. :)
Son jeu est trop prévisible, et quand on a gagné une fois il est très simple de reproduire la même partie plusieurs fois.

bah, j'ai fait une erreur, voilà tout! tu parles de l'AI comme si tu croyais aux extra-terrestres :P
je verrai demain :wink:

ps: tu peux me dire où t'as trouvé le bug (genre, une capture d'écran), pour m'aider!
19/06/2005, 09h50
javatwister

houla, effectivement! ça sent la confusion de versions :P (j'ai 3 pages de tests différentes)

bon, voyons voir...
19/06/2005, 11h16
javatwister

à retester

le code n'est pas du tout économique mais bon, après tout, j'apprends à jouer hein :P
19/06/2005, 12h33
Invité
Celui de JT, quand on gagne c'est lui qui gagne les points...
Des fois c'est à lui de jouer, mais il joue pas...
L'autre de "je-sais-plus-qui" il fait une erreur très bête.
Code:

1 2 3 X?1 ?O? 2?X
Il ne faut surtout pas qu'il joue ni en 1, ni en 2 ! Sinon moi je joue soit en 1 ou en 2, et la c'est finit pour lui !
19/06/2005, 12h34
Celelibi

JT y'a encore un bug dans ton AI : quand on joue sur les cases 0, 5 ou 0, 7 ou 6, 5 l'ordinateur ne joue pas.
Une des parties gagnantes avec ton AI est : 0, 6, 5, 3.

Moi mon code avance, mais il s'annonce monstrueux. 140 lignes juste pour le constructeur et les méthodes du morpion, (sans le html) et j'ai pas encore commencé à programmer l'AI. :P
19/06/2005, 12h36
Celelibi

JT y'a encore un bug dans ton AI : quand on joue sur les cases 0, 5 ou 0, 7 ou 6, 5 l'ordinateur ne joue pas.
Une des parties gagnantes avec ton AI est : 0, 6, 5, 3.

Moi mon code avance, mais il s'annonce monstrueux. 140 lignes juste pour le constructeur et les méthodes du morpion, (sans le html) et j'ai pas encore commencé à programmer l'AI. :P

Au passage zebuman j'aime bien dans ton code la façon de représenter les grilles par des nombres. Je vais faire mon morpion+AI, après je l'optimiserais sûrement avec ça. :)
19/06/2005, 13h04
javatwister

correction du dernier bug en date?

Bon voilà mon premier code. Du bien lourd pour une AI déplorable (se contente de gagner ou ne pas perdre).
Il ne me reste plus "que" à ne pas jouer au hasard dans le cas par défaut.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr">
  <head>
    <title>Morbac</title>
    <style type="text/css">
    #morbac {
      table-layout: fixed;
      border-spacing: 1px;
      empty-cells: show;
      border: 3px outset #000;
      font-weight: bold;
    }
    #morbac td {
      width: 30px;
      height: 30px;
      border: 2px inset #000;
      text-align: center;
    }
    </style>
    <script type="text/javascript">
    function mor_joue (place) {
      if (this.lock) {
        alert("Impossible de jouer\n plus aucune partie n'est en cours");
        return false;
      }
      if (place < 0 || place > this.cases.length || this.grille[place]) {
        alert("Cette case est déjà prise");
        return false;
      }
      this.grille[place] = this.qui;
      this.cases[place].data = (this.qui == 1) ? 'X' : 'O';
      if (this.testFin()) {
        this.newPartie();
        return false;
      }
 
      if (this.qui == 1 && this.onplay1) {
        if (typeof this.onplay1 == 'function') this.onplay1(place);
        else if (typeof this.onplay1[0][this.onplay1[1]] == 'function') this.onplay1[0][this.onplay1[1]](place);
      } else if (this.qui == -1 && this.onplay2) {
        if (typeof this.onplay2 == 'function') this.onplay2(place);
        else if (typeof this.onplay2[0][this.onplay2[1]] == 'function') this.onplay2[0][this.onplay2[1]](place);
      }
      this.qui = -this.qui;
      if (this.qui == 1 && this.joueur1) {
        if (typeof this.joueur1 == 'function') this.joueur1(place);
        else if (typeof this.joueur1[0][this.joueur1[1]] == 'function') this.joueur1[0][this.joueur1[1]](place);
      } else if (this.qui == -1 && this.joueur2) {
        if (typeof this.joueur2 == 'function') this.joueur2(place);
        else if (typeof this.joueur2[0][this.joueur2[1]] == 'function') this.joueur2[0][this.joueur2[1]](place);
      }
      return true;
    }
 
    function mor_testGagne () {
      //parcours du tableau horizontalement
      for (var i=0; i<this.grille.length; i++) {
        if (i%this.taille == 0) var temp = 0;
        temp += this.grille[i];
 
        if ((i+1)%this.taille == 0 && temp == this.taille) {
          return 1;
        } else if ((i+1)%this.taille == 0 && temp == -this.taille) {
          return -1;
        }
      }
 
 
      //verticalement (double boucle à optimiser)
      for (var i=0; i<this.taille; i++) {
        var temp = 0;
        for (var j=0; j<this.taille; j++) {
          temp += this.grille[j*this.taille+i];
        }
 
        if (temp == this.taille) {
          return 1;
        } else if (temp == -this.taille) {
          return -1;
        }
      }
 
      var temp = 0, temp2 = 0;
 
      //en diagonal (les 2 en même temps)
      for (var i=0; i<this.taille; i++) {
        temp += this.grille[i*this.taille+i];
        temp2 += this.grille[(i+1)*this.taille-(i+1)];
      }
      if (temp == this.taille || temp2 == this.taille) {
        return 1;
      } else if (temp == -this.taille || temp2 == -this.taille) {
        return -1;
      }
      return 0;
    }
 
    function mor_testFin() {
      var win = this.testGagne();
 
      if (win) {
        this.total.data++;
        this.lock = true;
      }
 
      if (win == 1) {
        this.gagne1.data++;
        alert("Le joueur 1 à gagné");
      } else if (win == -1) {
        this.gagne2.data++;
        alert("Le joueur 2 a gagné");
      } else {
        //si personne n'a gagné c'est un match null ou un match pas terminé
        for (var i=0; i<this.grille.length; i++) {
          if (!this.grille[i]) return false;
        }
 
        //si la boucle se fini il n'y a plus de cases libres
        this.nuls.data++;
        this.total.data++;
        this.lock = true;
        alert("Match nul");
      }
      return true;
    }
 
    function mor_newPartie () {
      this.grille = new Array(this.taille*this.taille); //on ne fait que des grilles carrés
      for (var i=0; i<this.grille.length; i++) {
        this.grille[i] = 0; //undefined pose des problèmes
        this.cases[i].data = ' ';
      }
 
      this.qui = (this.total.data%2) ? -1 : 1;
      this.lock = false;
 
      if (typeof this.onnew == 'function') this.onnew();
      else if (typeof this.onnew[0][this.onnew[1]] == 'function') this.onnew[0][this.onnew[1]]();
 
      if (this.qui == 1 && this.joueur1) {
        if (typeof this.joueur1 == 'function') this.joueur1();
        else if (typeof this.joueur1[0][this.joueur1[1]] == 'function') this.joueur1[0][this.joueur1[1]]();
      } else if (this.qui == -1 && this.joueur2) {
        if (typeof this.joueur2 == 'function') this.joueur2();
        else if (typeof this.joueur2[0][this.joueur2[1]] == 'function') this.joueur2[0][this.joueur2[1]]();
      }
    }
 
    function mor_reset() {
      this.total.data = 0;
      this.gagne1.data = 0;
      this.gagne2.data = 0;
      this.nuls.data = 0;
      this.grille = new Array(this.taille^2);
      this.cases = new Array();
      for (var i=0; i<this.grille.length; i++) {
        this.cases[i].data = ' ';
      }
      this.lock = false;
    }
 
    function morpion_grille(taille, tablo, total, gagne1, gagne2, nuls) {
      this.lock = false;
      this.taille = taille;
      this.total = total.firstChild;
      this.gagne1 = gagne1.firstChild;
      this.gagne2 = gagne2.firstChild;
      this.nuls = nuls.firstChild;
      this.cases = new Array();
 
      var elts = tablo.getElementsByTagName('td');
      for (var i=0; i<elts.length; i++) {
        this.cases[i] = elts[i].firstChild;
      }
 
      this.joue = mor_joue;
      this.testGagne = mor_testGagne;
      this.testFin = mor_testFin;
      this.newPartie = mor_newPartie;
      this.reset = mor_reset;
    }
 
 
	/***************/
	/*Début de l'AI*/
	/***************/
 
    function AI_played(place) {
      this.grille[place] = -1;
    }
 
    function AI_joue() {
      var prochain = this.bestChoice();
      if (prochain == -1) {
        do {
          prochain = parseInt(Math.random()*this.grille.length);
        } while (this.grille[prochain]);
      }
      this.grille[prochain] = 1;
      if (typeof this.doPlay == 'function') this.doPlay(prochain);
      else if (typeof this.doPlay[0][this.doPlay[1]] == 'function') this.doPlay[0][this.doPlay[1]](prochain);
      return prochain;
    }
 
    function AI_meilleur () {
      var placeVideDiag1, placeVideDiag2, nextWin = -1, nextNotLose = -1, nbVideDiag1 = 0, nbVideDiag2 = 0, addDiag1 = 0, addDiag2 = 0;
      //win the yes, need the know to win, against the no !
      for (var i=0; i<3; i++) {
        var placeVideLigne, placeVideColone, nbVideLigne = 0, nbVideColone = 0, addLigne = 0, addColone = 0;
        for (var j=0; j<3; j++) {
          if (this.grille[i*3+j]) {
            addLigne += this.grille[i*3+j];
          } else {
            nbVideLigne++;
            placeVideLigne = i*3+j;
          }
          if (this.grille[j*3+i]) {
            addColone += this.grille[j*3+i];
          } else {
            nbVideColone++;
            placeVideColone = j*3+i;
          }
        }
 
        if (this.grille[i*3+i]) {
          addDiag1 += this.grille[i*3+i];
        } else {
          nbVideDiag1++;
          placeVideDiag1 = i*3+i;
        }
        if (this.grille[i*3+(2-i)]) {
          addDiag2 += this.grille[i*3+(2-i)];
        } else {
          nbVideDiag2++;
          placeVideDiag2 = i*3+(2-i);
        }
 
        if (nbVideLigne == 1 && addLigne == 2) {
          //on peut gagner :) (en faisant une ligne)
          nextWin = placeVideLigne;
        } else if (nbVideColone == 1 && addColone == 2) {
          //on peut gagner (en faisant une colone)
          nextWin = placeVideColone;
        }
 
        if (nbVideLigne == 1 && addLigne == -2) {
          nextNotLose = placeVideLigne;
        } else if (nbVideColone == 1 && addColone == -2) {
          nextNotLose = placeVideColone;
        }
      }
 
      //win diag
      if (nbVideDiag1 == 1 && addDiag1 == 2) {
        nextWin = placeVideDiag1;
      } else if (nbVideDiag2 == 1 && addDiag2 == 2) {
        nextWin = placeVideDiag2;
      }
      //not lose diag
      if (nbVideDiag1 == 1 && addDiag1 == -2) {
        nextNotLose = placeVideDiag1;
      } else if (nbVideDiag2 == 1 && addDiag2 == -2) {
        nextNotLose = placeVideDiag2;
      }
      return (nextWin != -1) ? nextWin : nextNotLose;
    }
 
    function AI_restart() {
      this.grille = new Array(9);
    }
 
    function AI_new(callPlay) {
      this.doPlay = callPlay;
      this.played = AI_played;
      this.joue = AI_joue;
      this.bestChoice = AI_meilleur;
      this.restart = AI_restart;
    }
 
    function init() {
      morpion = new morpion_grille(3, nodeGratte = document.getElementById('morbac'),
        document.getElementById('nbParties'),
        document.getElementById('nbGagne1'),
        document.getElementById('nbGagne2'),
        document.getElementById('nbNuls'));
      var cases = nodeGratte.getElementsByTagName('td');
      for (var i=0; i<cases.length; i++) {
        cases[i].onclick = new Function("morpion.joue("+i+")");
      }
 
      AI = new AI_new([morpion, 'joue']);
      morpion.onplay1 = [AI, 'played'];
      morpion.onnew = [AI, 'restart'];
      morpion.joueur2 = [AI, 'joue'];
      morpion.newPartie();
    }
    </script>
  </head>
  <body onload="init()">
    <div>Nombre de parties joués : <var id="nbParties">0</var></div>
    <div>Nombre de parties gagnés par <em>vous</em> : <var id="nbGagne1">0</var></div>
    <div>Nombre de parties gagnés par <em>l'autre</em> : <var id="nbGagne2">0</var></div>
    <div>Nombre de matchs nuls : <var id="nbNuls">0</var></div>
    <table id="morbac">
      <tr>
        <td> </td>
        <td> </td>
        <td> </td>
      </tr>
      <tr>
        <td> </td>
        <td> </td>
        <td> </td>
      </tr>
      <tr>
        <td> </td>
        <td> </td>
        <td> </td>
      </tr>
    </table>
  </body>
</html>

L'avantage d'avoir totalement séparé le jeu de morpion de l'AI c'est de pouvoir changer complètement l'un sans affecter l'autre.
De plus je peux faire jouer l'AI contre elle-même. :)

21/06/2005, 10h46
javatwister

ne pas perdre? 8O à voir... :P

ça y est j'ai trouvé un moyen de réduire mon mastodonte; après, tu trouveras sûrement des bugs :mrgreen:
21/06/2005, 13h26
Celelibi

Ne pas perdre dans le sens où il va se mettre dans la case vide si tu en a deux d'alignés.
En gros pour le moment il a un niveau gros débutant. :)

Citation:

ça y est j'ai trouvé un moyen de réduire mon mastodonte

T'as vu la taille du mien ? :p

Au passage, pour le moment quand je fais jouer mon AI contre elle-même, sur 100 parties j'obtiens 25 - 26 et 49 nuls. Avec une AI parfaite on devrait obtenir 0 - 0 et 100 nuls.

JT y'aurait pas moyen que tu modifie un peu ton jeu pour faire jouer ton AI contre elle-même. (oublies pas de désactiver la petite animation ;))
21/06/2005, 13h48
javatwister

ben c'est couru d'avance, si je fais ça j'aurai que des nuls!
21/06/2005, 16h08
javatwister

démo

et là tu vas voir qu'il n'y a pas 50 manières de gagner au morpion :wink:
23/06/2005, 12h55
javatwister

bon alors! grattez-vous les méninges quoi! c'est un défi open hein, je le rappelle :mrgreen:
23/06/2005, 16h08
Celelibi

Ne désespère pas je travaille encore sur mon AI.
Par contre ça va pas être un champion de vitesse. :p
23/06/2005, 16h14
denisC

C'est quoi le défi??? Faire un morpion qui ne perds jamais. C'est fait (pas super compliqué). Et donc, après, ou est le reste du défi???
23/06/2005, 17h10
Celelibi

Si tu trouves ça trop simple, fais ton AI de telle sorte à ce qu'elle puisse facilement évoluer et jouer sur une grille de 4*4 et n*n.

Aille c'est moins marrant

Après on pourrait peut-être faire s'affronter les différentes AI :P
Au passage denisC tu pourrais peut-être nous poster ton code qui joue pas au hasard. :)
23/06/2005, 17h53
javatwister

Citation:

Envoyé par Celelibi

Au passage denisC tu pourrais peut-être nous poster ton code qui joue pas au hasard.

tiens c'est vrai ça :mrgreen:

sinon, denis, je parlais pour les milliards de visiteurs quotidiens du forum, qui sont cordialement invités à faire péter toutes les logiques avec leurs inventions inédites :wink:

ou alors j'aurais dû proposer un monopoly? ou un pacman :roll:

en tout cas, si quelqu'un se sent prêt à lancer le défi "Puissance 4" c'est cool :ccool:

Voilà, j'ai fini mon AI.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr">
  <head>
    <title>Morbac</title>
    <style type="text/css">
    #morbac {
      table-layout: fixed;
      border-spacing: 1px;
      empty-cells: show;
      border: 3px outset #000;
      font-weight: bold;
    }
    #morbac td {
      width: 30px;
      height: 30px;
      border: 2px inset #000;
      text-align: center;
    }
    </style>
    <script type="text/javascript">
    function melange () {
      this.sort(function () { return Math.random()*3-1 });
    }
    Array.prototype.shuffle = melange;
 
    function mor_joue (place) {
      if (this.lock) {
        alert("Impossible de jouer\n plus aucune partie n'est en cours");
        return false;
      }
      if (place < 0 || place > this.cases.length || (this.grille[0] | this.grille[1]) & (1 << place)) {
        alert("Cette case est déjà prise");
        return false;
      }
      this.grille[this.qui] |= 1 << place;
      this.cases[place].data = (this.qui == 1) ? 'X' : 'O';
      if (this.testFin()) {
        this.newPartie();
        return false;
      }
 
      if (this.qui == 1 && this.onplay1) {
        if (typeof this.onplay1 == 'function') this.onplay1(place);
        else if (typeof this.onplay1[0][this.onplay1[1]] == 'function') this.onplay1[0][this.onplay1[1]](place);
      } else if (this.qui == 0 && this.onplay2) {
        if (typeof this.onplay2 == 'function') this.onplay2(place);
        else if (typeof this.onplay2[0][this.onplay2[1]] == 'function') this.onplay2[0][this.onplay2[1]](place);
      }
      this.qui = 1 - this.qui; //comme ça on alterme entre 0 et 1
      if (this.qui == 1 && this.joueur1) {
        if (typeof this.joueur1 == 'function') this.joueur1();
        else if (typeof this.joueur1[0][this.joueur1[1]] == 'function') this.joueur1[0][this.joueur1[1]]();
      } else if (this.qui == 0 && this.joueur2) {
        if (typeof this.joueur2 == 'function') this.joueur2();
        else if (typeof this.joueur2[0][this.joueur2[1]] == 'function') this.joueur2[0][this.joueur2[1]]();
      }
      return true;
    }
 
    function mor_testGagne () {
      //motifs d'alignement horizontaux et verticaux
      var hzalign = (1 << this.taille) - 1; // 111b
      var vzalign = 0;
      for (var i=0; i<this.taille; i++) vzalign |= (1 << i*this.taille); // 001'001'001b
 
      //parcours du tableau horizontalement et verticalement
      for (var i=0; i<this.taille; i++) {
        var horiz = hzalign << (i*this.taille);
        var vertz = vzalign << i; 
 
        if (((this.grille[0] & horiz) == horiz) || ((this.grille[0] & vertz) == vertz)) {
          return -1;
        } else if (((this.grille[1] & horiz) == horiz) || ((this.grille[1] & vertz) == vertz)) {
          return 1;
        }
      }
 
      var diag1 = 0, diag2 = 0;
      //en diagonal
      for (var i=0; i<this.taille; i++) {
        diag1 |= 1 << (i*this.taille + i);
        diag2 |= 1 << ((i+1)*this.taille - (i+1));
      }
      if (((this.grille[0] & diag1) == diag1) || ((this.grille[0] & diag2) == diag2)) {
        return -1;
      } else if (((this.grille[1] & diag1) == diag1) || ((this.grille[1] & diag2) == diag2)) {
        return 1;
      }
      return 0;
    }
 
    function mor_testFin() {
      var win = this.testGagne();
 
      if (win) {
        this.total.data++;
        this.lock = true;
      }
 
      if (win == 1) {
        this.gagne1.data++;
        alert("Le joueur 1 à gagné");
      } else if (win == -1) {
        this.gagne2.data++;
        alert("Le joueur 2 a gagné");
      } else {
        //si personne n'a gagné c'est un match null ou un match pas terminé
        //si il reste une case vide c'est pas fini
        if ((this.grille[0] | this.grille[1]) < 511) return false;
 
 
        //si la boucle se fini il n'y a plus de cases libres
        this.nuls.data++;
        this.total.data++;
        this.lock = true;
        alert("Match nul");
      }
      return true;
    }
 
    function mor_newPartie () {
      this.grille = new Array(0, 0); //on ne fait que des grilles carrés
      for (var i=0; i<this.cases.length; i++) {
        this.cases[i].data = ' ';
      }
 
      this.qui = (~this.total.data) & 1;
      this.lock = false;
 
      if (this.onnew) {
        if (typeof this.onnew == 'function') this.onnew();
        else if (typeof this.onnew[0][this.onnew[1]] == 'function') this.onnew[0][this.onnew[1]]();
      }
 
      if (this.qui == 1 && this.joueur1) {
        if (typeof this.joueur1 == 'function') this.joueur1();
        else if (typeof this.joueur1[0][this.joueur1[1]] == 'function') this.joueur1[0][this.joueur1[1]]();
      } else if (this.qui == 0 && this.joueur2) {
        if (typeof this.joueur2 == 'function') this.joueur2();
        else if (typeof this.joueur2[0][this.joueur2[1]] == 'function') this.joueur2[0][this.joueur2[1]]();
      }
    }
 
    function mor_reset() {
      this.total.data = 0;
      this.gagne1.data = 0;
      this.gagne2.data = 0;
      this.nuls.data = 0;
      this.grille = new Array(0, 0);
      this.cases = new Array();
      for (var i=0; i<this.cases.length; i++) {
        this.cases[i].data = ' ';
      }
      this.lock = false;
    }
 
    function morpion_grille(taille, tablo, total, gagne1, gagne2, nuls) {
      this.lock = false;
      this.taille = taille;
      this.total = total.firstChild;
      this.gagne1 = gagne1.firstChild;
      this.gagne2 = gagne2.firstChild;
      this.nuls = nuls.firstChild;
      this.cases = new Array();
 
      var elts = tablo.getElementsByTagName('td');
      for (var i=0; i<elts.length; i++) {
        this.cases[i] = elts[i].firstChild;
      }
 
      this.joue = mor_joue;
      this.testGagne = mor_testGagne;
      this.testFin = mor_testFin;
      this.newPartie = mor_newPartie;
      this.reset = mor_reset;
    }
 
 
	/***************/
	/*Début de l'AI*/
	/***************/
 
    function AI_played(place) {
      this.grille[0] |= 1 << place;
    }
 
    function AI_joue() {
      var scoreCases = new Array();
      for (var i=0; i<9; i++) {
        if ((this.grille[0] | this.grille[1]) & (1 << i)) continue;
        //elle est bien cette case ?
        scoreCases.push([i, this.bienLaCase(i, 1)]);
      }
      scoreCases.sort(function (a, b) {return b[1]-a[1];});
      while (scoreCases.length > 1) {
        if (scoreCases[0][1] > scoreCases[scoreCases.length-1][1]) scoreCases.pop();
        else break;
      }
      scoreCases.shuffle();
      var prochain = scoreCases[0][0];
      this.grille[1] |= 1 << prochain;
      if (typeof this.doPlay == 'function') this.doPlay(prochain);
      else if (typeof this.doPlay[0][this.doPlay[1]] == 'function') this.doPlay[0][this.doPlay[1]](prochain);
      return prochain;
    }
 
    function AI_bien (place, qui) {
      //juste un accélérateur, l'algo donnerait le même résultat
      //toutes les cases donne un score de 0 si on joue le premier
      if ((this.grille[0] | this.grille[1]) == 0) return 0;
 
      this.grille[qui] |= 1 << place;
      //win the yes, need the know to win... against the no !
      for (var i=0; i<this.winCombi.length; i++) {
        if ((this.grille[qui] & this.winCombi[i]) == this.winCombi[i]) {
          //si je peux gagner il FAUT jouer là
          //si ça lui permet de gagner il NE FAUT PAS jouer là
          this.grille[qui] &= ~(1 << place);
          return (qui == 1) ? 1 : -1;
        }
      }
      //si je ne peux ni gagner ni empêcher de gagner on regarde le coup suivant
      var scoreNext = new Array();
      for (var i=0; i<9; i++) {
        if ((this.grille[0] | this.grille[1]) & (1 << i)) continue;
        scoreNext.push([i, this.bienLaCase(i, 1-qui)]);
      }
      this.grille[qui] &= ~(1 << place);
      if (scoreNext.length == 0) return 0;
      scoreNext.sort(function (a, b) {return b[1]-a[1];});
      if (qui == 1) scoreNext.reverse();
      return scoreNext[0][1];
    }
 
    function AI_restart() {
      this.grille = new Array(0, 0);
    }
 
    function AI_new(callPlay) {
      this.winCombi = new Array();
      this.doPlay = callPlay;
      this.played = AI_played;
      this.joue = AI_joue;
      this.bienLaCase = AI_bien;
      this.restart = AI_restart;
 
      this.winCombi.push(7, 7 << 3, 7 << 6, 73, 73 << 1, 73 << 2, 273, 84);
    }
 
    function init() {
      morpion = new morpion_grille(3, nodeGratte = document.getElementById('morbac'),
        document.getElementById('nbParties'),
        document.getElementById('nbGagne1'),
        document.getElementById('nbGagne2'),
        document.getElementById('nbNuls'));
      var cases = nodeGratte.getElementsByTagName('td');
      for (var i=0; i<cases.length; i++) {
        cases[i].onclick = new Function("morpion.joue("+i+")");
      }
 
      AI = new AI_new([morpion, 'joue']);
      //AI2 = new AI_new([morpion, 'joue']);
      morpion.onplay1 = [AI, 'played'];
      //morpion.onplay2 = [AI2, 'played'];
      morpion.onnew = [AI, 'restart'];
      //morpion.onnew = function () { AI.restart(); AI2.restart();};
      morpion.joueur2 = [AI, 'joue'];
      //morpion.joueur1 = [AI2, 'joue'];
      morpion.newPartie();
    }
    </script>
  </head>
  <body onload="init()">
    <div>Nombre de parties joués : <var id="nbParties">0</var></div>
    <div>Nombre de parties gagnés par <em>vous</em> : <var id="nbGagne1">0</var></div>
    <div>Nombre de parties gagnés par <em>l'autre</em> : <var id="nbGagne2">0</var></div>
    <div>Nombre de matchs nuls : <var id="nbNuls">0</var></div>
    <table id="morbac">
      <tr>
        <td> </td>
        <td> </td>
        <td> </td>
      </tr>
      <tr>
        <td> </td>
        <td> </td>
        <td> </td>
      </tr>
      <tr>
        <td> </td>
        <td> </td>
        <td> </td>
      </tr>
    </table>
  </body>
</html>

Celui là est théoriquement imbattable.
De plus il est facilement adaptable pour une grille plus grande.
(Le constructeur grille lui il suffit de lui passer les bons paramètres pour qu'il s'adapte tout seul)

Après quelques recherches il semblerait que j'ai réinventé l'algo du MinMax. :P
Moi qui voulais juste attribuer un score à chaque coup jouable voilà qu'on me parle d'heuristique...

Je vais essayer d'accélérer la recherche avec le MinMax2 :) http://bertoul.com/index.php?link=minmax

23/06/2005, 20h30
Celelibi

Tien JT un autre bug dans ton AI.
Quand c'est ton AI qui commence et que je joue la séquence suivante (0 = première case) : 7, 2, 3, 6. L'AI gagne, mais dit "match nul".

Je suis en train de faire jouer mon AI contre la tienne. (2 onglets d'ouvert et je joue sur l'un ce que l'AI à joué sur l'autre). Mon AI viens de gagner une partie. :D
23/06/2005, 20h54
javatwister

ça m'étonnerait!

quand je joue 7-2-3, l'ordi gagne et ça s'arrête là!

mais aujourd'hui t'as raison, il m'a semblé avoir un message aberrant de ce genre :wink:

jolie ton AI 8)
24/06/2005, 02h42
Celelibi

Tu as raison ça commence pas par 7 mais 8, la partie qui fait buger est donc 8, 2, 3, 6.

Citation:

jolie ton AI 8)

Au niveau du code, de l'algo ou au niveau de la façon dont elle joue ?

La prochaine fois que tu donnes un défis de ce genre il faudrai que tu code avant une interface de jeu pour que tout le monde parte sur les mêmes bases et pouvoir ensuite faire s'affronter les AI. :)
Mon constructeur grille par exemple est totalement indépendant de l'AI.
Il va appeller une fonction ou une méthode défini par l'utilisateur à chaque fois que l'autre joueur a joué un coup ou quand on lui demande de jouer.
Et aussi pour quand on doit réinitialiser la partie.
(méthodes onplay, onnew et joueur2)

Je vais essayer d'intégrer mon AI dans ton jeu pour les faire jouer ensemble automatiquement. Ça m'a l'air plus simple que de faire le contraire. :P

Voir 40 message(s) de cette discussion en une page