Tic Tac Toe "Ohne Grenzen"

Tic-Tac-Toe ... alle haben sie gespielt, da bin ich mir sicher. Das Spiel ist in seiner Einfachheit attraktiv, besonders wenn Sie die Uhr irgendwo in der Lektion ziehen, ein Paar, und nichts zur Hand ist außer einem Notizbuchblatt und einem einfachen Bleistift. Ich weiß nicht, wer der erste war, der einmal vermutet hat, Kreuze und Kreise auf 9 Feldern zu zeichnen, aber seitdem hat das Spiel überhaupt nicht an Nachfrage verloren, zumal die Leute viele seiner Variationen erfunden haben.



In diesem Artikel geht es um den Prozess der Entwicklung von KI auf Javascript zum Spielen einer dieser Variationen von Tic-Tac-Toe: Ich habe viel Material, aber ich habe es mit Animationen und Bildern verdünnt. Auf jeden Fall ist es einen Versuch wert, es zu spielen.
Die Unterschiede zwischen dieser Version des Spiels und dem Original sind wie folgt:

1. Das Feld kann beliebig groß sein (wie lange hält das Notebook)
2. Der Gewinner ist derjenige, der 5 Teile (wenn man sie so nennen kann) hintereinander legt.

Alles ist einfach ... und gleichzeitig kompliziert: Das Ergebnis des Spiels kann nicht wie im klassischen Analogon im Voraus berechnet werden. Diese "kleine Projektion" hat mir viel Zeit und Nerven genommen. Hoffe du findest es interessant.

Bevor wir anfangen

Ich war gezwungen, mich im Voraus für den Umfang des Artikels und an einigen Stellen für die nicht ganz verständliche Darstellung des Denkens zu entschuldigen, konnte die Herde jedoch nicht ohne Verlust an Inhalt und Qualität quetschen.
Ich empfehle Ihnen, sich zuerst mit dem Ergebnis vertraut zu machen. Code

Hotkeys und Befehle:

• D - AI wird einen Schritt für Sie machen
• T - siehe Zellgewicht
• Schreiben Sie SHOW_WEIGHTS = true in die Konsole, um die Gewichte aller analysierten Zellen anzuzeigen.

Fangen wir an

Sie müssen mit der Implementierung des Spiels selbst beginnen, d. H. schreibe eine Bewerbung für zwei Spieler, bisher ohne Bot. Für meine Zwecke habe ich mich für Javascript + JQuery + Bootstrap4 entschieden, obwohl es dort praktisch nicht verwendet wird, aber es ist besser, es zu belassen - sonst schwebt die Tabelle. Es gibt nichts Besonderes zu erzählen, es gibt viel Material zu js, jquery und bootstrap. Ich kann nur sagen, dass ich MVC verwendet habe. Wie auch immer, ich werde nicht den gesamten Code erklären - es gab bereits viel Material.

Das Spielfeld war also fertig. Sie können Formen in Zellen festlegen. Aber der Sieg eines der Spieler war in keiner Weise festgelegt.

Spielende-Scan

Das Spiel endet, wenn einer der Spieler 5 Teile hintereinander legt. "Es ist einfach!" Dachte ich. Und er fing an, absolut alle Zellen des Feldes zu scannen: zuerst alle horizontalen, dann die vertikalen und schließlich die Diagonalen.

Das ist ein dummer Weg, aber es hat funktioniert. Es könnte jedoch erheblich verbessert werden, was ich auch getan habe: Die meisten Zellen bleiben während des Spiels leer - das Spielfeld ist zu groß, um vollständig gefüllt zu werden. Da es notwendig war, jede Bewegung zu scannen und nur ein Teil in einer Bewegung platziert wird, können Sie sich nur auf dieses Teil (Zelle) konzentrieren: Scannen Sie nur eine horizontale, vertikale und zwei Diagonalen der Zelle, die dieselbe Zelle besitzt.

Außerdem müssen Sie nicht alle Zelllinien scannen. Da das Ende des Spiels 5 Teile hintereinander ist, sind die Teile, die 6 Zellen voneinander entfernt sind, für uns nicht von Interesse. Es reicht aus, fünf Zellen auf jeder Seite zu scannen. Unverständlich? Siehe die Animation unten.

Kommen wir zum Bot selbst

Wir haben also bereits eine Seite mit Tic-Tac-Toe geschrieben. Wir gehen zur Hauptaufgabe über - KI.
Sie können nicht einfach Code nehmen und schreiben, wenn Sie nicht wissen wie: Sie müssen über die Logik des Bots nachdenken.

Die Quintessenz besteht darin, das Spielfeld, zumindest einen Teil davon, zu analysieren und den Preis (das Gewicht) jeder Zelle auf dem Spielfeld zu berechnen. Die Zelle mit dem höchsten Gewicht - das vielversprechendste - der Bot wird dort eine Zahl setzen. Die Hauptschwierigkeit besteht in der Berechnung des Gewichts einer Zelle.

Terminologie

Kreuze und Zehen sind Figuren.
Ein Angriff wird als mehrere identische Figuren bezeichnet, die nebeneinander auf derselben Linie stehen. In der Tat ist das viel. Die Anzahl der Teile eines Angriffs ist seine Stärke . Ein separates Stück ist auch ein Angriff (Kraft 1).

Auf benachbarten Angriffszellen (an den Enden) können sich leere Zellen oder feindliche Teile befinden. Es ist logisch zu denken, dass ein Angriff mit zwei leeren Zellen an den „Enden“ in zwei Richtungen entwickelt werden kann, was ihn vielversprechender macht. Die Anzahl der leeren Zellen an den "Enden" des Angriffs wird als Potenzial bezeichnet . Das Potential kann 0, 1 oder 2 sein.
Wir bezeichnen Angriffe wie folgt: [Angriffskraft, Potenzial] . Zum Beispiel ein Angriff [4: 1] .


Abbildung 1. Angriff [4: 1]

Im Verlauf der Analyse werden alle Zellen ausgewertet, die in einen bestimmten Bereich eintreten. Jede Zelle berechnet ihr Gewicht . Sie wird basierend auf den Gewichten aller Angriffe berechnet, die von dieser Zelle betroffen sind.

Das Wesentliche der Analyse

Stellen Sie sich vor, auf dem Spielfeld gibt es bereits mehrere Angriffe eines und des zweiten Spielers. Einer der Spieler macht einen Zug (lass die Kreuze). Natürlich zieht er in eine leere Zelle - und damit kann er:

1. Entwickle deinen Angriff und vielleicht mehr als einen, um seine Kraft zu erhöhen. Kann einen neuen Angriff starten usw.
2. Verhindern Sie die Entwicklung eines feindlichen Angriffs oder blockieren Sie ihn vollständig.

Das heißt, unser Protagonist kann angreifen und verteidigen. Oder vielleicht auf einmal. Für ihn sind sowohl der erste als auch der zweite wichtig.

Das Wesentliche der Analyse ist wie folgt:

1. Der Bot ersetzt die Zahlen in der markierten Zelle: zuerst ein Kreuz, dann eine Null.
2. Dann sucht er nach allen Angriffen, die durch solche Bewegungen erhalten wurden, und fasst ihre Gewichte zusammen.
3. Die erhaltene Menge ist das Gewicht der Zelle.
4. Ein ähnlicher Algorithmus wird für alle Zellen des Spielfelds durchgeführt.

Tatsächlich überprüfen wir mit einem solchen Algorithmus, was passieren wird, wenn wir diesen Weg gehen ... und was passieren wird, wenn der Gegner diesen Weg geht. Wir freuen uns auf einen Schritt und wählen die am besten geeignete Zelle aus - mit dem höchsten Gewicht.

Wenn eine Zelle mehr Gewicht als eine andere hat, führt dies zur Entstehung gefährlicherer Angriffe oder zur Blockierung starker feindlicher Angriffe. Alles ist logisch ... es scheint mir.
Wenn Sie zur Seite gehen und in die Konsole SHOW_WEIGHTS = true schreiben, können Sie die Funktionsweise des Algorithmus visuell spüren (Zellengewichte werden angezeigt).

Angriffsgewichte

Ich ging mein Gehirn durch und brachte eine solche Entsprechung von Angriffen und Gewichten:

 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; 

Empirisch ausgewählt - vielleicht ist dies nicht die beste Option.

Ich habe dem Array eine Angriffskraft von 5 mit unerschwinglich großem Gewicht hinzugefügt. Dies kann durch die Tatsache erklärt werden, dass der Bot das Spiel analysiert und einen Schritt nach vorne betrachtet (indem er die Figur in der Zelle ersetzt). Das Überspringen eines solchen Angriffs ist nichts anderes als eine Niederlage. Na ja, oder Sieg ... je nachdem wer.

Angriffe mit hohem Potenzial werden höher bewertet.

Angriff [4: 2] entscheidet in den meisten Fällen über das Ergebnis des Spiels. Wenn es dem Spieler gelungen ist, einen solchen Angriff zu erstellen, kann der Gegner ihn nicht mehr blockieren. Dies ist jedoch kein Sieg. Der Feind kann das Spiel schneller beenden, selbst wenn wir einen Angriff [4: 2] auf dem Spielfeld haben, sodass sein Gewicht geringer ist als das von Angriffen mit einer Stärke von 5. Siehe ein Beispiel unten.


Abbildung 2. Angriff [4: 2]

Zerrissene Angriffe

Der Code wird in diesem Absatz nicht dargestellt. Hier stellen wir das Konzept eines Angriffsteilers vor und erklären die Essenz von „zerrissenen Angriffen“ .

Stellen Sie sich folgende Situation vor: Wenn Sie eine Zahl ersetzen, um mehrere leere Zellen zu entfernen, jedoch nicht mehr als 5, befindet sich eine weitere.

Und es scheint, zwei identische Figuren auf derselben Linie ... visuell sieht es aus wie ein Angriff, aber tatsächlich nicht. Kein Befehl, da solche "zerrissenen" Angriffe auch eine potenzielle Bedrohung darstellen.

Insbesondere in solchen Fällen berechnen wir für jeden Angriff den Divisor. Anfangs ist sein Wert 1.

1. Wir präsentieren den "zerrissenen" Angriff als mehrere gewöhnliche
2. Wir zählen die Anzahl der leeren Zellen zwischen dem zentralen Angriff und der Seite
3. Für jede leere Zelle wird der Divisor um 1 erhöht
4. Wir berechnen wie gewohnt das Gewicht des Zentralangriffs, das Gewicht der Seitenangriffe - dividiert durch den Divisor

Abb. 3. Analyse des "Zerrissenen Angriffs". Eine Zelle mit einem gelben Kreuz wird gescannt.

Somit werden zerrissene Angriffe auch von der KI berücksichtigt. Tatsächlich handelt es sich um gewöhnliche Angriffe, aber je weiter sie von der gescannten Zelle entfernt sind, desto weniger Einfluss haben sie darauf und dementsprechend haben sie weniger Gewicht (dank des Teilers).

Angriffssuchalgorithmus

Erstellen Sie zunächst eine Angriffsklasse. Der Angriff wird 3 Attribute haben, über die ich zuvor geschrieben habe:

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

Und eine Methode , die das Gewicht eines bestimmten Angriffs zurückgibt:

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

Weiter. Wir werden die Suche nach allen Angriffen für eine Zelle in folgende Bereiche unterteilen:

1. Horizontale Suche
2. Vertikale Suche
3. 45-Grad-Diagonalsuche
4. 135-Grad-Diagonalsuche

All dies sind Linien , und der Algorithmus für die Suche nach Angriffen auf diese Linien kann verallgemeinert werden: die checkLine-Klasse .

Wir müssen jedoch nicht die gesamte Zeile überprüfen. Die maximale Angriffskraft, die uns interessiert, ist 5. Natürlich ist es möglich, einen Angriff mit einer Kraft von beispielsweise 6 zu erstellen. Für eine KI, die die Spielsituation des nächsten Zuges analysiert, entspricht dies 6 oder 5. Die Aussicht auf einen dieser Angriffe zeigt das Ende des Spiels im nächsten Zug an. Dementsprechend ist das Gewicht der analysierten Zelle in beiden Fällen gleich.

Klassenattribute:

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

Hier muss angehalten werden, da sich die Frage stellen kann: Warum die 6. Zelle überprüfen, wenn die maximale Angriffskraft 5 beträgt? Die Antwort besteht darin, das Potenzial zu ermitteln, das vom Angriffszentrum entfernt ist.

Hier ein Beispiel: Ein Angriff mit einer Potenz von 1 im Bild befindet sich am Rand des gescannten Bereichs. Um das Potenzial dieses Angriffs herauszufinden, müssen Sie "ins Ausland schauen".


Abb. 3. 6. Zellen scannen. Wenn Sie die 6. Zelle nicht scannen, können Sie das Angriffspotential falsch bestimmen.

  //   this.attackplace = 1; } 

Möglicherweise ist einfach nicht genügend Platz vorhanden, um einige Angriffe abzuschließen. Nachdem wir den Angriffsort gezählt haben, können wir im Voraus verstehen, welcher der Angriffe nicht vielversprechend ist.


Abb. 4. Ort zum Angriff

Der Algorithmus ist wie folgt:

1) Beginnen wir mit der zentralen Zelle. Es sollte leer sein (wir werden einen Zug hinein machen, richtig? Aber wir vergessen nicht, dass unsere KI Zahlen in dieser Zelle für die Analyse des nächsten Zuges ersetzen muss. Die Zahl, die wir ersetzen, ist this.subfig - der Standardwert ist ein Kreuz. Da die zentrale Zelle nach dem Ersetzen zunächst eine bestimmte Form enthält, gehört sie zu einem Angriff this.curAttack :

• seine Leistung wird nicht weniger als 1 sein (eine Zahl in der zentralen Zelle)
• Teiler - 1, weil es ist ein zentraler Angriff (es gehört zur gescannten Zelle);
• Potenzial ist noch nicht bekannt - Standard ist 0;

Wir haben alle diese Punkte in den Standardkonstruktorwerten angezeigt - siehe den obigen Code.

2) Als nächstes iteriert das Reduzieren des Iterators über 5 Zellen auf einer Seite des gescannten. Die Funktion getAttacks (cellX, cellY, subFig, dx, dy) ist dafür verantwortlich, wobei:

cellX, cellY - Koordinaten der überprüften Zelle
subFig - die Zahl, die wir in der markierten Zelle ersetzen
dx, dy - Änderungen der x- und y-Koordinaten in Zyklen - so stellen wir die Suchrichtung ein:

• Horizontal (dx = 1, dy = 0)
• Vertikal (dx = 0, dy = 1)
• Diagonale 45 (dx = 1, dy = -1)
• Diagonale 135 (dx = 1, dy = 1)

In gewissem Sinne ist dies ein Vektor parallel zur Suchlinie. Somit kann eine Funktion in 4 Richtungen suchen und wir werden das DRY-Prinzip nicht noch einmal verletzen.

Funktionscode:

 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; } 

Bitte beachten Sie, dass die Schleife stoppt, wenn checkCell () etwas zurückgibt.

3) Wir überprüfen die Zahlen dieser Zellen.
Die Funktion checkCell (x, y) ist dafür verantwortlich:

Schreiben Sie zuerst die Form in die Feigenvariable :
Model.Field ist unser Spielfeld.

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

fig kann 'x', 'o', 'b' (Rand), 0 (leere Zelle) sein.

• Wenn eine solche Zahl mit der Figur der zentralen Zelle ( thisFig ) übereinstimmt , setzen wir den Algorithmus fort - das heißt, wir scannen den Angriff weiter, alles ist in Ordnung, wir fahren im gleichen Sinne fort. Ein zusätzliches Teil des Angriffs ist ein Plus für seine Kraft ( this.curAttack.capability ) und seinen Platz ( this.attackplace ).
  
  (Siehe Code im nächsten Absatz)
• Wenn dies eine andere Zahl ist, wird der zuvor gescannte Angriff (this.curAttack) von dieser Seite blockiert. Wir ändern nichts an den Angriffsparametern, schreiben es in das Array von Angriffen und fallen aus der Schleife heraus.
  
  

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

  
  
• Wenn es keine solche Zelle gibt, bedeutet dies, dass sie aus der Feldgrenze herausgefallen sind, was bedeutet, dass der Angriff blockiert ist. Wir schreiben es in ein Array aller Angriffe und verlassen die Schleife.
  
  

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

  
  
• Wenn Sie einen leeren Käfig fangen, bedeutet dies, dass der aktuelle Angriff beendet ist oder es sich um einen "zerrissenen Angriff" handelt. Plus das Potenzial und den Ort zum Angriff (weil der Angriff nicht blockiert ist). Wir kommen jedoch nicht aus der Schleife heraus - vielleicht ist dies ein "zerrissener Angriff" - wir schreiben einfach this.curAttack in das Array aller Angriffe der Zeile this.Attacks []. Erstellen Sie einen neuen „aktuellen“ Angriff und erhöhen Sie seinen Teiler um 1 (dies ist ein Seitenangriff).
  
  

   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) Wenn in der 5. Zelle die Zahl mit der zentralen Zelle übereinstimmt, „ruhte“ der Angriff an der Grenze und um das Angriffspotential zu bestimmen, müssen Sie „die Grenze überprüfen“ ( 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++ 

Die checkCell- Funktion ist bereit. Wir arbeiten jedoch weiterhin an der checkLine- Klasse.

5) Nach Abschluss des ersten Zyklus müssen Sie sich "umdrehen". Wir übersetzen den Iterator in die Mitte und den zentralen Angriff mit dem Index 0, entfernen ihn aus dem Array der Angriffe und legen ihn als aktuellen fest.

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

6) Gehen Sie als nächstes zur anderen Seite der aktuellen Zelle und erhöhen Sie den Iterator.
Absolut die gleiche Überprüfung der Zahlen. (Code bereits geschrieben - Funktion getAttacks )

7) Alles, wir haben alle Angriffe, die auf der Linie waren, in einem Array gesammelt.
Das war's mit der checkLine- Klasse ... alles ist erledigt.

Nun, dann ist alles einfach - erstellen Sie ein checkLine- Objekt für jede der Linien (2 Diagonalen, horizontal und vertikal) und rufen Sie die Funktion getAttacks auf . Das heißt, für jede Zeile - ein eigenes checkLine- Objekt und dementsprechend eine eigene Reihe von Angriffen.

Lassen Sie die Funktion getAllAttacks () für all dies verantwortlich sein - bereits getrennt von den oben beschriebenen Klassen;

 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 ) //   } 

Am Ausgang haben wir ein Objekt mit allen Angriffen für die getestete Zelle

Möglicherweise haben Sie jedoch eine Filterfunktion bemerkt. Seine Aufgabe ist es, "vergebliche" Angriffe auszusortieren:

• Mit null Leistung (Sie wissen nie, ob sie in das Array gelangen)
• Angriffe ohne Platz (Angriffsort <5)
• Mit Nullpotential.

Wenn der Angriff jedoch eine Stärke von mehr als 5 hat, überspringt der Filter diese. Der Bot muss solche Angriffe sehen, ihre Überprüfung führt am Ende des Spiels zu Pfosten.

 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 } 

Haltepunkte

Ja ... nochmal, sorry! Wir werden also die Situation im Spiel nennen, wenn ein falscher Zug über das Ergebnis des Spiels entscheidet.

Zum Beispiel ist ein Angriff [3: 2] ein Haltepunkt. Wenn der Gegner es nicht blockiert, indem er eine Figur daneben legt, haben wir im nächsten Zug bereits einen Angriff [4: 2] auf das Spielfeld - nun, das Ergebnis des Spiels wird entschieden, was auch immer man sagen mag (in den allermeisten Fällen).

Oder ein Angriff [4: 1]. Ein Gähnen - und das Spiel kann leicht abgeschlossen werden.


Abbildung 5. Haltepunkt

Alles ist klar und verständlich, und der oben beschriebene Algorithmus kann bereits Haltepunkte berücksichtigen und rechtzeitig blockieren. Der Bot freut sich. Er wird sehen, dass der Gegner in der nächsten Runde zum Beispiel einen Angriff [5: 1] ausführen kann, dessen Gewicht 200 beträgt - was bedeutet, dass der listige Nerdy hierher geht.

Stellen Sie sich jedoch eine Situation vor, in der einer der Spieler 2 Haltepunkte auf dem Spielfeld erreicht. Und das lässt dem Gegner natürlich keine Chance, denn In einem Zug können wir nur einen Haltepunkt blockieren. Wie kann man unserer KI beibringen, solche Angriffe abzuwehren?


Abbildung 6. 2 Haltepunkte

Alles ist einfach, wenn wir eine Zelle analysieren, wenn wir ein Teil darin ersetzen, zählen wir die Anzahl der Haltepunkte, die wir beim nächsten Zug erhalten (der Bot schaut auf den Vorwärtsschritt, nicht vergessen). Durch Zählen von 2 Haltepunkten erhöhen wir das Zellgewicht um 100.

Und jetzt wird der Bot solche Spielsituationen nicht nur verhindern, sondern auch erstellen können, was ihn jetzt zu einem gewaltigeren Gegner macht.

Wie man versteht, dass ein Angriff ein Haltepunkt ist

Beginnen wir mit dem Offensichtlichen: Jeder Angriff mit einer Potenz von 4 ist ein Haltepunkt. Nur ein verpasster Zug gibt uns die Möglichkeit, das Spiel zu beenden, d. H. 5 Stücke hintereinander legen.

Wenn das Angriffspotential 2 beträgt, werden wir 1 Runde mehr ausgeben, um einen solchen Angriff zu blockieren, was bedeutet, dass es einen Haltepunkt mit einer Potenz von 3 gibt. Es gibt jedoch nur einen solchen Haltepunkt - dies ist ein Angriff [3: 2].

Und noch schwieriger - "zerrissene Angriffe" .
Wir werden nur Angriffe mit einer leeren Zelle in der Mitte betrachten - nicht mehr. Dies liegt daran, dass Sie mindestens zwei Züge ausführen müssen, um den Angriff mit zwei leeren Zellen in der Mitte abzuschließen - dies ist eindeutig kein Haltepunkt.

Wie wir uns erinnern, betrachten wir zerrissene Angriffe als mehrere konventionelle: einen Zentralangriff und Seitenangriffe. Der zentrale Angriff gehört zur gescannten Zelle, der Seitenteiler hat mehr als 1 - dies wurde oben beschrieben.

Algorithmus zum Finden eines Haltepunkts (einfacher, siehe unten):

1. Wir führen die variable Punktzahl ein
2. Wir nehmen den Zentralangriff, wir betrachten die Macht
3. Wir nehmen eine der Seiten, wenn der Teiler nicht mehr als 2x beträgt.
4. Punktzahl - die Summe der Stärke der Zentral- und Seitenangriffe
5. Wenn das Potenzial der Zentral- und Seitenangriffe 2 beträgt, müssen Sie eine weitere Runde verbringen, um einen solchen Angriff zu blockieren. Daher wird die Punktzahl um 1 erhöht
6. Wenn Punktzahl > = 4 ist, ist dies ein Haltepunkt
   In der Tat könnten Haltepunkte einfach aufgezählt werden, es gibt nicht viele von ihnen, aber ich habe dies nicht sofort verstanden.

 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; } 

Ja, wir werden endlich alles zusammenbringen

Die Haupthölle dahinter ist oben beschrieben. Es ist Zeit, etwas daraus zu formen. Funktion countWeight (x, y) - nimmt die Koordinaten der Zelle als Eingabe und gibt ihr Gewicht zurück. Was ist unter ihrer Kapuze?

Zuerst erhalten wir eine Reihe aller Angriffe, zu denen die Zelle gehört. ( getAllAttacks (x, y) ). Wir gehen alle Zeilen durch und zählen die Anzahl der Haltepunkte. Wenn es 2 Haltepunkte gibt, erinnern wir uns, dass eine solche Situation das Ergebnis des Spiels bestimmen und das Zellgewicht um 100 erhöhen kann.
Alle Haltepunkte müssen jedoch einem Spieler gehören, daher musste ich eine Prüfung in zwei Schritten durchführen: zuerst Kreuze, dann Nullen.

Da ich in der Reihe der Angriffsgewichte ( ATTACK_WEIGHTS [] ) keine Angriffe mit einer Potenz von 6 oder mehr bereitgestellt habe , musste ich sie durch Angriffe mit einer Potenz von 5 ersetzen. Es macht keinen Unterschied - sie alle führen zum Ende des Spiels.

Nun, wir fassen die Angriffsgewichte zusammen - das ist alles.

Ein weiterer kleiner Punkt: Damit der Bot am Ende des Spiels nicht dumm ist, wenn er bereits einen Angriff mit einer Potenz von 4 aufgebaut hat und über den aktuellen Zug nachdenkt, muss das Gewicht der Zelle deutlich erhöht werden, um einen solchen Angriff abzuschließen. Ohne dies kann sich die KI einfach gegen die „gefährlichen“ Angriffe des Gegners verteidigen, obwohl das Spiel gewonnen zu sein scheint. Der letzte Schritt ist wichtig.

 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 } } 

Wenn wir diese Funktion für eine bestimmte Zelle aufrufen, erhalten wir ihr Gewicht. Wir führen diesen Vorgang für alle Zellen durch und wählen die besten (mit dem höchsten Gewicht) aus. Da und los)

Den Rest des Codes finden Sie auf github . Es gibt bereits viel Material, und seine Präsentation lässt, wie ich nicht versucht habe, zu wünschen übrig. Aber wenn Sie bis zu diesem Punkt lesen könnten, lieber Leser, dann bin ich Ihnen dankbar.

Komm runter! Ja, du kannst ihn schlagen, aber das zu tun ist für mich persönlich ein wenig problematisch. Vielleicht bin ich einfach nicht vorsichtig genug. Versuche auch deine Stärke.

Ich weiß, dass es einfacher ist, aber ich weiß nicht wie. Ich würde gerne Leuten zuhören, die andere Implementierungen eines solchen Bots kennen oder anschauen.

Ich weiß, was besser sein kann. Ja ... Sie können bekannte Algorithmen wie Minimax verwenden, aber dafür benötigen Sie eine Wissensbasis auf dem Gebiet der Spieltheorie, mit der ich mich leider nicht rühmen kann.

In Zukunft plane ich, die Breakpoint-Analyse einige Schritte weiter hinzuzufügen, um den Bot zu einem noch ernsthafteren Gegner zu machen. Jetzt habe ich jedoch keine klare Vorstellung von der Umsetzung; Ich habe gerade die bevorstehende Sitzung und ein unvollständiges Diplom - was mich traurig macht.

Vielen Dank, wenn Sie bis zum Ende lesen.