algorithm - 三目並べゲームオーバーを決定するためのアルゴリズム

Question

私はJavaで三目並べのゲームを作成しました。ゲームの終了を判断する現在の方法は、ゲームが終了する可能性のある次のシナリオを考慮しています。

1. ボードはいっぱいで、勝者はまだ宣言されていません。ゲームは引き分けです。
2. クロスが勝ちました。
3. サークルが勝ちました。

残念ながら、そうするために、テーブルからこれらのシナリオの事前定義されたセットを読み取ります。ボード上にスペースが9つしかないため、テーブルがやや小さいことを考えると、これは必ずしも悪いことではありませんが、ゲームが終了したかどうかを判断するためのより良いアルゴリズムの方法はありますか？9つのスペースがいっぱいかどうかを確認するのは簡単なので、誰かが勝ったかどうかの判断が問題の核心です。

テーブルメソッドが解決策かもしれませんが、そうでない場合は何ですか？また、ボードがサイズでない場合はどうなりn=9ますか？それがはるかに大きなボード、たとえばn=16、n=25などで、連続して配置されたアイテムの数が、などになるx=4とどうなりx=5ますか？すべてに使用する一般的なアルゴリズムn = { 9, 16, 25, 36 ... }？

Answer 1

X または O が最新の動きを行った後にのみ勝利の動きが発生することがわかっているため、勝利ボードを決定しようとするときに検索スペースを制限するために、その動きに含まれるオプションの診断を使用して行/列のみを検索できます。また、ドローの三目並べゲームでは、最後のムーブが勝利のムーブでない場合に行われると、既定ではドロー ゲームになります。

このコードは、n 行 n 列の n x n ボードで勝つためのものです (3x3 ボードでは 3 行が必要など)。

public class TripleT {
    
    enum State{Blank, X, O};
    
    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;
    
    void Move(int x, int y, State s){
        if(board[x][y] == State.Blank){
            board[x][y] = s;
        }
        moveCount++;
        
        //check end conditions
        
        //check col
        for(int i = 0; i < n; i++){
            if(board[x][i] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }
        
        //check row
        for(int i = 0; i < n; i++){
            if(board[i][y] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }
        
        //check diag
        if(x == y){
            //we're on a diagonal
            for(int i = 0; i < n; i++){
                if(board[i][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }
            
        //check anti diag (thanks rampion)
        if(x + y == n - 1){
            for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check draw
        if(moveCount == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }
}

Answer 2

魔方陣http://mathworld.wolfram.com/MagicSquare.htmlを使用できます。行、列、またはdiagの合計が15になると、プレーヤーが勝ちます。

Answer 3

この疑似コードはどうですか:

プレーヤーが位置 (x,y) に駒を置いた後:

col=row=diag=rdiag=0
winner=false
for i=1 to n
  if cell[x,i]=player then col++
  if cell[i,y]=player then row++
  if cell[i,i]=player then diag++
  if cell[i,n-i+1]=player then rdiag++
if row=n or col=n or diag=n or rdiag=n then winner=true

char [n,n] の配列を使用し、O、X、および空のスペースを使用します。

1. 単純。
2. 1 つのループ。
3. 5 つの単純な変数: 4 つの整数と 1 つのブール値。
4. n の任意のサイズにスケーリングします。
5. 現在のピースのみをチェックします。
6. 魔法はありません。:)

Answer 4

これはOsama ALASSIRY's answerに似ていますが、定数空間と線形時間を線形空間と定数時間と交換します。つまり、初期化後のループはありません。

(0,0)各行、各列、および 2 つの対角線 (対角線と反対角線)のペアを初期化します。これらのペアは(sum,sum)、対応する行、列、または対角線のピースの累積を表します。

プレーヤー A の駒の値は (1,0)
プレイヤー B の駒の値は (0,1)

プレイヤーがピースを配置すると、対応する行のペア、列のペア、および対角線のペア (対角線上にある場合) を更新します。新しく更新された行、列、または対角線のペアがいずれ(n,0)かに等しい場合、または(0,n)A または B のいずれかがそれぞれ勝ちました。

漸近分析:

O(1) 時間 (移動ごと)
O(n) スペース (全体)

4*(n+1)メモリの使用には、整数を使用します。

two_elements*n_rows + two_elements*n_columns +
two_elements*two_diagonals = 4*n + 4 整数 = 4(n+1) 整数

演習: 引き分けを 1 回の移動で O(1) 時間でテストする方法がわかりますか? もしそうなら、引き分けでゲームを早く終わらせることができます。

Answer 5

私がjavascriptで取り組んでいるプロジェクトのために書いた私の解決策を次に示します。いくつかの配列のメモリ コストを気にしないのであれば、おそらく最も速くて簡単な解決策です。最後の移動の位置を知っていることを前提としています。

/*
 * Determines if the last move resulted in a win for either player
 * board: is an array representing the board
 * lastMove: is the boardIndex of the last (most recent) move
 *  these are the boardIndexes:
 *
 *   0 | 1 | 2
 *  ---+---+---
 *   3 | 4 | 5
 *  ---+---+---
 *   6 | 7 | 8
 * 
 * returns true if there was a win
 */
var winLines = [
    [[1, 2], [4, 8], [3, 6]],
    [[0, 2], [4, 7]],
    [[0, 1], [4, 6], [5, 8]],
    [[4, 5], [0, 6]],
    [[3, 5], [0, 8], [2, 6], [1, 7]],
    [[3, 4], [2, 8]],
    [[7, 8], [2, 4], [0, 3]],
    [[6, 8], [1, 4]],
    [[6, 7], [0, 4], [2, 5]]
];
function isWinningMove(board, lastMove) {
    var player = board[lastMove];
    for (var i = 0; i < winLines[lastMove].length; i++) {
        var line = winLines[lastMove][i];
        if(player === board[line[0]] && player === board[line[1]]) {
            return true;
        }
    }
    return false;
}

Answer 6

これは私の C プログラミング クラス用に書いたものです。

ここに掲載している他の例は、どのサイズの長方形のグリッドでも機能せず、任意の数のN行の連続したマークが勝つためです。

私のアルゴリズムは、checkWinner()関数の中にあります。勝者をチェックするために魔法の数字や凝ったものは使用しません。単純に 4 つの for ループを使用します。

// This program will work with any whole number sized rectangular gameBoard.
// It checks for N marks in straight lines (rows, columns, and diagonals).
// It is prettiest when ROWS and COLS are single digit numbers.
// Try altering the constants for ROWS, COLS, and N for great fun!    

// PPDs come first

    #include <stdio.h>
    #define ROWS 9              // The number of rows our gameBoard array will have
    #define COLS 9              // The number of columns of the same - Single digit numbers will be prettier!
    #define N 3                 // This is the number of contiguous marks a player must have to win
    #define INITCHAR ' '        // This changes the character displayed (a ' ' here probably looks the best)
    #define PLAYER1CHAR 'X'     // Some marks are more aesthetically pleasing than others
    #define PLAYER2CHAR 'O'     // Change these lines if you care to experiment with them


// Function prototypes are next

    int playGame    (char gameBoard[ROWS][COLS]);               // This function allows the game to be replayed easily, as desired
    void initBoard  (char gameBoard[ROWS][COLS]);               // Fills the ROWSxCOLS character array with the INITCHAR character
    void printBoard (char gameBoard[ROWS][COLS]);               // Prints out the current board, now with pretty formatting and #s!
    void makeMove   (char gameBoard[ROWS][COLS], int player);   // Prompts for (and validates!) a move and stores it into the array
    int checkWinner (char gameBoard[ROWS][COLS], int player);   // Checks the current state of the board to see if anyone has won

// The starting line
int main (void)
{
    // Inits
    char gameBoard[ROWS][COLS];     // Our gameBoard is declared as a character array, ROWS x COLS in size
    int winner = 0;
    char replay;

    //Code
    do                              // This loop plays through the game until the user elects not to
    {
        winner = playGame(gameBoard);
        printf("\nWould you like to play again? Y for yes, anything else exits: ");

        scanf("%c",&replay);        // I have to use both a scanf() and a getchar() in
        replay = getchar();         // order to clear the input buffer of a newline char
                                    // (http://cboard.cprogramming.com/c-programming/121190-problem-do-while-loop-char.html)

    } while ( replay == 'y' || replay == 'Y' );

    // Housekeeping
    printf("\n");
    return winner;
}


int playGame(char gameBoard[ROWS][COLS])
{
    int turn = 0, player = 0, winner = 0, i = 0;

    initBoard(gameBoard);

    do
    {
        turn++;                                 // Every time this loop executes, a unique turn is about to be made
        player = (turn+1)%2+1;                  // This mod function alternates the player variable between 1 & 2 each turn
        makeMove(gameBoard,player);
        printBoard(gameBoard);
        winner = checkWinner(gameBoard,player);

        if (winner != 0)
        {
            printBoard(gameBoard);

            for (i=0;i<19-2*ROWS;i++)           // Formatting - works with the default shell height on my machine
                printf("\n");                   // Hopefully I can replace these with something that clears the screen for me

            printf("\n\nCongratulations Player %i, you've won with %i in a row!\n\n",winner,N);
            return winner;
        }

    } while ( turn < ROWS*COLS );                           // Once ROWS*COLS turns have elapsed

    printf("\n\nGame Over!\n\nThere was no Winner :-(\n");  // The board is full and the game is over
    return winner;
}


void initBoard (char gameBoard[ROWS][COLS])
{
    int row = 0, col = 0;

    for (row=0;row<ROWS;row++)
    {
        for (col=0;col<COLS;col++)
        {
            gameBoard[row][col] = INITCHAR;     // Fill the gameBoard with INITCHAR characters
        }
    }

    printBoard(gameBoard);                      // Having this here prints out the board before
    return;                             // the playGame function asks for the first move
}


void printBoard (char gameBoard[ROWS][COLS])    // There is a ton of formatting in here
{                                               // That I don't feel like commenting :P
    int row = 0, col = 0, i=0;                  // It took a while to fine tune
                                                // But now the output is something like:
    printf("\n");                               // 
                                                //    1   2   3
    for (row=0;row<ROWS;row++)                  // 1    |   |
    {                                           //   -----------
        if (row == 0)                           // 2    |   |
        {                                       //   -----------
            printf("  ");                       // 3    |   |

            for (i=0;i<COLS;i++)
            {
                printf(" %i  ",i+1);
            }

            printf("\n\n");
        }

        for (col=0;col<COLS;col++)
        {
            if (col==0)
                printf("%i ",row+1);

            printf(" %c ",gameBoard[row][col]);

            if (col<COLS-1)
                printf("|");
        }

        printf("\n");

        if (row < ROWS-1)
        {
            for(i=0;i<COLS-1;i++)
            {
                if(i==0)
                    printf("  ----");
                else
                    printf("----");
            }

            printf("---\n");
        }
    }

    return;
}


void makeMove (char gameBoard[ROWS][COLS],int player)
{
    int row = 0, col = 0, i=0;
    char currentChar;

    if (player == 1)                    // This gets the correct player's mark
        currentChar = PLAYER1CHAR;
    else
        currentChar = PLAYER2CHAR;

    for (i=0;i<21-2*ROWS;i++)           // Newline formatting again :-(
        printf("\n");

    printf("\nPlayer %i, please enter the column of your move: ",player);
    scanf("%i",&col);
    printf("Please enter the row of your move: ");
    scanf("%i",&row);

    row--;                              // These lines translate the user's rows and columns numbering
    col--;                              // (starting with 1) to the computer's (starting with 0)

    while(gameBoard[row][col] != INITCHAR || row > ROWS-1 || col > COLS-1)  // We are not using a do... while because
    {                                                                       // I wanted the prompt to change
        printBoard(gameBoard);
        for (i=0;i<20-2*ROWS;i++)
            printf("\n");
        printf("\nPlayer %i, please enter a valid move! Column first, then row.\n",player);
        scanf("%i %i",&col,&row);

        row--;                          // See above ^^^
        col--;
    }

    gameBoard[row][col] = currentChar;  // Finally, we store the correct mark into the given location
    return;                             // And pop back out of this function
}


int checkWinner(char gameBoard[ROWS][COLS], int player)     // I've commented the last (and the hardest, for me anyway)
{                                                           // check, which checks for backwards diagonal runs below >>>
    int row = 0, col = 0, i = 0;
    char currentChar;

    if (player == 1)
        currentChar = PLAYER1CHAR;
    else
        currentChar = PLAYER2CHAR;

    for ( row = 0; row < ROWS; row++)                       // This first for loop checks every row
    {
        for ( col = 0; col < (COLS-(N-1)); col++)           // And all columns until N away from the end
        {
            while (gameBoard[row][col] == currentChar)      // For consecutive rows of the current player's mark
            {
                col++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }

    for ( col = 0; col < COLS; col++)                       // This one checks for columns of consecutive marks
    {
        for ( row = 0; row < (ROWS-(N-1)); row++)
        {
            while (gameBoard[row][col] == currentChar)
            {
                row++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }

    for ( col = 0; col < (COLS - (N-1)); col++)             // This one checks for "forwards" diagonal runs
    {
        for ( row = 0; row < (ROWS-(N-1)); row++)
        {
            while (gameBoard[row][col] == currentChar)
            {
                row++;
                col++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }
                                                        // Finally, the backwards diagonals:
    for ( col = COLS-1; col > 0+(N-2); col--)           // Start from the last column and go until N columns from the first
    {                                                   // The math seems strange here but the numbers work out when you trace them
        for ( row = 0; row < (ROWS-(N-1)); row++)       // Start from the first row and go until N rows from the last
        {
            while (gameBoard[row][col] == currentChar)  // If the current player's character is there
            {
                row++;                                  // Go down a row
                col--;                                  // And back a column
                i++;                                    // The i variable tracks how many consecutive marks have been found
                if (i == N)                             // Once i == N
                {
                    return player;                      // Return the current player number to the
                }                                       // winnner variable in the playGame function
            }                                           // If it breaks out of the while loop, there weren't N consecutive marks
            i = 0;                                      // So make i = 0 again
        }                                               // And go back into the for loop, incrementing the row to check from
    }

    return 0;                                           // If we got to here, no winner has been detected,
}                                                       // so we pop back up into the playGame function

// The end!

// Well, almost.

// Eventually I hope to get this thing going
// with a dynamically sized array. I'll make
// the CONSTANTS into variables in an initGame
// function and allow the user to define them.

Answer 7

ボードがn × nの場合、 n行、n列、2つの対角線があります。それらのそれぞれをすべてXまたはすべてOでチェックして、勝者を見つけます。

勝つためにx < nの連続した正方形しか必要としない場合、それはもう少し複雑です。最も明白な解決策は、勝者がないか各x × xの正方形をチェックすることです。これを示すコードを次に示します。

（私は実際にこの*咳*をテストしませんでしたが、最初の試行でコンパイルされました、イェーイ！）

public class TicTacToe
{
    public enum Square { X, O, NONE }

    /**
     * Returns the winning player, or NONE if the game has
     * finished without a winner, or null if the game is unfinished.
     */
    public Square findWinner(Square[][] board, int lengthToWin) {
        // Check each lengthToWin x lengthToWin board for a winner.    
        for (int top = 0; top <= board.length - lengthToWin; ++top) {
            int bottom = top + lengthToWin - 1;

            for (int left = 0; left <= board.length - lengthToWin; ++left) {
                int right = left + lengthToWin - 1;

                // Check each row.
                nextRow: for (int row = top; row <= bottom; ++row) {
                    if (board[row][left] == Square.NONE) {
                        continue;
                    }

                    for (int col = left; col <= right; ++col) {
                        if (board[row][col] != board[row][left]) {
                            continue nextRow;
                        }
                    }

                    return board[row][left];
                }

                // Check each column.
                nextCol: for (int col = left; col <= right; ++col) {
                    if (board[top][col] == Square.NONE) {
                        continue;
                    }

                    for (int row = top; row <= bottom; ++row) {
                        if (board[row][col] != board[top][col]) {
                            continue nextCol;
                        }
                    }

                    return board[top][col];
                }

                // Check top-left to bottom-right diagonal.
                diag1: if (board[top][left] != Square.NONE) {
                    for (int i = 1; i < lengthToWin; ++i) {
                        if (board[top+i][left+i] != board[top][left]) {
                            break diag1;
                        }
                    }

                    return board[top][left];
                }

                // Check top-right to bottom-left diagonal.
                diag2: if (board[top][right] != Square.NONE) {
                    for (int i = 1; i < lengthToWin; ++i) {
                        if (board[top+i][right-i] != board[top][right]) {
                            break diag2;
                        }
                    }

                    return board[top][right];
                }
            }
        }

        // Check for a completely full board.
        boolean isFull = true;

        full: for (int row = 0; row < board.length; ++row) {
            for (int col = 0; col < board.length; ++col) {
                if (board[row][col] == Square.NONE) {
                    isFull = false;
                    break full;
                }
            }
        }

        // The board is full.
        if (isFull) {
            return Square.NONE;
        }
        // The board is not full and we didn't find a solution.
        else {
            return null;
        }
    }
}

Answer 8

Java はよくわかりませんが、C は知っているので、adk の魔方陣のアイデアを ( Hardwareguy の検索制限と共に) 試してみました。

// tic-tac-toe.c
// to compile:
//  % gcc -o tic-tac-toe tic-tac-toe.c
// to run:
//  % ./tic-tac-toe
#include <stdio.h>

// the two types of marks available
typedef enum { Empty=2, X=0, O=1, NumMarks=2 } Mark;
char const MarkToChar[] = "XO ";

// a structure to hold the sums of each kind of mark
typedef struct { unsigned char of[NumMarks]; } Sum;

// a cell in the board, which has a particular value
#define MAGIC_NUMBER 15
typedef struct {
  Mark mark;
  unsigned char const value;
  size_t const num_sums;
  Sum * const sums[4];
} Cell;

#define NUM_ROWS 3
#define NUM_COLS 3

// create a sum for each possible tic-tac-toe
Sum row[NUM_ROWS] = {0};
Sum col[NUM_COLS] = {0};
Sum nw_diag = {0};
Sum ne_diag = {0};

// initialize the board values so any row, column, or diagonal adds to
// MAGIC_NUMBER, and so they each record their sums in the proper rows, columns,
// and diagonals
Cell board[NUM_ROWS][NUM_COLS] = { 
  { 
    { Empty, 8, 3, { &row[0], &col[0], &nw_diag } },
    { Empty, 1, 2, { &row[0], &col[1] } },
    { Empty, 6, 3, { &row[0], &col[2], &ne_diag } },
  },
  { 
    { Empty, 3, 2, { &row[1], &col[0] } },
    { Empty, 5, 4, { &row[1], &col[1], &nw_diag, &ne_diag } },
    { Empty, 7, 2, { &row[1], &col[2] } },
  },
  { 
    { Empty, 4, 3, { &row[2], &col[0], &ne_diag } },
    { Empty, 9, 2, { &row[2], &col[1] } },
    { Empty, 2, 3, { &row[2], &col[2], &nw_diag } },
  }
};

// print the board
void show_board(void)
{
  size_t r, c;
  for (r = 0; r < NUM_ROWS; r++) 
  {
    if (r > 0) { printf("---+---+---\n"); }
    for (c = 0; c < NUM_COLS; c++) 
    {
      if (c > 0) { printf("|"); }
      printf(" %c ", MarkToChar[board[r][c].mark]);
    }
    printf("\n");
  }
}


// run the game, asking the player for inputs for each side
int main(int argc, char * argv[])
{
  size_t m;
  show_board();
  printf("Enter moves as \"<row> <col>\" (no quotes, zero indexed)\n");
  for( m = 0; m < NUM_ROWS * NUM_COLS; m++ )
  {
    Mark const mark = (Mark) (m % NumMarks);
    size_t c, r;

    // read the player's move
    do
    {
      printf("%c's move: ", MarkToChar[mark]);
      fflush(stdout);
      scanf("%d %d", &r, &c);
      if (r >= NUM_ROWS || c >= NUM_COLS)
      {
        printf("illegal move (off the board), try again\n");
      }
      else if (board[r][c].mark != Empty)
      {
        printf("illegal move (already taken), try again\n");
      }
      else
      {
        break;
      }
    }
    while (1);

    {
      Cell * const cell = &(board[r][c]);
      size_t s;

      // update the board state
      cell->mark = mark;
      show_board();

      // check for tic-tac-toe
      for (s = 0; s < cell->num_sums; s++)
      {
        cell->sums[s]->of[mark] += cell->value;
        if (cell->sums[s]->of[mark] == MAGIC_NUMBER)
        {
          printf("tic-tac-toe! %c wins!\n", MarkToChar[mark]);
          goto done;
        }
      }
    }
  }
  printf("stalemate... nobody wins :(\n");
done:
  return 0;
}

コンパイルとテストがうまくいきます。

% gcc -o tic-tac-toe tic-tac-toe.c
％ 。/○×ゲーム
     | | | |
  ---+---+---
     | | | |
  ---+---+---
     | | | |
  移動を " " として入力します (引用符なし、ゼロ インデックス)
  Xの手：1 2
     | | | |
  ---+---+---
     | | | | バツ
  ---+---+---
     | | | |
  Oの手：1 2
  不正な移動 (既に取得済み)、再試行
  Oの手：3 3
  不正な動き (盤面外)、やり直してください
  Oの手：2 2
     | | | |
  ---+---+---
     | | | | バツ
  ---+---+---
     | | | | 〇
  Xの手: 1 0
     | | | |
  ---+---+---
   X | | | バツ
  ---+---+---
     | | | | 〇
  Oの手：1 1
     | | | |
  ---+---+---
   X | お | バツ
  ---+---+---
     | | | | 〇
  Xの手: 0 0
   X | | |
  ---+---+---
   X | お | バツ
  ---+---+---
     | | | | 〇
  Oの手: 2 0
   X | | |
  ---+---+---
   X | お | バツ
  ---+---+---
   お | | | 〇
  Xの手：2 1
   X | | |
  ---+---+---
   X | お | バツ
  ---+---+---
   お | X | 〇
  Oの手：0 2
   X | | | 〇
  ---+---+---
   X | お | バツ
  ---+---+---
   お | X | 〇
  ○×ゲーム！ああ、勝った！
％ 。/○×ゲーム
     | | | |
  ---+---+---
     | | | |
  ---+---+---
     | | | |
  移動を " " として入力します (引用符なし、ゼロ インデックス)
  Xの手: 0 0
   X | | |
  ---+---+---
     | | | |
  ---+---+---
     | | | |
  Oの手：0 1
   X | お |
  ---+---+---
     | | | |
  ---+---+---
     | | | |
  Xの手：0 2
   X | お | バツ
  ---+---+---
     | | | |
  ---+---+---
     | | | |
  Oの手：1 0
   X | お | バツ
  ---+---+---
   お | | |
  ---+---+---
     | | | |
  Xの手：1 1
   X | お | バツ
  ---+---+---
   お | X |
  ---+---+---
     | | | |
  Oの手: 2 0
   X | お | バツ
  ---+---+---
   お | X |
  ---+---+---
   お | | |
  Xの手：2 1
   X | お | バツ
  ---+---+---
   お | X |
  ---+---+---
   お | X |
  Oの手：2 2
   X | お | バツ
  ---+---+---
   お | X |
  ---+---+---
   お | X | 〇
  Xの手：1 2
   X | お | バツ
  ---+---+---
   お | X | バツ
  ---+---+---
   お | X | 〇
  膠着状態...誰も勝てません:(
%

楽しかったです、ありがとう！

実際、考えてみると、魔方陣は必要ありません。各行/列/対角線のカウントだけです。nこれは、魔方陣を×n行列に一般化するよりも少し簡単ですn。

Answer 9

ある面接で同じ質問をされました。私の考え: 0 で行列を初期化します。3 つの配列を保持します 1)sum_row (サイズ n) 2) sum_column (サイズ n) 3) 対角 (サイズ 2)

(X) ずつ移動するたびにボックスの値を 1 減らし、(0) ずつ移動するたびに 1 ずつ増やします。現在の移動で変更された行/列/対角線の合計が -3 または + のいずれかである場合、任意の時点で3 は誰かがゲームに勝ったことを意味します。ドローの場合、上記のアプローチを使用して moveCount 変数を保持できます。

私は何かが足りないと思いますか？

編集: nxn 行列にも同じことが使用できます。合計は +3 または -3 である必要があります。

Answer 10

私はパーティーに遅れましたが、魔方陣を使用することでわかった 1 つの利点を指摘したいと思います。ゲームがいつ終了するかを計算するために使用されているだけです。

この魔方陣を取る：

4 9 2
3 5 7
8 1 6

scoresまず、移動するたびにインクリメントされる配列を設定します。詳細については、この回答を参照してください。[0,0] と [0,1] で X を 2 回続けて不正にプレイすると、scores配列は次のようになります。

[7, 0, 0, 4, 3, 0, 4, 0];

そして、ボードは次のようになります。

X . .
X . .
. . .

次に、勝つ/ブロックする正方形への参照を取得するために必要なことは次のとおりです。

get_winning_move = function() {
  for (var i = 0, i < scores.length; i++) {
    // keep track of the number of times pieces were added to the row
    // subtract when the opposite team adds a piece
    if (scores[i].inc === 2) {
      return 15 - state[i].val; // 8
    }
  }
}

実際には、実装には (JavaScript での) 番号付きキーの処理など、いくつかの追加のトリックが必要ですが、私はそれが非常に簡単で、気晴らしの数学を楽しんでいました.

Answer 11

ポイントがアンチ診断にあったかどうかを判断する非ループの方法:

`if (x + y == n - 1)`

Answer 12

これは非常に簡単なチェック方法です。

    public class Game() { 

    Game player1 = new Game('x');
    Game player2 = new Game('o');

    char piece;

    Game(char piece) {
       this.piece = piece;
    }

public void checkWin(Game player) {

    // check horizontal win
    for (int i = 0; i <= 6; i += 3) {

        if (board[i] == player.piece &&
                board[i + 1] == player.piece &&
                board[i + 2] == player.piece)
            endGame(player);
    }

    // check vertical win
    for (int i = 0; i <= 2; i++) {

        if (board[i] == player.piece &&
                board[i + 3] == player.piece &&
                board[i + 6] == player.piece)
            endGame(player);
    }

    // check diagonal win
    if ((board[0] == player.piece &&
            board[4] == player.piece &&
            board[8] == player.piece) ||
            board[2] == player.piece &&
            board[4] == player.piece &&
            board[6] == player.piece)
        endGame(player);
    }

}

Answer 13

行、列、対角チェックでいくつかの最適化を行いました。特定の列または対角線をチェックする必要がある場合は、主に最初のネストされたループで決定されます。そのため、列または対角線のチェックを避けて時間を節約します。これは、ボードのサイズが大きくなり、かなりの数のセルが埋められていない場合に大きな影響を与えます。

これがそのためのJavaコードです。

    int gameState(int values[][], int boardSz) {


    boolean colCheckNotRequired[] = new boolean[boardSz];//default is false
    boolean diag1CheckNotRequired = false;
    boolean diag2CheckNotRequired = false;
    boolean allFilled = true;


    int x_count = 0;
    int o_count = 0;
    /* Check rows */
    for (int i = 0; i < boardSz; i++) {
        x_count = o_count = 0;
        for (int j = 0; j < boardSz; j++) {
            if(values[i][j] == x_val)x_count++;
            if(values[i][j] == o_val)o_count++;
            if(values[i][j] == 0)
            {
                colCheckNotRequired[j] = true;
                if(i==j)diag1CheckNotRequired = true;
                if(i + j == boardSz - 1)diag2CheckNotRequired = true;
                allFilled = false;
                //No need check further
                break;
            }
        }
        if(x_count == boardSz)return X_WIN;
        if(o_count == boardSz)return O_WIN;         
    }


    /* check cols */
    for (int i = 0; i < boardSz; i++) {
        x_count = o_count = 0;
        if(colCheckNotRequired[i] == false)
        {
            for (int j = 0; j < boardSz; j++) {
                if(values[j][i] == x_val)x_count++;
                if(values[j][i] == o_val)o_count++;
                //No need check further
                if(values[i][j] == 0)break;
            }
            if(x_count == boardSz)return X_WIN;
            if(o_count == boardSz)return O_WIN;
        }
    }

    x_count = o_count = 0;
    /* check diagonal 1 */
    if(diag1CheckNotRequired == false)
    {
        for (int i = 0; i < boardSz; i++) {
            if(values[i][i] == x_val)x_count++;
            if(values[i][i] == o_val)o_count++;
            if(values[i][i] == 0)break;
        }
        if(x_count == boardSz)return X_WIN;
        if(o_count == boardSz)return O_WIN;
    }

    x_count = o_count = 0;
    /* check diagonal 2 */
    if( diag2CheckNotRequired == false)
    {
        for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {
            if(values[j][i] == x_val)x_count++;
            if(values[j][i] == o_val)o_count++;
            if(values[j][i] == 0)break;
        }
        if(x_count == boardSz)return X_WIN;
        if(o_count == boardSz)return O_WIN;
        x_count = o_count = 0;
    }

    if( allFilled == true)
    {
        for (int i = 0; i < boardSz; i++) {
            for (int j = 0; j < boardSz; j++) {
                if (values[i][j] == 0) {
                    allFilled = false;
                    break;
                }
            }

            if (allFilled == false) {
                break;
            }
        }
    }

    if (allFilled)
        return DRAW;

    return INPROGRESS;
}

Answer 14

9スロットの場合、次のアプローチはどうですか? a1、a2、a3 が行 1 を表し、a1、a4、a7 が列 1 を形成する 3x3 マトリックス (a1、a2....a9) の 9 つの整数変数を宣言します (アイデアはわかります)。Player-1 を示すには「1」を使用し、Player-2 を示すには「2」を使用します。

勝利の組み合わせは 8 通りあります: 勝利 1: a1+a2+a3 (どちらのプレイヤーが勝ったかによって、答えは 3 または 6 になります) 勝利 2: a4+a5+a6 勝利 3: a7+a8+a9 勝利 4 : a1+a4+a7 .... Win-7: a1+a5+a9 Win-8: a3+a5+a7

これで、プレーヤー 1 が a1 を超えた場合、3 つの変数 (Win-1、Win-4、Win-7) の合計を再評価する必要があることがわかりました。どちらが「勝つ-？」変数が 3 または 6 に達すると、最初にゲームに勝ちます。Win-1 変数が最初に 6 に達した場合、Player-2 が勝ちます。

このソリューションが簡単に拡張できないことは理解しています。

Answer 15

私はかつて科学プロジェクトの一環としてこのためのアルゴリズムを開発しました。

基本的に、ボードを再帰的に2x2の長方形の束に分割し、2x2の正方形で勝つためのさまざまな可能な組み合わせをテストします。

低速ですが、かなり線形のメモリ要件で、任意のサイズのボードで動作するという利点があります。

自分の実装を見つけられたらいいのに