Tic Tac Toe algoritmo AI perfetto: più profondo nel passaggio "crea forchetta"

Question

Ho già letto molti argomenti di Tic Tac Toe su StackOverflow. E ho trovato la strategia su Wikipedia è adatto per il mio progetto di presentazione:

Un giocatore può giocare perfetto tic-tac-toe se scelgono la mossa con la massima priorità nella seguente tabella [3].

1) Win: Se ne hai due di fila, gioca il terzo per ottenere tre in una riga .

2) Blocco: se l'avversario ha due di fila, gioca il terzo per bloccare .

3) Forcella: crea un'opportunità in cui puoi vincere in due modi.

4) del blocco avversario Forcella:

Opzione 1: Creare due di fila per costringere l'avversario in difesa, come purché non dia luogo a loro creando una forchetta o vincere. Per esempio , se "X" ha un angolo, "O" ha il centro, e "X" ha anche l'angolo opposto , "O" non deve giocare un angolo per vincere. (Giocare un angolo in questo scenario crea un fork per "X" per vincere.)

Opzione 2: Se c'è una configurazione in cui l'avversario può sborsare, bloccare quella forcella.

5) Centro: gioca al centro.

6) Angolo opposto: se l'avversario è nell'angolo, giocare l'angolo opposto .

7) Angolo vuoto: gioca un angolo vuoto.

8) Lato vuoto: riproduce un lato vuoto.

Ho seguito questi passaggi e il computer non perde mai. Tuttavia, il modo in cui attacca non è perfetto. Perché non ho idea di come fare il passaggio 3. Ecco cosa faccio nel passaggio 3: scansiona ogni cella, controlla se metti il ​​token su quella cella crea una forchetta, poi mettila lì.

private void step3() // Create Fork. 
{ 
    int[] dummyField = (int[])field.Clone(); 
    // Try Level 1 Dummy 
    for (int i = 0; i < 9; i++) 
    { 
     if (dummyField[i] != 0) continue; 
     dummyField[i] = 2; 
     if (countFork(dummyField, 2) >= 2) 
     { 
      nextCell = i; 
      return; 
     } 
     dummyField[i] = 0; 
    } 

} 

Per favore, dammi qualche consiglio su questo passaggio.

EDIT1: Il conteggio forcella conta quante forchette ha quel computer (i token del computer sono 2, i token del giocatore è 1, perché anch'io ho usato quel metodo per il passo 4, quindi c'è un parametro per il token nella funzione countFork).

EDIT2: Il motivo per cui dico che non è perfetto è questo (la CPU va prima, e le sue celle sono blu, le celle umane sono rosse). Come potete vedere, se inserisco la cella in alto, vince il computer. Ma se inserisco la cella di destra, è un pareggio, anche se il computer può ancora vincere.

EDIT3: Non so perché, ma ho commentato il passaggio 3 e il computer suona ... perfettamente! Sono davvero sorpreso! Ecco la mia funzione countFork (ho bisogno di questo codice in Alice, che non supporta array di 2-dimensione, per cui uso getNumberFromXY convertire matrice 2-dimensione nel 1-dimensione):

private int countFork(int[] field, int token) 
{ 
    int result = 0; 

    // Vertical 
    int cpuTokenCount; 
    int spareCell; 
    for (int x = 0; x < 3; x++) 
    { 
     cpuTokenCount = 0; 
     spareCell = -1; 
     for (int y = 0; y < 3; y++) 
     { 
      if (field[getNumberFromXY(x, y)] == token) 
       cpuTokenCount++; 
      else if (field[getNumberFromXY(x, y)] == 0) 
       spareCell = getNumberFromXY(x, y); 
     } 
     if (cpuTokenCount == 2 && spareCell != -1) result++; 
    } 

    // Horizontal 
    for (int y = 0; y < 3; y++) 
    { 
     cpuTokenCount = 0; 
     spareCell = -1; 
     for (int x = 0; x < 3; x++) 
     { 
      if (field[getNumberFromXY(x, y)] == token) 
       cpuTokenCount++; 
      else if (field[getNumberFromXY(x, y)] == 0) 
       spareCell = getNumberFromXY(x, y); 
     } 
     if (cpuTokenCount == 2 && spareCell != -1) result++; 
    } 

    // Top-Left To Lower-Right Diagonal 
    cpuTokenCount = 0; 
    spareCell = -1; 
    for (int i = 0; i < 3; i++) 
    { 
     if (field[getNumberFromXY(i, i)] == token) 
      cpuTokenCount++; 
     else if (field[getNumberFromXY(i, i)] == 0) 
      spareCell = getNumberFromXY(i, i); 
    } 
    if (cpuTokenCount == 2 && spareCell != -1) result++; 

    // Top-Right To Lower-Left Diagonal 
    cpuTokenCount = 0; 
    spareCell = -1; 
    for (int i = 0; i < 3; i++) 
    { 
     if (field[getNumberFromXY(2 - i, i)] == token) 
      cpuTokenCount++; 
     else if (field[getNumberFromXY(2 - i, i)] == 0) 
      spareCell = getNumberFromXY(2 - i, i); 
    } 
    if (cpuTokenCount == 2 && spareCell != -1) result++; 

    return result; 
} 

EDIT4: FISSATO il bug in base a soandos e aggiornato il codice in EDIT 3, ora funziona perfettamente!

Answer 1

Non sono sicuro che sia il modo più elegante per farlo, ma ecco un modo in due per guardare le forcelle.

Se il computer non può vincere il prossimo turno, e non è il primo o il secondo turno, una forca potrebbe essere possibile (questo non si occupa della creazione del setup di una forcella, ma solo di una forchetta).

Per ciascuna delle celle vuote, compilarlo, quindi eseguire la funzione di passaggio 1 (vede se ce ne sono due di seguito). Se trova due posti, congratulazioni, hai una forchetta. Se no, non lo fai.