Algorithme pour déterminer la fin d'une partie de Tic Tac Toe

Question

J'ai écrit un jeu de morpion en Java, et ma méthode actuelle pour déterminer la fin de la partie tient compte des scénarios possibles suivants pour la fin de la partie :

1. Le plateau est plein, et aucun gagnant n'a encore été déclaré : La partie est nulle.
2. Cross a gagné.
3. Le cercle a gagné.

Malheureusement, pour ce faire, il lit un ensemble prédéfini de ces scénarios dans un tableau. Ce n'est pas forcément mauvais, étant donné qu'il n'y a que 9 cases sur un plateau, et que le tableau est donc un peu petit, mais existe-t-il un meilleur moyen algorithmique de déterminer si la partie est terminée ? Déterminer si quelqu'un a gagné ou non est le cœur du problème, puisque vérifier si 9 cases sont pleines est trivial.

La méthode des tables pourrait être la solution, mais si ce n'est pas le cas, qu'est-ce qui l'est ? De même, que se passerait-il si le tableau n'était pas de taille n=9 ? Et s'il s'agissait d'un tableau beaucoup plus grand, par exemple n=16 , n=25 et ainsi de suite, ce qui fait que le nombre d'éléments placés consécutivement pour gagner est de x=4 , x=5 etc. Un algorithme général à utiliser pour tous les n = { 9, 16, 25, 36 ... } ?

Answer 1

Vous savez qu'un coup gagnant ne peut se produire qu'après que X ou O a effectué son dernier coup, donc vous ne pouvez rechercher que les lignes/colonnes avec des diag optionnels qui sont contenus dans ce coup pour limiter votre espace de recherche lorsque vous essayez de déterminer un plateau gagnant. De plus, comme il y a un nombre fixe de coups dans une partie de morpion, une fois que le dernier coup a été joué, si ce n'était pas un coup gagnant, la partie est nulle par défaut.

edit : ce code est pour un tableau n par n avec n dans une rangée pour gagner (tableau 3x3 exige 3 dans une rangée, etc)

edit : ajout d'un code pour vérifier l'anti diag, je n'ai pas pu trouver un moyen sans boucle pour déterminer si le point était sur l'anti diag, c'est pourquoi cette étape est manquante.

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

Vous pouvez utiliser un carré magique http://mathworld.wolfram.com/MagicSquare.html si une ligne, une colonne ou une diagonale fait 15, un joueur a gagné.

Answer 3

Que pensez-vous de ce pseudo-code :

Après qu'un joueur ait posé une pièce à la position (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

J'utiliserais un tableau de char [n,n], avec O,X et un espace pour le vide.

1. simple.
2. Une boucle.
3. Cinq variables simples : 4 entiers et un booléen.
4. S'adapte à toutes les tailles de n.
5. Vérifie uniquement la pièce en cours.
6. Pas de magie. :)

Answer 4

Ceci est similaire à Réponse d'Osama ALASSIRY mais il échange l'espace constant et le temps linéaire contre l'espace linéaire et le temps constant. C'est-à-dire qu'il n'y a pas de bouclage après l'initialisation.

Initialiser une paire (0,0) pour chaque ligne, chaque colonne, et les deux diagonales (diagonale & anti-diagonale). Ces paires représentent le cumul des (sum,sum) des pièces de la ligne, de la colonne ou de la diagonale correspondante, où

A piece from player A has value (1,0)
A piece from player B has value (0,1)

Lorsqu'un joueur place un pion, il met à jour la paire de lignes, la paire de colonnes et les paires de diagonales correspondantes (si elles sont sur les diagonales). Si une paire de lignes, de colonnes ou de diagonales nouvellement mise à jour est égale à l'un des éléments suivants (n,0) o (0,n) alors soit A ou B a gagné, respectivement.

Analyse asymptotique :

O(1) time (per move)
O(n) space (overall)

Pour l'utilisation de la mémoire, vous utilisez 4*(n+1) entiers.

two\_elements\*n\_rows + two\_elements\*n\_columns +
two\_elements\*two\_diagonals = 4\*n + 4 integers = 4(n+1) integers

Exercice : Pouvez-vous voir comment tester un match nul en O(1) temps par coup ? Si c'est le cas, vous pouvez terminer la partie plus tôt sur un match nul.

Answer 5

Si le conseil est n × n alors il y a n rangs, n colonnes, et 2 diagonales. Vérifiez chacun de ces éléments pour voir s'il y a des X ou des O pour trouver un gagnant.

S'il faut seulement x < n carrés consécutifs pour gagner, alors c'est un peu plus compliqué. La solution la plus évidente est de vérifier chaque x × x carré pour un gagnant. Voici un code qui le démontre.

(Je n'ai pas réellement testé cela *cough*, mais il a fait compiler du premier coup, bravo à moi !)

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