È possibile verificare la condizione vincente di un gioco di TicTacToe usando jGraphT?

Question

Ho trovato questa soluzione di lavoro:

private int[] winningPatterns = { 0b111000000, 0b000111000, 0b000000111, // rows 
     0b100100100, 0b010010010, 0b001001001, // cols 
     0b100010001, 0b001010100 // diagonals 
}; 

/** Returns true if thePlayer wins */ 
private boolean hasWon(int thePlayer) { 
    int pattern = 0b000000000; // 9-bit pattern for the 9 cells 
    for (int row = 0; row < 3; ++row) { 
     for (int col = 0; col < 3; ++col) { 
      if (cells[row][col].content == thePlayer) { 
       pattern |= (1 << (row * 3 + col)); 
      } 
     } 
    } 
    for (int winningPattern : winningPatterns) { 
     if ((pattern & winningPattern) == winningPattern) 
      return true; 
    } 
    return false; 
} 

ma vorrei sapere se esiste una soluzione più elegante utilizzando grafico logica.

Aggiornamento: Sto anche sfruttando le mie conoscenze su varianti diverse e più grandi della scheda 3x3 e credo che questo approccio non si estenda bene.

Ad esempio: https://en.wikipedia.org/wiki/Teeko

Answer 1

per un 25 da 25 della scheda di I che il metodo che hai è fattibile, ma alcuni modi per migliorarlo sono i seguenti.

1. Creare il modello mentre l'utente sta aggiungendo i pezzi, perché allora sarà solo il tempo necessario per passare attraverso la matrice winningPatterns.

2. Per migliorare la seconda parte, è possibile provare a memorizzarla in modo più efficace. Memorizza i pattern vincenti in modo da poterne controllare più di uno allo stesso tempo. Ad esempio se la prima posizione è 0, allora è possibile rimuovere 3 possibilità dai modelli vincenti invece di una sola (111 000 000, 100 100 100, 100 010 001).

3. È possibile migliorare il caso medio controllando la posizione che ha la più alta probabilità che sia corretta. Ad esempio, ci sono 4 modi in cui il giocatore avrebbe potuto vincere piazzando il pezzo al centro, quindi controlla l'ordine.

4. Se si memorizzano le posizioni dei giocatori in un array separato, dove p1Tiles e p2Tiles. Quindi ciò potrebbe aumentare di molto il caso medio, perché la maggior parte di essi cronometra il tabellone sarà abbastanza vuoto. Sarà pieno per 1 istanza di questo gioco prima che la scacchiera venga resettata.

5. In realtà non è necessario controllare tutti i pezzi del giocatore che ti ha vinto, ma solo per verificare se il pezzo che l'utente attuale pone fa una vittoria. Quindi con questo metodo dovresti solo controllare il caso peggiore in altri 12 punti, anche se la scheda ha una dimensione di 99..999 per 99..999. (12 a causa di tutti gli slot attorno allo slot attuale PLUS se ci sono due dello stesso colore l'uno accanto all'altro quindi dovresti guardare il seguente slot)