AI для Tic Tac Toe

Question

Я работаю над проектом, проект заключается в создании игры с Нотами и Крестами. Я запрограммировал GUI, выиграл чеки e.t.c, но я застрял на программировании AI. Я представил массив 3x3, полный JButtons. Это было очень сложно.

Я ищу идеи, которые могли бы помочь мне составить код более эффективного и эффективного кода. Я думаю, что мой метод был не очень эффективным, и я хочу кодировать AI, чтобы сделать отметки горизонтально и вертикально (наступательные и защитные стратегии).

Заранее спасибо

Это то, что я сделал до сих пор:

общественного класса Компьютер {

public void AI() 
{ 

    for(int i=0; i<3; i++) 
    { 


     for (int j=0; j<3; j++) 
     { 
      // Diagonal Defensive Strategy for computerX and computerO 
      if (Game.computerX == true && Game.Board[i*1][j*1].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1+2][j*1+2].getText().equals("")) 
      { 
       Game.Board[i*1+2][j*1+2].setText("X"); 

      } 


      else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1][j*1].getText().equals("")) 
      { 
       Game.Board[i*1][j*1].setText("X"); 
      } 


      else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("O")) 
      { 
       Game.Board[i*1+1][j*1+1].setText("X"); 
      } 


      //*************************************** For computerO ******************************* 

      else if (Game.computerO == true && Game.Board[i*1][j*1].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1+2][j*1+2].getText().equals("")) 
      { 
       Game.Board[i*1+2][j*1+2].setText("O"); 

      } 


      else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1][j*1].getText().equals("")) 
      { 
       Game.Board[i*1][j*1].setText("O"); 
      } 


      else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("X")) 
      { 
       Game.Board[i*1+1][j*1+1].setText("O"); 
      } 

      //********************************************************************************************* 







      // Diagonal Offensive Strategy for computerX and computerO 
      if (Game.computerX == true && Game.Board[i*1][j*1].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1+2][j*1+2].getText().equals("")) 
      { 
       Game.Board[i*1+2][j*1+2].setText("X"); 
      } 


      else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1][j*1].getText().equals("")) 
      { 
       Game.Board[i*1][j*1].setText("X"); 
      } 

      else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("X")) 
      { 
       Game.Board[i*1+1][j*1+1].setText("X"); 
      } 



      //*************************************** For computerO ******************************* 

      else if (Game.computerO == true && Game.Board[i*1][j*1].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1+2][j*1+2].getText().equals("")) 
      { 
       Game.Board[i*1+2][j*1+2].setText("O"); 
      } 



      else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1][j*1].getText().equals("")) 
      { 
       Game.Board[i*1][j*1].setText("O"); 
      } 


      else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("O")) 
      { 
       Game.Board[i*1+1][j*1+1].setText("O"); 
      } 


      //************************************************************************************** 



    } 

Answer 1

Простая оборонительная стратегия в псевдокоде:

for every line 
    if line is not full and opponent has two Xs in this line 
     place your O in the remaining space 

for every pair of lines 
    if lines intersect, there is no element in the intersection and opponent has X in each line and you have no Xs in any of these two 
     place your O in the intersecton 

Вы следует также попытаться улучшить читаемость вашего кода, попробуйте написать выше lgorithm так:

for (Line line : allLines()) { 
    if (line.has(2, "X") && line.has(0, "O")) { 
     place(line.getEmptySpace(), "O"); 
    } 

for (PairOfLines pairOfLines : allPairsOfLines()) { 
    Line line1 = pairOfLines.getOne(); 
    Line line2 = pairOfLines.getTwo(); 
    if (line1.intersects(line2) 
      && pairOfLines.getIntersection().isEmpty() 
      && line1.has(1, "X") 
      && line2.has(1, "X") 
      && pairOfLines.has(0, "O")) { 
     place(pairofLines.getIntersection(), "O"); 
    } 
} 

Вам нужно будет создать некоторые вспомогательные методы, чтобы сделать его компиляции, но код чист, и вы можете легко увидеть поведение из кода.

Тогда вы можете сделать аналогичным образом для наступательной стратегии, например. найдите две пересекающиеся линии, где есть ваш один O и отсутствие X's соперника.

Я попробовал, и вот что я придумал. Он не был Test Driven (здесь есть пробелы), и он нуждается в большем количестве некоторые рефакторинга:

import org.junit.Test; 

import static blah.tictactoe.Cog.O; 
import static blah.tictactoe.Cog.X; 
import static com.shazam.shazamcrest.MatcherAssert.assertThat; 
import static com.shazam.shazamcrest.matcher.Matchers.sameBeanAs; 
import static org.hamcrest.CoreMatchers.is; 

public class BoardTest { 

    @Test 
    public void blocksLineOfTwo() { 
     Board board = new Board(new Cog[][]{ 
       {X, null, null}, 
       {null, X, null}, 
       {null, null, null} 
     }); 

     board.placeOAutomatically(); 

     assertThat(board, is(sameBeanAs(new Board(new Cog[][]{ 
       {X, null, null}, 
       {null, X, null}, 
       {null, null, O } 
     })))); 
    } 

    @Test 
    public void blocksIntersectionForOneCogOnEachOfLines() { 
     Board board = new Board(new Cog[][]{ 
       {null, null, null}, 
       {O, O, X }, 
       {X, null, null} 
     }); 

     board.placeOAutomatically(); 

     assertThat(board, is(sameBeanAs(new Board(new Cog[][]{ 
       {null, null, null}, 
       {O, O, X }, 
       {X, null, O } 
     })))); 
    } 

    @Test 
    public void placesWinningCog() { 
     Board board = new Board(new Cog[][]{ 
       {O, O, null}, 
       {null, null, null}, 
       {X, X, null} 
     }); 

     board.placeOAutomatically(); 

     assertThat(board, is(sameBeanAs(new Board(new Cog[][]{ 
       {O, O, O }, 
       {null, null, null}, 
       {X, X, null} 
     })))); 
    } 

} 

---- 

public enum Cog { 
    X, O 
} 

---- 

public class Field { 

    private Cog cog; 

    public Field(Cog cog) { 
     this.cog = cog; 
    } 

    public Cog getCog() { 
     return cog; 
    } 

    public boolean isEmpty() { 
     return cog == null; 
    } 

    public void setCog(Cog cog) { 
     this.cog = cog; 
    } 

} 

---- 

import com.google.common.collect.ImmutableSet; 
import com.google.common.collect.Sets; 

import java.util.Set; 

public class Line { 

    private final Set<Field> fields; 

    public Line(Field fieldOne, Field fieldTwo, Field fieldThree) { 
     fields = ImmutableSet.of(fieldOne, fieldTwo, fieldThree); 
    } 

    public Set<Field> getFields() { 
     return fields; 
    } 

    public boolean has(int count, Cog cog) { 
     return fields.stream().map(Field::getCog).filter(c -> c == cog).count() == count; 
    } 

    public Field getEmptySpace() { 
     long emptyFields = fields.stream().filter(Field::isEmpty).count(); 
     if (emptyFields != 1) { 
      throw new IllegalStateException("there are " + emptyFields + " empty fields"); 
     } 
     return fields.stream().filter(Field::isEmpty).findFirst().get(); 
    } 

    public boolean intersects(Line line) { 
     return !Sets.intersection(this.fields, line.fields).isEmpty(); 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 

     Line line = (Line) o; 

     return fields.equals(line.fields); 
    } 

} 

---- 

import com.google.common.collect.Sets; 

import java.util.HashSet; 
import java.util.Set; 

public class PairOfLines { 

    private final Line lineOne; 
    private final Line lineTwo; 

    public PairOfLines(Line lineOne, Line lineTwo) { 
     this.lineOne = lineOne; 
     this.lineTwo = lineTwo; 
    } 

    public Line getOne() { 
     return lineOne; 
    } 

    public Line getTwo() { 
     return lineTwo; 
    } 

    public Field getIntersection() { 
     return Sets.intersection(lineOne.getFields(), lineTwo.getFields()).iterator().next(); 
    } 

    public boolean has(int count, Cog cog) { 
     Set<Field> allFields = new HashSet<>(); 
     allFields.addAll(lineOne.getFields()); 
     allFields.addAll(lineTwo.getFields()); 
     return allFields.stream().map(Field::getCog).filter(c -> c == cog).count() == count; 
    } 

} 

---- 

import com.google.common.collect.ImmutableSet; 

import java.util.Set; 

import static blah.tictactoe.Cog.X; 
import static blah.tictactoe.Cog.O; 

public class Board { 

    private final Field[][] matrix = new Field[3][3]; 

    public Board(Cog[][] matrix) { 
     for (int i = 0; i < 3; i++) { 
      for (int j = 0; j < 3; j++) { 
       this.matrix[i][j] = new Field(matrix[i][j]); 
      } 
     } 
    } 

    public void placeOAutomatically() { 
     // winning move 
     for (Line line : allLines()) { 
      if (line.has(2, O) && line.has(0, X)) { 
       line.getEmptySpace().setCog(O); 
       return; 
      } 
     } 

     // block line of two 
     for (Line line : allLines()) { 
      if (line.has(2, X) && line.has(0, O)) { 
       line.getEmptySpace().setCog(O); 
       return; 
      } 
     } 

     // block intersection 
     for (PairOfLines pairOfLines : allPairsOfIntersectingLines()) { 
      if (pairOfLines.getIntersection().isEmpty() 
        && pairOfLines.getOne().has(1, X) 
        && pairOfLines.getTwo().has(1, X) 
        && pairOfLines.has(0, O)) { 
       pairOfLines.getIntersection().setCog(O); 
       return; 
      } 
     } 
    } 


    private Set<Line> allLines() { 
     return ImmutableSet.of(
       new Line(matrix[0][0], matrix[0][1], matrix[0][2]), 
       new Line(matrix[1][0], matrix[1][1], matrix[1][2]), 
       new Line(matrix[2][0], matrix[2][1], matrix[2][2]), 

       new Line(matrix[0][0], matrix[1][0], matrix[2][0]), 
       new Line(matrix[0][1], matrix[1][1], matrix[2][1]), 
       new Line(matrix[0][2], matrix[1][2], matrix[2][2]), 

       new Line(matrix[0][0], matrix[1][1], matrix[2][2]), 
       new Line(matrix[0][2], matrix[1][1], matrix[2][0]) 
     ); 
    } 

    private Set<PairOfLines> allPairsOfIntersectingLines() { 
     ImmutableSet.Builder<PairOfLines> builder = new ImmutableSet.Builder<>(); 
     for (Line lineOne : allLines()) { 
      for (Line lineTwo : allLines()) { 
       if (!lineOne.equals(lineTwo) && lineOne.intersects(lineTwo)) { 
        builder.add(new PairOfLines(lineOne, lineTwo)); 
       } 
      } 
     } 
     return builder.build(); 
    } 

} 

Несколько зависимостей Maven необходимое:

<dependencies> 
    <!-- COMPILE --> 
    <dependency> 
     <groupId>com.google.collections</groupId> 
     <artifactId>google-collections</artifactId> 
     <version>1.0</version> 
    </dependency> 

    <!-- TEST --> 
    <dependency> 
     <groupId>junit</groupId> 
     <artifactId>junit-dep</artifactId> 
     <version>4.11</version> 
     <scope>test</scope> 
    </dependency> 
    <dependency> 
     <groupId>org.hamcrest</groupId> 
     <artifactId>hamcrest-library</artifactId> 
     <version>1.3</version> 
     <scope>test</scope> 
    </dependency> 
    <dependency> 
     <groupId>org.hamcrest</groupId> 
     <artifactId>hamcrest-core</artifactId> 
     <version>1.3</version> 
     <scope>test</scope> 
    </dependency> 
    <dependency> 
     <groupId>com.shazam</groupId> 
     <artifactId>shazamcrest</artifactId> 
     <version>0.9</version> 
     <scope>test</scope> 
     <exclusions> 
      <exclusion> 
       <groupId>com.google.guava</groupId> 
       <artifactId>guava</artifactId> 
      </exclusion> 
     </exclusions> 
    </dependency> 
</dependencies> 

Answer 2

Самый простой способ кодирования ИИ для такого рода игра - это Minimax algorithm, которая является алгоритмом для игр с двумя игроками, где каждый игрок пытается сделать лучший ход. Вам просто нужно закодировать алгоритм, как описано на странице wiki, и написать простую функцию оценки, которая возвращает 1 для выигрыша, 0 для ничьей (или еще не результат) и -1 для потери (при более сложной оценке алгоритм могут с удовольствием играть в шахматы). Tic-tac-toe - достаточно простая игра, в которой вы можете сделать полную оценку глубины для каждого хода - очевидно, что более сложная игра, такая как шахматы, потребует отсечения.

Вы также можете посмотреть немного более сложную, но также более эффективную версию этого алгоритма, известную как Alpha-Beta pruning.