Quale algoritmo per un gioco tic-tac-toe posso usare per determinare la “mossa migliore” per l’intelligenza artificiale?

In un’implementazione tic-tac-toe suppongo che la parte più impegnativa sia determinare la mossa migliore da giocare con la macchina.

Quali sono gli algoritmi che possono essere perseguiti? Sto esaminando le implementazioni da semplici a complesse. Come farei per affrontare questa parte del problema?

    La strategia di Wikipedia per giocare a un gioco perfetto (vincere o pareggiare ogni volta) sembra uno pseudo-codice semplice:

    Citazione da Wikipedia (strategia Tic Tac Toe #)

    Un giocatore può giocare una partita perfetta di Tic-tac-toe (per vincere o, almeno, pareggiare) se sceglie la prima mossa disponibile dalla seguente lista, ogni turno, come usato nel tic-tac-toe di Newell e Simon del 1972 programma. [6]

    1. Vittoria: se ne hai due di fila, gioca la terza per ottenere tre di fila.

    2. Blocco: se l’avversario ha due di fila, gioca il terzo per bloccarli.

    3. Fork: crea un’opportunità in cui puoi vincere in due modi.

    4. Blocco dell’avversario:

      Opzione 1: Crea due di fila per costringere l’avversario a difendere, a condizione che non crei una forchetta o una vittoria. Ad 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, blocca quella forchetta.

    5. Centro: gioca al centro.

    6. Angolo opposto: se l’avversario è nell’angolo, gioca nell’angolo opposto.

    7. Angolo vuoto: gioca un angolo vuoto.

    8. Lato vuoto: gioca un lato vuoto.

    Riconoscere come si presenta una situazione “a fork” potrebbe essere fatto in un modo a forza bruta come suggerito.

    Nota: un avversario “perfetto” è un bel esercizio ma alla fine non vale la pena “giocare” contro. Potresti, tuttavia, modificare le priorità sopra riportate per conferire debolezze caratteristiche alle personalità avversarie.

    Quello che ti serve (per il tris o un gioco molto più difficile come gli scacchi) è l’ algoritmo minimax , o la sua variante leggermente più complicata, la potatura alfa-beta . Tuttavia, l’ordinario ingenuo minimax andrà bene per un gioco con uno spazio di ricerca tanto piccolo come quello di tic-tac-toe.

    In poche parole, quello che vuoi fare non è cercare la mossa che ha il miglior risultato ansible per te, ma piuttosto la mossa in cui il peggior risultato ansible è il migliore ansible. Se ritieni che il tuo avversario stia giocando in modo ottimale, devi assumere che prenderanno la mossa peggiore per te, e quindi devi prendere la mossa che minimizza il loro guadagno massimo.

    Il metodo della forza bruta per generare ogni singola scheda ansible e il suo calcolo basato sulle tabs che successivamente produce più in basso sull’albero non richiede molta memoria, specialmente quando si riconosce che le rotazioni della scheda a 90 gradi sono ridondanti, come i capovolgimenti sulla verticale, asse orizzontale e diagonale.

    Una volta arrivato a quel punto, c’è qualcosa come meno di 1k di dati in un albero grafico per descrivere il risultato, e quindi la mossa migliore per il computer.

    -Adamo

    Un tipico algo per tic-tac-toe dovrebbe assomigliare a questo:

    Tavola: un vettore di nove elementi che rappresenta il tabellone. Memorizziamo 2 (che indica Blank), 3 (che indica X) o 5 (che indica O). Turno: un numero intero che indica quale movimento del gioco sta per essere giocato. La prima mossa sarà indicata da 1, l’ultima da 9.

    L’algoritmo

    L’algoritmo principale utilizza tre funzioni.

    Rendi2: ritorna 5 se il quadrato centrale del tabellone è vuoto, cioè se il tabellone [5] = 2. Altrimenti, questa funzione restituisce qualsiasi quadrato non ad angolo (2,4,6 o 8).

    Posswin (p): restituisce 0 se il giocatore p non può vincere alla sua prossima mossa; altrimenti restituisce il numero di quadrato che costituisce una mossa vincente. Questa funzione consentirà al programma di vincere e bloccare gli avversari. Questa funzione opera controllando ciascuna delle righe, colonne e diagonali. Moltiplicando i valori del quadrato per un’intera riga (o colonna o diagonale), è ansible verificare la ansible situazione di vittoria. Se il prodotto ha 18 (3 x 3 x 2), allora X può vincere. Se il prodotto è 50 (5 x 5 x 2), allora O può vincere. Se viene trovata una riga vincente (colonna o diagonale), il quadrato vuoto in esso può essere determinato e il numero di quel quadrato viene restituito da questa funzione.

    Vai (n): fa una mossa in piazza n. questa procedura imposta board [n] su 3 se Turn è dispari, o 5 se Turn è pari. Aumenta anche il giro di uno.

    L’algoritmo ha una strategia integrata per ogni mossa. Rende la mossa numerata dispari se gioca X, la mossa con numero pari se gioca O.

    Turn =1 Go(1) (upper left corner). Turn =2 If Board[5] is blank, Go(5), else Go(1). Turn =3 If Board[9] is blank, Go(9), else Go(3). Turn =4 If Posswin(X) is not 0, then Go(Posswin(X)) ie [ block opponent's win], else Go(Make2). Turn =5 if Posswin(X) is not 0 then Go(Posswin(X)) [ie win], else if Posswin(O) is not 0, then Go(Posswin(O)) [ie block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ]. Turn =6 If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2). Turn =7 If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank. Turn =8 if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank. Turn =9 Same as Turn=7. 

    L’ho usato Fammi sapere come ti senti.

    Dal momento che hai a che fare solo con una matrice 3×3 di possibili posizioni, sarebbe piuttosto semplice scrivere una ricerca attraverso tutte le possibilità senza imporre il tuo potere di calcolo. Per ogni spazio aperto, calcola attraverso tutti i possibili risultati dopo quello che segna quello spazio (ricorsivamente, direi), quindi usa la mossa con le maggiori possibilità di vincita.

    Ottimizzare questo sarebbe uno spreco di sforzi, davvero. Anche se alcuni facili potrebbero essere:

    • Controlla prima possibili vittorie per l’altra squadra, blocca il primo che trovi (se ci sono almeno 2 giochi in ogni caso).
    • Prendi sempre il centro se è aperto (e la regola precedente non ha candidati).
    • Prendi gli angoli davanti ai lati (di nuovo, se le regole precedenti sono vuote)

    Puoi fare in modo che l’intelligenza artificiale giochi da solo in alcuni giochi di esempio da cui imparare. Utilizzare un algoritmo di apprendimento supervisionato, per aiutarlo.

    Un tentativo senza usare un campo di gioco.

    1. vincere (il tuo doppio)
    2. in caso contrario, non perdere (il doppio dell’avversario)
    3. se no, hai già una forchetta (avere una doppia doppia)
    4. in caso contrario, se l’avversario ha una forchetta
      1. cerca nei punti di blocco il ansible doppio e fork (ultima vincita)
      2. se non cerca forchette nei punti di blocco (che dà all’avversario le possibilità più perdenti)
      3. se non solo punti di blocco (da non perdere)
    5. se non la ricerca di doppio e fork (ultima vittoria)
    6. se non cerchi solo forchette che danno all’avversario le possibilità più perdenti
    7. se non cercare solo un doppio
    8. se non vicolo cieco, bind, a caso.
    9. se no (significa la tua prima mossa)
      1. se è la prima mossa del gioco;
        1. dare all’avversario la possibilità più perdente (l’algoritmo si traduce in soli angoli che danno 7 possibilità di perdere punti all’avversario)
        2. o per rompere la noia solo a caso.
      2. se è la seconda mossa del gioco;
        1. trova solo i punti non perdenti (dà un po ‘più di opzioni)
        2. o trova i punti in questa lista che ha la migliore possibilità di vincere (può essere noioso, perché si traduce solo in tutti gli angoli o angoli adiacenti o al centro)

    Nota: quando hai il doppio e le forchette, controlla se il tuo doppio dà all’opponente un doppio. Se lo fa, controlla se il tuo nuovo punto obbligatorio è incluso nella tua lista delle forche.

    Classifica ciascuno dei quadrati con punteggi numerici. Se viene preso un quadrato, passare alla scelta successiva (ordinata in ordine decrescente per grado). Dovrai scegliere una strategia (ce ne sono due principali per il primo e il terzo (credo) per il secondo). Tecnicamente, puoi semplicemente programmare tutte le strategie e poi sceglierne una a caso. Ciò renderebbe un avversario meno prevedibile.

    Questa risposta presuppone che tu comprenda l’implementazione dell’algoritmo perfetto per P1 e discuti su come ottenere una vittoria in condizioni contro i normali giocatori umani, che faranno alcuni errori più comunemente di altri.

    Il gioco ovviamente dovrebbe terminare in parità se entrambi i giocatori giocano in modo ottimale. A livello umano, P1 che gioca in un angolo produce vittorie molto più spesso. Per qualsiasi motivo psicologico, P2 è esagerato nel pensare che giocare al centro non sia così importante, il che è sfortunato per loro, dal momento che è l’unica risposta che non crea un gioco vincente per P1.

    Se P2 blocca correttamente al centro, P1 dovrebbe giocare l’angolo opposto, perché ancora una volta, per qualsiasi motivo psicologico, P2 preferirà la simmetria di giocare un angolo, che di nuovo produce una tavola perdente per loro.

    Per ogni mossa che P1 può fare per la mossa iniziale, vi è una mossa P2 che può creare una vittoria per P1 se entrambi i giocatori giocano in modo ottimale successivamente. In questo senso P1 può giocare ovunque. Le mosse di bordo sono più deboli nel senso che la più grande frazione di possibili risposte a questa mossa produce un pareggio, ma ci sono ancora delle risposte che creeranno una vittoria per P1.

    Empiricamente (più precisamente, aneddoticamente) le migliori mosse iniziali di P1 sembrano essere il primo angolo, il secondo centro e l’ultimo spigolo.

    La prossima sfida che puoi aggiungere, di persona o tramite una GUI, non è quella di visualizzare la scheda. Un umano può sicuramente ricordare tutto lo stato, ma la sfida aggiunta porta a una preferenza per le tabs simmetriche, che richiedono meno sforzi per ricordare, portando all’errore che ho delineato nel primo ramo.

    Mi diverto molto alle feste, lo so.

    Ecco una soluzione che considera tutte le mosse possibili e le conseguenze di ciascuna mossa per determinare la mossa migliore ansible.

    avremo bisogno di una striatura di dati che rappresenti il ​​tabellone. Rappresenteremo la tavola con una matrice bidimensionale. La matrice esterna rappresenta l’intera scheda e una matrice interna rappresenta una riga. Ecco lo stato di una lavagna vuota.

     _gameBoard: [ [“”, “”, “”], [“”, “”, “”], [“”, “”, “”] ] 

    Compileremo la tavola con i caratteri “x” e “o”.

    Successivamente avremo bisogno di una funzione che possa controllare il risultato. La funzione controllerà una serie di caratteri. Qualunque sia lo stato del tabellone, il risultato è una delle 4 opzioni: Incomplete, giocatore X vinto, giocatore O vinto o pareggio. La funzione dovrebbe restituire quale è lo stato della scheda.

     const SYMBOLS = { x:'X', o:'O' } const RESULT = { incomplete: 0, playerXWon: SYMBOLS.x, playerOWon: SYMBOLS.o, tie: 3 } function getResult(board){ // returns an object with the result let result = RESULT.incomplete if (moveCount(board)<5){ {result} } function succession (line){ return (line === symbol.repeat(3)) } let line //first we check row, then column, then diagonal for (var i = 0 ; i<3 ; i++){ line = board[i].join('') if(succession(line)){ result = symbol; return {result}; } } for (var j=0 ; j<3; j++){ let column = [board[0][j],board[1][j],board[2][j]] line = column.join('') if(succession(line)){ result = symbol return {result}; } } let diag1 = [board[0][0],board[1][1],board[2][2]] line = diag1.join('') if(succession(line)){ result = symbol return {result}; } let diag2 = [board[0][2],board[1][1],board[2][0]] line = diag2.join('') if(succession(line)){ result = symbol return {result}; } //Check for tie if (moveCount(board)==9){ result=RESULT.tie return {result} } return {result} }