Tic Tac Toe «Sans Frontières»

Tic-tac-toe ... tout le monde les a joués, j'en suis sûr. Le jeu est séduisant par sa simplicité, surtout lorsque vous faites glisser l'horloge quelque part dans la leçon, un couple, et il n'y a rien à portée de main, sauf une feuille de cahier et un simple crayon. Je ne sais pas qui a été le premier à avoir pensé à dessiner des croix et des cercles sur 9 cases, mais depuis lors, le jeu n'a plus perdu en demande, d'autant plus que les gens ont proposé de nombreuses variantes.



Cet article concerne le processus de développement de l'IA sur javascript pour jouer à l'une de ces variations de tic-tac-toe: j'ai beaucoup de matériel, mais je l'ai dilué avec de l'animation et des images. Dans tous les cas, au moins ça vaut le coup d'essayer de le jouer.
Les différences entre cette version du jeu et l'original sont les suivantes:

1. Le champ peut être arbitrairement grand (combien de temps durera le bloc-notes)
2. Le gagnant est celui qui met 5 pièces (si vous pouvez les appeler ainsi) dans une rangée.

Tout est simple ... et en même temps compliqué: le résultat du jeu ne peut pas être calculé à l'avance, comme dans l'analogue classique. Cette "petite projection" m'a enlevé beaucoup de temps et de nerfs. J'espère que vous le trouverez intéressant.

Avant de commencer

Forcé de m'excuser à l'avance pour le volume de l'article et à certains endroits une présentation de pensée pas tout à fait intelligible, cependant, je n'ai pas pu serrer le troupeau sans perte de contenu et de qualité.
Je vous recommande de vous familiariser d'abord avec le résultat . Code

Raccourcis clavier et commandes:

• D - AI fera un pas pour vous
• T - voir le poids des cellules
• Écrivez SHOW_WEIGHTS = true dans la console pour afficher les poids de toutes les cellules analysées.

Commençons

Vous devez commencer par la mise en œuvre du jeu lui-même, c'est-à-dire écrire une application pour deux joueurs, jusqu'ici sans bot. Pour mes besoins, j'ai décidé d'utiliser javascript + jquery + bootstrap4, bien qu'il n'y soit pratiquement pas utilisé, mais il vaut mieux le laisser - sinon la table flottera. Il n'y a rien de spécial à dire, il y a beaucoup de matériel sur js, jquery et bootstrap. Je peux seulement dire que j'ai utilisé MVC. Quoi qu'il en soit, je n'expliquerai pas absolument tout le code - il y a déjà eu beaucoup de matériel.

Le terrain de jeu était donc prêt. Vous pouvez définir des formes dans les cellules. Mais la victoire de l'un des joueurs n'a été fixée en aucune façon.

Analyse de fin de partie

Le jeu se termine lorsque l'un des joueurs met 5 pièces d'affilée. "C'est simple!" Pensai-je. Et il a commencé à balayer absolument toutes les cellules du champ: tout d'abord l'horizontale, puis la verticale, et enfin les diagonales.

C'est une façon stupide, mais cela a fonctionné. Cependant, cela pourrait être considérablement amélioré, ce que j'ai fait: la plupart des cellules resteront vides tout au long du jeu - le terrain de jeu est trop grand pour être entièrement rempli. Puisqu'il était nécessaire de le scanner à chaque mouvement, et qu'une seule pièce est placée en un seul mouvement - vous pouvez vous concentrer uniquement sur cette pièce (cellule): scannez seulement une horizontale, verticale et deux diagonales de la cellule qui possède la même cellule.

De plus, vous n'avez pas besoin de scanner toutes les lignées cellulaires. Puisque la fin du jeu est de 5 pièces d'affilée, les pièces qui sont à 6 cases les unes des autres ne nous intéressent pas. Il suffit de scanner cinq cellules de chaque côté. Je ne comprends pas? Voir l'animation ci-dessous.

Descendons au bot lui-même

Donc, nous avons déjà écrit une page avec tic-tac-toe. Nous passons à la tâche principale - l'IA.
Vous ne pouvez pas simplement prendre et écrire du code si vous ne savez pas comment: vous devez réfléchir à la logique du bot.

L'essentiel est d'analyser le terrain de jeu, au moins une partie de celui-ci, et de calculer le prix (poids) de chaque cellule sur le terrain. La cellule avec le poids le plus élevé - la plus prometteuse - le bot y mettra un chiffre. La principale difficulté est de calculer le poids d'une cellule.

Terminologie

Les croix et les orteils sont des figures.
Une attaque sera appelée plusieurs personnages identiques côte à côte sur la même ligne. En fait, c'est beaucoup. Le nombre de pièces dans une attaque est sa puissance . Une pièce distincte est également une attaque (puissance 1).

Sur les cellules d'attaque adjacentes (aux extrémités), il peut y avoir des cellules vides ou des pièces ennemies. Il est logique de penser qu'une attaque avec deux cellules vides aux «extrémités» peut se développer dans deux directions, ce qui la rend plus prometteuse. Le nombre de cellules vides aux "extrémités" de l'attaque sera appelé son potentiel . Le potentiel peut être 0, 1 ou 2.
Nous désignons les attaques comme suit: [puissance d'attaque, potentiel] . Par exemple, une attaque [4: 1] .


Figure 1. Attaque [4: 1]

Au cours de l'analyse, nous évaluerons toutes les cellules qui entrent dans une zone spécifique. Chaque cellule calculera son poids . Il est calculé sur la base du poids de toutes les attaques que cette cellule affecte.

L'essence de l'analyse

Imaginez que sur le terrain de jeu, il y a déjà plusieurs attaques d'un et du deuxième joueur. Un des joueurs fait un mouvement (laissez les croix). Naturellement, il se déplace vers une cellule vide - et ainsi il peut:

1. Développez votre attaque, et peut-être plus d'une, en augmentant sa puissance. Peut lancer une nouvelle attaque, etc.
2. Empêchez le développement d'une attaque ennemie ou bloquez-la complètement.

Autrement dit, notre protagoniste peut attaquer et défendre. Ou peut-être d'un coup. Pour lui, le premier et le second sont importants.

L'essence de l'analyse est la suivante:

1. Le bot substitue les chiffres de la cellule cochée: d'abord une croix, puis un zéro.
2. Il recherche ensuite toutes les attaques reçues par de tels mouvements et résume leurs poids.
3. Le montant reçu est le poids de la cellule.
4. Un algorithme similaire est exécuté pour toutes les cellules du terrain de jeu.

En fait, nous vérifions avec un tel algorithme ce qui se passera si nous allons de cette façon ... et ce qui se passera si l'adversaire va de cette façon. Nous attendons avec impatience une étape et sélectionnons la cellule la plus appropriée - avec le poids le plus élevé.

Si une cellule a plus de poids qu'une autre, elle conduit à la création d'attaques plus dangereuses ou à bloquer de fortes attaques ennemies. Tout est logique ... il me semble.
Si vous allez sur la page et écrivez dans la console SHOW_WEIGHTS = true, vous pouvez sentir visuellement le fonctionnement de l'algorithme (les poids des cellules seront affichés).

Poids d'attaque

Je suis allé sur mon cerveau et apporté une telle correspondance d'attaques et de poids:

 ATTACK_WEIGHT = [[],[],[],[],[],[]]; ATTACK_WEIGHT[1][1] = 0.1; ATTACK_WEIGHT[2][1] = 2; ATTACK_WEIGHT[3][1] = 4; ATTACK_WEIGHT[4][1] = 6; ATTACK_WEIGHT[5][1] = 200; ATTACK_WEIGHT[1][2] = 0.25; ATTACK_WEIGHT[2][2] = 5; ATTACK_WEIGHT[3][2] = 7; ATTACK_WEIGHT[4][2] = 100; ATTACK_WEIGHT[5][2] = 200; ATTACK_WEIGHT[5][0] = 200; 

Empiriquement sélectionné - ce n'est peut-être pas la meilleure option.

J'ai ajouté une puissance d'attaque de 5 avec un poids prohibitif à la matrice. Cela peut s'expliquer par le fait que le bot analyse le jeu en regardant un pas en avant (en remplaçant la figure dans la cellule). Sauter une telle attaque n'est rien d'autre qu'une défaite. Eh bien, ou la victoire ... selon qui.

Les attaques à fort potentiel sont valorisées plus haut.

L'attaque [4: 2] dans la plupart des cas décide du résultat de la partie. Si le joueur a réussi à créer une telle attaque, l'adversaire ne pourra plus la bloquer. Mais ce n'est pas une victoire. L'ennemi peut terminer le jeu plus rapidement, même si nous avons une attaque [4: 2] sur le terrain, donc son poids est inférieur à celui des attaques d'une puissance de 5. Voir un exemple ci-dessous.


Figure 2. Attaque [4: 2]

Attaques déchirées

Le code n'est pas présenté dans ce paragraphe. Ici, nous introduisons le concept d'un diviseur d'attaque et expliquons l'essence des «attaques déchirées» .

Considérez la situation suivante: lorsque vous remplacez un chiffre pour supprimer plusieurs cellules vides, mais pas plus de 5, une autre est localisée.

Et, semble-t-il, deux figures identiques, sur la même ligne ... visuellement cela ressemble à une attaque, mais en fait non. Pas un ordre, car de telles attaques "déchirées" comportent également une menace potentielle.

Surtout pour de tels cas, pour chaque attaque, nous calculerons le diviseur. Initialement, sa valeur est 1.

1. Nous présentons l'attaque "déchirée" comme plusieurs
2. On compte le nombre de cellules vides entre l'attaque centrale et le côté
3. Pour chaque cellule vide, le diviseur est augmenté de 1
4. Nous calculons le poids de l'attaque centrale comme d'habitude, le poids des attaques latérales - divisé par le diviseur

Fig 3. Analyse de "Attaque déchirée". Une cellule avec une croix jaune est scannée.

Ainsi, les attaques déchirées seront également prises en compte par l'IA. En fait, ce seront des attaques ordinaires, mais plus elles sont éloignées de la cellule scannée, moins elles ont d'influence sur elle et, par conséquent, elles ont moins de poids (grâce au diviseur).

Algorithme de recherche d'attaque

Créez d'abord une classe d' attaque. L'attaque aura 3 attributs, dont j'ai parlé plus tôt:

 class Attack{ constructor( cap = 0, pot = 0, div = 1 ){ this.capability = cap; // this.potential = pot; // this.divider = div; // } 

Et une méthode qui renverra le poids d'une attaque donnée:

 countWeigth(){ return ATTACK_WEIGHT[ this.capability, this.potential ] / this.divider } } 

Ensuite. Nous diviserons la recherche de toutes les attaques pour une cellule en:

1. Recherche horizontale
2. Recherche verticale
3. Recherche diagonale à 45 degrés
4. Recherche en diagonale à 135 degrés

Ce sont toutes des lignes , et l'algorithme de recherche d'attaques sur ces lignes peut être généralisé: la classe checkLine .

Cependant, nous n'avons pas besoin de vérifier toute la ligne. La puissance d'attaque maximale qui nous intéresse est de 5. Bien sûr, il est possible de créer une attaque avec une puissance de, disons, 6. Mais pour une IA qui analyse la situation de jeu du prochain coup, c'est la même chose que 6 ou 5. La perspective d'obtenir l'une de ces attaques indique la fin du jeu au coup suivant. En conséquence, le poids de la cellule analysée sera le même dans les deux cas.

Attributs de classe:

 class checkLine{ constructor(){ //,        this.subFig = "×"; //     .    «0» - . this.Attacks = []; //  this.curAttack = new Attack; // (      ) this.iter = 1; //,     this.checkEdge = false; 

Il faut s'arrêter là, car la question peut se poser: pourquoi vérifier la 6e cellule si la puissance d'attaque maximale est 5. La réponse est de déterminer le potentiel éloigné du centre d'attaque.

Voici un exemple: une attaque avec une puissance de 1 dans l'image se situe à la frontière de la zone scannée. Pour découvrir le potentiel de cette attaque, vous devez «regarder à l'étranger».


Fig. 3. Numérisation des 6e cellules. Si vous ne scannez pas la 6e cellule, vous pouvez déterminer incorrectement le potentiel d'attaque.

  //   this.attackplace = 1; } 

Il n'y a peut-être tout simplement pas assez d'espace pour terminer certaines attaques. Après avoir compté le lieu de l'attaque, nous pouvons comprendre à l'avance laquelle des attaques n'est pas prometteuse.


Fig. 4. Lieu d'attaque

L'algorithme est le suivant:

1) Commençons par la cellule centrale. Elle doit être vide (nous allons y faire un pas, non? Mais nous n'oublions pas que notre IA doit substituer les chiffres de cette cellule pour l'analyse du prochain coup. Le chiffre que nous substituons est this.subfig - la valeur par défaut est une croix). Étant donné que la cellule centrale contiendra initialement une certaine forme après substitution, elle appartiendra à une attaque this.curAttack :

• sa puissance ne sera pas inférieure à 1 (un chiffre dans la cellule centrale)
• diviseur - 1, car c'est une attaque centrale (elle appartient à la cellule scannée);
• le potentiel n'est pas encore connu - la valeur par défaut est 0;

Nous avons affiché tous ces points dans les valeurs par défaut du constructeur - voir le code ci-dessus.

2) Ensuite, en réduisant l'itérateur, itère plus de 5 cellules d'un côté de celle numérisée. La fonction getAttacks (cellX, cellY, subFig, dx, dy) en est responsable, où:

cellX, cellY - coordonnées de la cellule cochée
subFig - le chiffre que nous substituons dans la cellule cochée
dx, dy - changements dans les coordonnées x et y dans les cycles - c'est ainsi que nous définissons la direction de recherche:

• Horizontale (dx = 1, dy = 0)
• Verticale (dx = 0, dy = 1)
• Diagonale 45 (dx = 1, dy = -1)
• Diagonale 135 (dx = 1, dy = 1)

Dans un sens, il s'agit d'un vecteur parallèle à la ligne de recherche. Ainsi, une fonction pourra rechercher dans 4 directions et nous ne violerons pas le principe DRY à nouveau.

Code de fonction:

 getAttacks( cellX, cellY, subFig, dx, dy ){ this.substitudeFigure( subFig ); //  –  ... for( var x = cellX - dx, y = cellY - dy; Math.abs( x - cellX ) <= 5 && Math.abs( y - cellY ) <= 5; x -= dx, y -= dy ) if( this.checkCell( x, y ) ) break; //: //    (  ) this.turnAround(); //  -    ... for( var x = cellX + dx, y = cellY + dy; Math.abs( x - cellX ) <= 5 && Math.abs( y - cellY ) <= 5; x += dx, y += dy ) if( this.checkCell( x, y ) ) break; return this.Attacks; } 

Veuillez noter que si checkCell () renvoie quelque chose, la boucle s'arrête.

3) Nous vérifions les chiffres de ces cellules.
La fonction checkCell (x, y) en est responsable:

Tout d'abord, écrivez la forme dans la variable fig :
Model.Field est notre terrain de jeu.

 checkCell( x, y ){ var fig = Model.Field[x] && Model.Field[x][y] !== undefined ? Model.Field[x][y] : 'b'; 

fig peut être 'x', 'o', 'b' (bordure), 0 (cellule vide).

• Si une telle figure coïncide avec la figure de la cellule centrale ( this.subFig ), alors nous continuons l'algorithme - alors nous continuons à scanner l'attaque, tout va bien, nous continuons dans le même esprit. Une pièce supplémentaire dans l'attaque est un plus pour sa puissance ( this.curAttack.capability ) et sa place ( this.attackplace ).
  
  (Voir le code dans le paragraphe suivant)
• S'il s'agit d'un chiffre différent, l'attaque que nous avons analysée auparavant (this.curAttack) est bloquée de ce côté. Nous ne changeons rien dans les paramètres d'attaque, l'écrivons dans le tableau d'attaques et sortons de la boucle.
  
  

   if( fig == '○' || fig == '×' ){ if( this.subFig != fig ){ //  this.Attacks.push( this.curAttack ); //  return fig; //      } else{ //    this.curAttack.capability++; // +   this.attackplace++; // +   } } 

  
  
• S'il n'y a pas de telles cellules, cela signifie qu'elles sont tombées hors de la limite du champ, ce qui signifie que l'attaque est bloquée. Nous l'écrivons dans un tableau de toutes les attaques et sortons de la boucle.
  
  

   else if( fig == 'b' ){ // this.Attacks.push( this.curAttack ); return 'b'; } 

  
  
• Si vous attrapez une cage vide, cela signifie que l'attaque en cours est terminée ou que nous avons affaire à une "attaque déchirée". Plus le potentiel et le lieu d'attaque (car l'attaque n'est pas bloquée). Cependant, nous ne sortons pas de la boucle - c'est peut-être une "attaque déchirée" - nous écrivons simplement this.curAttack dans le tableau de toutes les attaques de la ligne this.Attacks []. Créez une nouvelle attaque «actuelle» et augmentez son diviseur de 1 (il s'agit d'une attaque latérale).
  
  

   else{ //  if( this.curAttack.capability ){ this.curAttack.potential++; this.Attacks.push( this.curAttack ); this.curAttack = new Attack; this.curAttack.potential++; } this.curAttack.divider++; this.attackplace++; } 

  
  

4) Si sur la 5ème cellule le chiffre coïncide avec la cellule centrale, alors l'attaque "reposait" contre la frontière et pour déterminer le potentiel d'attaque, vous devrez "vérifier la frontière" ( this.checkEdge = true ).

 if( this.iter == 4 && fig == this.subFig ) // 5-  this.checkEdge = true; else if( this.iter == 5 ){ if( this.checkEdge ){ if( fig == this.curFig || fig == 0 ) this.curAttack.potential++; this.Attacks.push( this.curAttack ) } return 0; } this.iter++ 

La fonction checkCell est prête. Cependant, nous continuons à travailler sur la classe checkLine .

5) Après avoir terminé le premier cycle, vous devez "faire demi-tour". Nous traduisons l'itérateur au centre et l'attaque centrale, avec l'index 0, le supprimons du tableau d'attaques et le définissons comme l'actuel.

 turnAround(){ this.iter = 1; this.checkEdge = false; this.curAttack = this.Attacks[0]; this.Attacks.splice(0,1) } 

6) Ensuite, allez de l'autre côté de la cellule actuelle, augmentant l'itérateur.
Absolument le même contrôle des chiffres. (Code déjà écrit - fonction getAttacks )

7) Tout, nous avons rassemblé toutes les attaques qui étaient sur la ligne dans un même tableau.
C'est tout avec la classe checkLine ... tout est fait.

Eh bien, alors tout est simple - créez un objet checkLine pour chacune des lignes (2 diagonales, horizontale et verticale) et appelez la fonction getAttacks . Autrement dit, pour chaque ligne - son propre objet checkLine et, par conséquent, son propre ensemble d'attaques.

Que la fonction getAllAttacks () soit responsable de tout cela - déjà séparément des classes décrites ci-dessus;

 getAllAttacks( cellX, cellY ){ // ,  , //       if( Model.Field[ cellX ][ cellY ] ) return false var cX = []; var cO = []; //   ... cX['0'] = this.getAttacksLine( cellX, cellY, '×', 1, 0 ); cX['90'] = this.getAttacksLine( cellX, cellY, '×', 0, 1 ); cX['45'] = this.getAttacksLine( cellX, cellY, '×', 1, -1 ); cX['135'] = this.getAttacksLine( cellX, cellY, '×', 1, 1 ); //  ... cO['0'] = this.getAttacksLine( cellX, cellY, '○', 1, 0 ); cO['90'] = this.getAttacksLine( cellX, cellY, '○', 0, 1 ); cO['45'] = this.getAttacksLine( cellX, cellY, '○', 1, -1 ); cO['135'] = this.getAttacksLine( cellX, cellY, '○', 1, 1 ); return { //     'x': cX, 'o': cO } } getAttacksLine( cellX, cellY, subFig, dx, dy ){ //      var C = new checkLine; C.getAttacks( cellX, cellY, subFig, dx, dy ); return this.filterAttacks( C ) //   } 

En sortie, nous avons un objet avec toutes les attaques pour la cellule testée

Cependant, vous avez peut-être remarqué une sorte de fonction de filtre. Sa tâche est de filtrer les attaques «futiles»:

• Avec une puissance nulle (on ne sait jamais s'ils entrent dans le réseau)
• Attaques qui manquent d'espace (lieu d'attaque <5)
• Avec un potentiel nul.

Cependant, si l'attaque a une puissance supérieure à 5, le filtre la sautera. Le bot doit voir de telles attaques, leur dépistage entraînera des jambages en fin de partie.

 filterAttacks( attackLine ){ var res = [] if( attackLine.attackplace >= 5 ) attackLine.Attacks.forEach( ( a )=>{ if( a.capability && a.potential || a.capability >= 5 ) res.push( a ) }) attackLine.Attacks = res; return res } 

Points d'arrêt

Oui ... encore une fois, désolé! Nous appellerons donc la situation dans le jeu, lorsqu'un mauvais coup décide du résultat du jeu.

Par exemple, une attaque [3: 2] est un point d'arrêt. Si l'adversaire ne le bloque pas en plaçant une pièce à côté de lui, alors au prochain coup, nous avons déjà une attaque [4: 2] sur le terrain de jeu - eh bien, le résultat du jeu est décidé, quoi qu'on puisse dire (dans la grande majorité des cas).

Ou une attaque [4: 1]. Un bâillement - et le jeu peut être facilement terminé.


Figure 5. Point d'arrêt

Tout est clair et compréhensible, et l'algorithme décrit ci-dessus est déjà capable de prendre en compte les points d'arrêt et de les bloquer en temps opportun. Le bot attend avec impatience. Il verra qu'au prochain tour, l'adversaire est capable de créer une attaque [5: 1], par exemple, dont le poids est de 200 - ce qui signifie que le ringard rusé ira ici.

Cependant, imaginez une situation où l'un des joueurs parvient à obtenir 2 points d'arrêt sur le terrain. Et cela, évidemment, ne laisse aucune chance à l'adversaire, car d'un seul coup, nous ne pouvons bloquer qu'un seul point d'arrêt. Comment apprendre à notre IA à bloquer de telles attaques?


Figure 6. 2 points d'arrêt

Tout est simple, lors de l'analyse d'une cellule, en y substituant une pièce, nous compterons le nombre de points d'arrêt que nous obtiendrons au prochain coup (le bot regarde le pas en avant, n'oubliez pas). En comptant 2 points d'arrêt, nous augmentons le poids des cellules de 100.

Et maintenant, le bot empêchera non seulement de telles situations de jeu, mais pourra également les créer, ce qui en fait maintenant un adversaire plus redoutable.

Comment comprendre qu'une attaque est un point d'arrêt

Commençons par l'évidence: toute attaque d'une puissance de 4 est un point d'arrêt. Un seul coup manqué nous donne la possibilité de terminer le jeu, c'est-à-dire mettre 5 morceaux d'affilée.

De plus, si le potentiel d'attaque est de 2, alors nous dépenserons 1 tour de plus pour bloquer une telle attaque, ce qui signifie qu'il y a un point d'arrêt d'une puissance de 3. Mais il n'y a qu'un seul point d'arrêt - c'est une attaque [3: 2].

Et encore plus difficile - "attaques déchirées" .
Nous ne considérerons que les attaques avec une cellule vide au milieu - pas plus. En effet, pour terminer l'attaque avec deux cellules vides au milieu, vous devez dépenser au moins 2 mouvements - ce n'est clairement pas un point d'arrêt.

Comme nous nous en souvenons, nous considérons les attaques déchirées comme plusieurs attaques classiques: une attaque centrale et des attaques latérales. L'attaque centrale appartient à la cellule scannée, le diviseur latéral en a plus de 1 - cela a été décrit ci-dessus.

Algorithme pour trouver un point d'arrêt (plus facile, lire ci-dessous):

1. Nous introduisons le score variable
2. On prend l'attaque centrale, on considère le pouvoir
3. Nous prenons l'un des côtés si son diviseur n'est pas plus de 2x.
4. Score - la somme de la puissance des attaques centrales et latérales
5. Si les potentiels des attaques centrales et latérales sont de 2, alors pour bloquer une telle attaque, vous devez passer un tour de plus. Par conséquent, le score est augmenté de 1
6. Si score > = 4, alors c'est un point d'arrêt
   En fait, les points d'arrêt pouvaient simplement être énumérés, il n'y en a pas beaucoup, mais je n'ai pas tout de suite compris cela.

 isBreakPoint( attackLine ){ if( ! attackLine || ! attackLine.length ) return false; var centAtk; attackLine.forEach( ( a )=>{ if( a.divider == 1 ) centAtk = a; }) if( centAtk.capability >= 4 ) return true if( centAtk.potential == 2 && centAtk.capability >= 3 ) return true; var res = false; attackLine.forEach( ( a )=>{ var score = centAtk.capability; if( a.divider == 2 ){ //side attack if( centAtk.potential == 2 && a.potential == 2 ) score++; if( score + a.capability >= 4 ){ res = true; return; } } }) return res; } 

Oui, nous allons enfin tout rassembler

Ainsi, l'enfer principal derrière est décrit ci-dessus. Il est temps de façonner quelque chose qui fonctionne à partir de cela. Fonction countWeight (x, y) - prend les coordonnées de la cellule en entrée et renvoie son poids. Qu'y a-t-il sous sa capuche?

Tout d'abord, nous obtenons un tableau de toutes les attaques auxquelles appartient la cellule. ( getAllAttacks (x, y) ). En parcourant toutes les lignes, nous comptons le nombre de points d'arrêt. S'il y a 2 points d'arrêt, nous rappelons qu'une telle situation peut décider du résultat du jeu et augmenter le poids des cellules de 100.
Cependant, tous les points d'arrêt doivent appartenir à un seul joueur, j'ai donc dû implémenter une vérification en 2 étapes: d'abord les croix, puis les zéros.

Étant donné que dans la gamme de poids d'attaque ( ATTACK_WEIGHTS [] ), je n'ai pas fourni d'attaques d'une puissance de 6 ou plus, j'ai dû les remplacer par des attaques d'une puissance de 5. Cela ne fait aucune différence - ils mènent tous à la fin du jeu.

Eh bien, nous résumons les poids d'attaque - c'est tout.

Autre petit point: pour que le bot ne soit pas stupide en fin de partie, quand il a déjà construit une attaque avec une puissance de 4 et pense au coup en cours, il faut augmenter significativement le poids de la cellule pour terminer une telle attaque. Sans cela, l'IA peut tout simplement commencer à se défendre contre les attaques «dangereuses» de l'adversaire, bien que le jeu semble gagné. Le dernier mouvement est important.

 countWeight( x, y ){ var attacks = this.getAttacks( x, y ) if( ! attacks ) return; var sum = 0; sum += count.call( this, attacks.x, '×' ); sum += count.call( this, attacks.o, '○' ); return sum function count( atks, curFig ){ var weight = 0; var breakPoints = 0; [ "0", "45", "90", "135" ].forEach( ( p )=>{ if( this.isBreakPoint( atks[p] ) ){ debug( "Break point" ) if( ++breakPoints == 2 ){ weight += 100; debug( "Good cell" ) return; } } atks[p].forEach( ( a )=>{ if( a.capability > 5 ) a.capability = 5; if( a.capability == 5 && curFig == Model.whoPlays.char ) weight += 100; weight += a.getWeight(); }); }) return weight } } 

Maintenant, lors de l'appel de cette fonction pour une cellule spécifique, nous obtiendrons son poids. Nous effectuons cette opération pour toutes les cellules et sélectionnons la meilleure (avec le poids le plus élevé). Là et allez)

Vous pouvez trouver le reste du code sur github . Il y a déjà beaucoup de matériel, et sa présentation, comme je n'ai pas essayé, laisse beaucoup à désirer. Mais si vous pouviez lire jusqu'ici, cher lecteur, je vous en serais reconnaissant.

Descends! Oui, vous pouvez le battre, mais le faire est un peu problématique pour moi personnellement. Peut-être que je ne fais pas assez attention. Essayez aussi votre force.

Je sais que c'est plus facile, mais je ne sais pas comment. Je voudrais écouter les gens qui connaissent ou regardent d'autres implémentations d'un tel bot.

Je sais ce qui peut être mieux. Oui ... vous pouvez utiliser des algorithmes bien connus, tels que minimax, mais pour cela, vous devez avoir une base de connaissances dans le domaine de la théorie des jeux, dont je ne peux malheureusement pas me vanter.

À l'avenir, je prévois d'ajouter une analyse des points d'arrêt à plusieurs étapes, ce qui fera du bot un adversaire encore plus sérieux. Cependant, maintenant je n'ai pas une idée claire de la mise en œuvre de cela; J'ai juste la prochaine session et un diplôme incomplet - ce qui m'attriste.

Merci si vous lisez jusqu'au bout.