Determinazione della condizione vincente per Tic-Tac-Toe [chiuso]

Il puro fatto che non capisci questa funzione dovrebbe essere un grande segnale di avvertimento per non implementare il tuo test vincente Tic-Tac-Toe in modo simile. Se lo fai, probabilmente non capirai più il tuo codice in poche settimane.

Usa invece un array o vettore bidimensionale e alcuni loop per verificare le condizioni vincenti. E non pensare troppo alla velocità o allo spazio di memoria a patto che non si verifichino colli di bottiglia significativi e misurabili.

L'uso dei bit per rappresentare una scheda Tic-Tac-Toe è perfettamente soddisfacente ed è tanto facile e manutenibile quanto l'uso di un array bidimensionale. Dal momento che ci sono solo 8 possibilità per vincere la condizione, puoi semplicemente controllare il tabellone contro ogni caso.

1 0 0       0 1 0      0 0 1     1 1 1    0 0 0
1 0 0       0 1 0      0 0 1     0 0 0    1 1 1
1 0 0       0 1 0      0 0 1     0 0 0    0 0 0

0 0 0       1 0 0      0 0 1
0 0 0       0 1 0      0 1 0
1 1 1       0 0 1      1 0 0

Per mantenere la pulizia del codice, prova ad astrarre l'implementazione della scheda dalla logica del gioco. È più facile cambiare l'implementazione della scheda in seguito se non ti piace la rappresentazione del bitboard.

class Board
{
    private:
        uint32_t board;

    public:
        Board() { board = 0; }

        /* Check if there is any of our piece
           placed in this (x, y) location */
        bool Check(int x, int y) {
            return (board & (1 << y * 3 + x)) > 0;
        }

        /* Make a move in this (x, y) location */
        void Move(int x, int y) {
            board = board | (1 << y * 3 + x);
        }

        /* Check if we have won */
        bool IsWin()
        {
            return (board & 292) == 292 || (board & 146) == 146 ||
                   (board & 73) == 73 || (board & 448) == 448 ||
                   (board & 56) == 56 || (board & 7) == 7 ||
                   (board & 273) == 273 || (board & 84) == 84;
        }
};

Mantieni due schede per il giocatore 1 e il giocatore2.

Board player1;
Board player2;

Controlla se (x, y) la posizione non è occupata

if (!player1.Check(x, y) && !player2.Check(x, y)) {
    // unoccupied slot
}

Verifica se il giocatore 1 ha vinto

if (player1.isWin()) {
    // player 1 has won.
}

Pensalo come un numero binario in cui tutti quelli sono i tuoi pezzi. Per semplificare la mia spiegazione, prenderò in considerazione solo una riga di 8. Il resto funziona in modo simile.

Considera un caso vincente di quattro in una riga: 11110000 . board && (board >> 1) ti dà 1110000 , che è tutti quelli con uno immediatamente adiacente a sinistra. Ripetendo con y & (y >> 2) esegue lo stesso controllo, ma per due a sinistra. La combinazione dei due produce un valore diverso da zero quando ne ottieni quattro di fila.

Gli altri offset fanno la stessa cosa, ma si avviano alla riga successiva anziché controllare immediatamente i quadrati adiacenti. 8 avvolge immediatamente sotto, 7 avvolge sotto ma uno a sinistra e 9 avvolge sotto ma uno a destra.

Questo è possibile grazie ai poteri di due persone coinvolte. In una griglia 3x3 non puoi fare qualcosa di simile. Puoi usarlo per controllare due di fila o quattro di fila, ma non tre.

Detto questo, anche se il bit-shifting ha funzionato per tic-tac-toe, non dovresti usarlo. Connect four ha 4.531,985,219,092 possibili giochi , quindi ha senso ottimizzare questa funzione il più possibile, per essere in grado di calcolare un albero più profondo in un tempo ragionevole, anche se ciò significa sacrificare una certa leggibilità. Tic-tac-toe ha solo 255,168 possibili giochi , il che significa che puoi ricalcolare ogni combinazione su ogni mossa in modo ingenuo modo, e hanno ancora tempo da perdere. In questi casi, la leggibilità dovrebbe essere fondamentale.

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

—Turing award winner Tony Hoare

Il motivo per cui non si ottimizza quando non è necessario è che i bug non sono più evidenti. Ad esempio, la seguente tabella è erroneamente riportata come una vittoria:

10000001
00000010
00000100
00000000
00000000
00000000
00000000
00000000

Dimentica che connetti 4 funzioni. Oltre a essere inutilmente criptico, il controllo per una vittoria in Connect 4 è più complesso rispetto a tac-tac-toe.

In tic-tac-toe ci sono otto righe da controllare: tre righe, tre colonne e due diagonali. La prima cosa che suggerirò è usare un array monodimensionale per la scheda, quindi gli indici di array sono i seguenti ...

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

Il motivo dell'utilizzo di un array bidimensionale sarebbe rendere più facile l'identificazione delle posizioni e più facile il loro loop su di esse. In questo caso, sostengo che poiché la scheda è così piccola, è in realtà più semplice evitare il problema delle due dimensioni. Eviterò anche i loop, almeno per un primo tentativo, poiché la scala del problema è abbastanza piccola da permetterlo. Quindi ...

bool line_is_full (Board* p_board, char p_player, int p1, int p2, int p3)
{
  return (   (p_board [p1] == p_player)
          && (p_board [p2] == p_player)
          && (p_board [p3] == p_player));
}

bool board_has_win (Board* p_board, char p_player)
{
  return (   line_is_full (p_board, p_player, 0, 1, 2)
          || line_is_full (p_board, p_player, 3, 4, 5)
          || line_is_full (p_board, p_player, 6, 7, 8)

          || line_is_full (p_board, p_player, 0, 3, 6)
          || line_is_full (p_board, p_player, 1, 4, 7)
          || line_is_full (p_board, p_player, 2, 5, 8)

          || line_is_full (p_board, p_player, 0, 4, 8)

          || line_is_full (p_board, p_player, 2, 4, 6));
}

Solo il controllo della vincita di un giocatore è valido perché l'unico giocatore che devi controllare è il giocatore che ha appena effettuato una mossa. Non sto nemmeno controllando un pareggio qui - ti basta contare quante mosse sono state fatte per gestirlo.

Cose ovvie che potrebbero essere migliorate ...

1. Le righe vuote in board_has_win servono per enfatizzare gruppi di casi simili. Potresti avere un loop sulle tre righe e un loop sulle tre colonne.

2. In alternativa, board_has_win è un ciclo "non eseguito" su tutte le otto righe. Ci sono diversi modi in cui questo potrebbe essere espresso usando un ciclo. Probabilmente il più sensato è avere una tabella di dati (dando i tre numeri di cella per ciascuna delle otto linee), in modo che tu possa ricorrere direttamente alle otto righe.

3. line_is_full potrebbe ovviamente essere riscritto come un ciclo sulle tre celle se solo quelle celle fossero passate come array.

4. In alternativa, per ogni riga (dato il modo in cui li ho specificati), (p2-p1) == (p3-p2) - c'è una distanza costante tra le celle. Anche (p1+p3)/2 == p2 - la posizione della cella centrale è la media delle due celle terminali. Ciò significa che vengono fornite due celle (a patto di sapere quali due) è possibile determinare la prima e la distanza di passo e il ciclo su tutte e tre.

Personalmente ignorerei i punti 3 e 4: avere un ciclo piuttosto che tre casi non vale davvero nemmeno una piccola quantità di complessità extra. Probabilmente mi concentrerei sul punto 2 - quella tabella di numeri di cella per ogni riga potrebbe avere altri usi nel programma.

Ecco un suggerimento che penso di aver visto per la prima volta nei vecchi tempi in cui le riviste di computer stampavano annunci in BASIC. Ciascuna delle linee ha tre celle. Cosa succede se assegni O il valore 1 e X il valore 4 (e zero per vuoto)? Considera il totale dei valori per le tre celle in una riga: ecco una tabella ...

 0 .... All three cells empty
 1 .... One O, two empty cells
 2 .... Two Os, one empty cell
 3 .... Three Os - O wins

 4 .... One X, two empty cells
 5 .... One X, one O, one empty cell
 6 .... One X, two Os
 7 .... Impossible

 8 .... Two Xs, one empty cell
 9 .... Two Xs, one O
10 .... Impossible
11 .... Impossible

12 .... Three Xs - X wins
13+ ... Impossible

Questo è un tipo di tabella hash del caso speciale. Questo è utile non solo per individuare una vittoria ma anche per un'IA molto semplice.