Algorithmus für die Bestimmung von Tic Tac Toe Game Over

können Sie ein Magisches Quadrat http://mathworld.wolfram.com/MagicSquare.htmlwenn jede Zeile, Spalte oder diag fügt bis zu 15, dann hat der Spieler gewonnen.

InformationsquelleAutor der Antwort adk

Wie wäre es mit diesem pseudocode:

Nachdem ein Spieler legt ein Stück an der 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

Ich würde verwenden Sie ein array von char [n,n], mit O -, X-und Raum für leere.

1. einfach.
2. Einer Schleife.
3. Fünf einfache Variablen: 4 Ganzzahlen und eine boolean.
4. Skalen für jede Größe von n.
5. Prüft nur die aktuellen Stück.
6. Keine Magie. 🙂

InformationsquelleAutor der Antwort Osama Al-Maadeed

Ich schrieb dies für meine C-Programmierung Klasse.

Ich bin Entsendung es, weil keines der anderen Beispiele, die hier gemacht werden, mit einer Größe rechteckigen Gitter, und eine beliebige Anzahl N-in-einer-Reihe aufeinanderfolgender Markierungen, um zu gewinnen.

Finden Sie mein Algorithmus, wie es ist, in der checkWinner() Funktion. Es spielt keine Magie benutzen, zahlen oder etwas Phantasie, um zu prüfen, ob ein Sieger, der es verwendet einfach vier for-Schleifen - Der code ist gut kommentiert, so dass ich ' ll lassen Sie es für sich selbst sprechen, denke ich.

//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.

InformationsquelleAutor der Antwort mattR

Ich weiß nicht, Java auch, aber ich weiß, dass C, also versuchte ich adk ' s magic square Idee (zusammen mit Hardwareguy such-Einschränkung).

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

Kompiliert und die tests auch.

% gcc -o tic-tac-toe tic-tac-toe.c 
% ./tic-tac-toe 
| | 
---+---+--- 
| | 
---+---+--- 
| | 
Geben Sie bewegt sich als "" (keine Anführungszeichen, null, indiziert) 
X verschieben: 1 2 
| | 
---+---+--- 
| | X 
---+---+--- 
| | 
O s verschieben: 1 2 
illegal verschieben (bereits getroffen), versuchen Sie es erneut 
O zu bewegen: 3 3 
illegal verschieben (aus dem board), versuchen Sie es erneut 
O Umzug: 2 2 
| | 
---+---+--- 
| | X 
---+---+--- 
| | O 
X bewegen: 1 0 
| | 
---+---+--- 
X | | X 
---+---+--- 
| | O 
O zu bewegen: 1 1 
| | 
---+---+--- 
X | O | X 
---+---+--- 
| | O 
X bewegen: 0 0 
X | | 
---+---+--- 
X | O | X 
---+---+--- 
| | O 
O Umzug: 2 0 
X | | 
---+---+--- 
X | O | X 
---+---+--- 
O | | O 
X bewegen: 2 1 
X | | 
---+---+--- 
X | O | X 
---+---+--- 
O | X | O 
O zu bewegen: 0 2 
X | | O 
---+---+--- 
X | O | X 
---+---+--- 
O | X | O 
tic-tac-toe! O gewinnt! 
% ./tic-tac-toe 
| | 
---+---+--- 
| | 
---+---+--- 
| | 
Geben Sie bewegt sich als "" (keine Anführungszeichen, null, indiziert) 
X bewegen: 0 0 
X | | 
---+---+--- 
| | 
---+---+--- 
| | 
O zu bewegen: 0 1 
X | O | 
---+---+--- 
| | 
---+---+--- 
| | 
X bewegen: 0 2 
X | O | X 
---+---+--- 
| | 
---+---+--- 
| | 
O zu bewegen: 1 0 
X | O | X 
---+---+--- 
O | | 
---+---+--- 
| | 
X bewegen: 1 1 
X | O | X 
---+---+--- 
O | X | 
---+---+--- 
| | 
O Umzug: 2 0 
X | O | X 
---+---+--- 
O | X | 
---+---+--- 
O | | 
X bewegen: 2 1 
X | O | X 
---+---+--- 
O | X | 
---+---+--- 
O | X | 
O Umzug: 2 2 
X | O | X 
---+---+--- 
O | X | 
---+---+--- 
O | X | O 
X verschieben: 1 2 
X | O | X 
---+---+--- 
O | X | X 
---+---+--- 
O | X | O 
Patt... niemand gewinnt :( 
% 

Das war lustig, danke!

Eigentlich, denken Sie daran, Sie brauchen nicht, ein Magisches Quadrat, nur eine Anzahl für jede Zeile/Spalte/Diagonale. Dies ist ein wenig leichter als die Verallgemeinerung eines magischen Quadrates zu n × n Matrizen, da Sie gerade brauchen, um count zu n.

InformationsquelleAutor der Antwort rampion

nicht-Schleife Weg, um festzustellen, ob der Punkt wurde auf die anti-diag:

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

InformationsquelleAutor der Antwort Jeff

Ich bin spät dran, die party, aber ich wollte darauf hinweisen, ein Vorteil, den, die ich fand, um mit einem magic squarenämlich, dass es verwendet werden kann, um einen Verweis auf das Quadrat dazu führen würde, dass der Gewinn oder der Verlust auf den nächsten Zug, anstatt nur verwendet, um zu berechnen, Wann ein Spiel vorbei ist.

Nehmen Sie dieses Magische Quadrat:

4 9 2
3 5 7
8 1 6

Richten Sie zuerst ein scores array wird erhöht, jedes mal ein Umzug. Sehen diese Antwort für details. Nun, wenn wir illegal spielen Sie X zweimal in Folge bei [0,0] und [0,1], dann ist die scores array sieht wie folgt aus:

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

Und das board sieht wie folgt aus:

X . .
X . .
. . .

Dann müssen wir alle tun, um zu bekommen eine Referenz auf dem Platz um zu gewinnen/block auf:

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

In der Realität, die Umsetzung erfordert einige zusätzliche tricks, wie Umgang mit numerierten Tasten (in JavaScript), aber ich fand es ziemlich einfach und genossen die Freizeit-math.

InformationsquelleAutor der Antwort gwg

Andere Möglichkeit: erstellen Sie Ihre Tabelle mit code. Bis auf Symmetrie gibt es nur drei Möglichkeiten zu gewinnen: die edge-Reihe, mittlere Reihe, oder Diagonale. Nehmen Sie diese drei, und drehen Sie Sie um jede mögliche Weise:

def spin(g): return set([g, turn(g), turn(turn(g)), turn(turn(turn(g)))])
def turn(g): return tuple(tuple(g[y][x] for y in (0,1,2)) for x in (2,1,0))

X,s = 'X.'
XXX = X, X, X
sss = s, s, s

ways_to_win = (  spin((XXX, sss, sss))
               | spin((sss, XXX, sss))
               | spin(((X,s,s),
                       (s,X,s),
                       (s,s,X))))

Diese Symmetrien haben kann, mehr verwendet in der Spiele-spielen-code: wenn du ein board hast du schon gesehen, eine gedrehte version, können Sie einfach den zwischengespeicherten Wert oder den besten Zug aus, dass man (und unrotate es wieder). Dies ist in der Regel viel schneller als die Bewertung der Spiel-Teilbaum.

(Spiegeln Links und rechts können helfen, die gleiche Art und Weise; es war nicht nötig, weil hier die Menge der Rotationen der gewinnenden Muster ist Spiegel-symmetrisch.)

InformationsquelleAutor der Antwort Darius Bacon

Wie wäre es mit einem folgenden Ansatz für die 9 slots? Erklären 9 integer-Variablen für eine 3x3 matrix (a1,a2,....a9), wo a1,a2,a3 darstellen, Zeile-1 und a1,a4,a7 würde column-1 (Sie erhalten die Idee). Verwenden Sie '1', um anzugeben, Spieler-1 und '2', um anzugeben, Spieler-2.

Gibt es 8 mögliche Gewinn Kombinationen:
Gewinnen-1: a1+a2+a3 (Antwort könnte sein, 3 oder 6, basierend auf dem Spieler gewonnen)
Win-2: a4+a5+a6
Gewinnen-3: a7+a8+a9
Gewinnen-4: a1+a4+a7
....
Win-7: a1+a5+a9
Win-8: a3+a5+a7

Nun wissen wir, dass wenn der Spieler durchquert man a1 dann müssen wir uns beleben, die Summe von 3 Variablen: Win-1, Win-4 und Win-7. Welche " Win-?' Variablen erreicht 3-oder 6-erste gewinnt das Spiel. Wenn die Win-1 variable 6 erreicht zuerst, dann Spieler 2 gewinnt.

Verstehe ich, dass diese Lösung nicht skalierbar leicht.

InformationsquelleAutor der Antwort user3071398

Dies ist eine wirklich einfache Möglichkeit zu überprüfen.

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

}

InformationsquelleAutor der Antwort lusion

Entwickelte ich einen Algorithmus für diese als Teil eines wissenschaftlichen Projekts einmal.

Dass Sie im Grunde rekursiv aufteilen der Platte in einer Reihe von überlappenden 2x2 rects, die Prüfung der verschiedenen möglichen Kombinationen für den Gewinn auf ein 2x2-Quadrat.

Es ist langsam, aber es hat den Vorteil der Arbeit auf jede Größe der Platte mit einem ziemlich linearen Speicherbedarf.

Ich wünschte, ich könnte meine Implementierung

InformationsquelleAutor der Antwort bgw