Gioco da tavolo Intelligenza artificiale: l'algoritmo Minimax: 8 passaggi

2024 Autore: John Day | [email protected]. Ultima modifica: 2024-01-30 10:02

Ti sei mai chiesto come sono fatti i computer contro cui giochi a scacchi oa dama? Bene, non guardare oltre questo Instructable perché ti mostrerà come creare un'intelligenza artificiale (AI) semplice ma efficace usando l'algoritmo Minimax! Usando l'algoritmo Minimax, l'intelligenza artificiale fa mosse ben pianificate e ponderate (o almeno imita un processo di pensiero). Ora, potrei darti il codice per l'intelligenza artificiale che ho creato, ma non sarebbe divertente. Spiegherò la logica dietro le scelte del computer.

In questo Instructable, ti guiderò attraverso i passaggi su come creare un'intelligenza artificiale per Othello (AKA Reversi) in Python. Dovresti avere una comprensione intermedia di come codificare in Python prima di affrontare questo progetto. Ecco alcuni buoni siti Web da guardare per prepararti a questo Instructable: w3schools o learnpython. Alla fine di questo Instructable, dovresti avere un'IA che farà mosse calcolate e dovrebbe essere in grado di sconfiggere la maggior parte degli umani.

Poiché questo Instructable si occuperà principalmente di come creare un'intelligenza artificiale, non spiegherò come progettare un gioco in Python. Invece, darò il codice per il gioco in cui un essere umano può giocare contro un altro umano e modificarlo in modo che tu possa giocare a un gioco in cui un umano gioca contro l'IA.

Ho imparato a creare questa IA attraverso un programma estivo alla Columbia SHAPE. Mi sono divertito lì, quindi dai un'occhiata al loro sito Web per vedere se saresti interessato.

Ora che abbiamo tolto di mezzo la logistica, iniziamo a programmare!

(Ho messo un paio di note nelle immagini quindi assicurati di guardarle)

Forniture

Questo è facile:

1) Computer con ambiente Python come Spyder o IDLE

2) Scarica i file per il gioco Othello dal mio GitHub

3) Il tuo cervello con pazienza installato

Passaggio 1: scarica i file necessari

Quando accedi al mio GitHub, dovresti vedere 5 file. Scaricali tutti e 5 e inseriscili tutti nella stessa cartella. Prima di eseguire il gioco, apri tutti i file nell'ambiente spyder.

Ecco cosa fanno i file:

1) othello_gui.py questo file crea il tabellone di gioco su cui i giocatori possono giocare (sia umani che computer)

2) othello_game.py questo file fa giocare due computer uno contro l'altro senza il tabellone e mostra solo il punteggio e le posizioni delle mosse

3) ai_template.py qui è dove metterai tutto il tuo codice per creare la tua AI

4) randy_ai.py questa è un'IA prefabbricata che sceglie le sue mosse in modo casuale

5) othello_shared.py una serie di funzioni predefinite che puoi usare per rendere la tua intelligenza artificiale come controllare le mosse disponibili, il punteggio o lo stato del tabellone

6) Gli altri tre file: Puma.py, erika_5.py e nathan.py, realizzati rispettivamente da me, Erika e Nathan dal programma SHAPE, sono tre AI differenti con codici univoci

Passaggio 2: come aprire e riprodurre Python Othello

Una volta aperti tutti i file, nell'angolo in basso a destra dello schermo, digita "run othello_gui.py" e premi invio nella console IPython. Oppure nel terminale Mac, digita "python othello_gui.py" (dopo che sei nella cartella giusta ovviamente). Quindi una scheda dovrebbe apparire sullo schermo. Questa modalità è la modalità uomo contro uomo. La luce passa per seconda e l'oscurità per prima. Guarda il mio video se sei confuso. iIn alto, c'è il punteggio di ogni tessera colorata. Per giocare, fai clic su uno spazio di movimento valido per posizionare una tessera lì e poi dai il computer al tuo avversario che farà lo stesso e ripeterà.

Se non sai come giocare a Othello, leggi queste regole dal sito web di ultra board:

Il nero muove sempre per primo. Una mossa viene eseguita posizionando un disco del colore del giocatore sul tabellone in una posizione che "affianca" uno o più dischi dell'avversario. Un disco o una fila di dischi viene aggirato quando è circondato alle estremità da dischi del colore opposto. Un disco può aggirare qualsiasi numero di dischi in una o più file in qualsiasi direzione (orizzontale, verticale, diagonale)… (finire di leggere sul loro sito web)

La differenza tra il gioco originale e questo gioco Python è che quando non ci sono mosse valide rimaste per un giocatore il gioco finisce

Ora che puoi giocare con un amico, creiamo un'IA con cui puoi giocare.

Passaggio 3: Algoritmo Minimax: generazione di scenari

Prima di parlare di come scriverlo nel codice, esaminiamo la logica alla base. L'algoritmo minimax è un algoritmo decisionale e di tracciamento all'indietro ed è tipicamente utilizzato nei giochi a turni a due giocatori. L'obiettivo di questa IA è trovare la mossa migliore successiva e le mosse migliori successive fino a quando non vince la partita.

Ora come farebbe l'algoritmo a determinare quale mossa è la mossa migliore? Fermati e pensa a come sceglieresti la prossima mossa. La maggior parte delle persone sceglierebbe la mossa che darebbe loro più punti, giusto? Oppure, se pensassero in anticipo, sceglierebbero la mossa che creerebbe una situazione in cui potrebbero guadagnare ancora più punti. Quest'ultimo modo di pensare è il modo in cui pensa l'algoritmo Minimax. Guarda avanti a tutte le future configurazioni del tabellone e fa la mossa che porterebbe al maggior numero di punti.

L'ho chiamato un algoritmo di backtracking, perché inizia prima creando e valutando tutti i futuri stati della scheda con i loro valori associati. Ciò significa che l'algoritmo giocherà il gioco tutte le volte che è necessario (facendo le mosse per sé e per l'avversario) fino a quando ogni scenario del gioco è stato giocato. Per tenere traccia di tutti gli stati della scacchiera (scenari), possiamo disegnare un albero (guarda le immagini). L'albero nella figura sopra è un semplice esempio di gioco di Connect 4. Ogni configurazione della scheda è chiamata stato della scheda e il suo posto sull'albero è chiamato nodo. Tutti i nodi nella parte inferiore dell'albero sono gli stati finali del tabellone dopo aver eseguito tutte le mosse. Ovviamente alcuni stati della scacchiera sono migliori per un giocatore rispetto all'altro. Quindi, ora dobbiamo fare in modo che l'IA scelga a quale stato della scheda vuole arrivare.

Passaggio 4: Minimax: valutazione delle configurazioni della scheda

Per dare valore agli stati della scacchiera, dobbiamo imparare le strategie del gioco che stiamo giocando: in questo caso, le strategie di Otello. Poiché questo gioco è una battaglia per capovolgere i dischi dell'avversario e dei tuoi, le migliori posizioni dei dischi sono quelle che sono stabili e non possono essere capovolte. L'angolo, ad esempio, è il punto in cui quando un disco viene posizionato non può essere cambiato nell'altro colore. Quindi, quel posto sarebbe estremamente prezioso. Altre buone posizioni includono i lati del tabellone che ti permetterebbero di prendere molte pietre. Ci sono più strategie su questo sito.

Ora possiamo assegnare valori alle posizioni per ogni consiglio di stato. Quando una posizione è occupata dal pezzo dell'IA, assegni un certo numero di punti a seconda della posizione. Ad esempio, uno stato della scacchiera in cui il pezzo dell'IA è nell'angolo, puoi dare un bonus di 50 punti, ma se fosse in un punto sfavorevole, il pezzo potrebbe avere un valore di 0. Dopo aver preso in considerazione tutti i valori di le posizioni, si assegna un valore allo stato della scheda. Ad esempio, se l'IA ha un pezzo nell'angolo, lo stato della scacchiera può avere un punteggio di 50 mentre un altro stato della scacchiera con il pezzo dell'IA nel mezzo ha un punteggio di 10.

Ci sono molti modi per farlo, e ho tre diverse euristiche per valutare i pezzi della scacchiera. Ti incoraggio a creare il tuo tipo di euristica. Ho caricato tre diverse AI sul mio github da tre diversi produttori, con tre diverse euristiche: Puma.py, erika5.py, nathanh.py.

Passaggio 5: Algoritmo Minimax: scelta della mossa migliore

Ora sarebbe bello se l'IA potesse semplicemente scegliere tutte le mosse per arrivare allo stato del tabellone con il punteggio più alto. Ma ricorda che l'IA stava anche scegliendo le mosse per l'avversario quando stava generando tutti gli stati del tabellone e se l'avversario è intelligente, non permetterà all'IA di ottenere il punteggio più alto del tabellone. Invece, un avversario intelligente farebbe la mossa per far passare l'IA allo stato più basso del tabellone. Nell'algoritmo, chiamiamo i due giocatori un giocatore che massimizza e un giocatore che minimizza. L'IA sarebbe il giocatore che massimizza poiché vuole ottenere il maggior numero di punti per se stessa. L'avversario sarebbe il giocatore che riduce al minimo poiché l'avversario sta cercando di fare la mossa in cui l'IA ottiene il minor numero di punti.

Una volta generati tutti gli stati della scheda e assegnati i valori alle schede, l'algoritmo inizia a confrontare gli stati della scheda. Nelle immagini, ho creato un albero per rappresentare come l'algoritmo avrebbe scelto le sue mosse. Ogni divisione nei rami è una mossa diversa che l'IA o l'avversario possono giocare. A sinistra delle righe di nodi, ho scritto se sta andando il giocatore che massimizza o minimizza. La riga in basso sono tutti gli stati del tabellone con i loro valori. All'interno di ciascuno di questi nodi c'è un numero e questi sono i punteggi che assegniamo a ciascuna delle schede: più sono alti, meglio è per l'IA.

Definizioni: nodo padre - un nodo che risulta o crea nodi sotto di esso; l'origine dei nodi figli - i nodi che provengono dallo stesso nodo genitore

I nodi vuoti rappresentano quale mossa farà l'IA per raggiungere il miglior stato della scacchiera. Inizia confrontando i figli del nodo più a sinistra: 10, -3, 5. Poiché il giocatore che massimizza farebbe la mossa, sceglierebbe la mossa che gli darebbe il maggior numero di punti: 10. Quindi, selezioniamo e memorizziamo quella spostati con il punteggio della lavagna e scrivilo nel nodo genitore. Ora che 10 è nel nodo genitore, ora è il turno dei giocatori che minimizzano. Tuttavia, il nodo a cui confronteremmo 10 è vuoto, quindi dobbiamo valutare quel nodo prima che il giocatore che riduce al minimo possa scegliere. Quindi torniamo al turno del giocatore che massimizza e confrontiamo i figli del nodo adiacente: 8, -2. La massimizzazione sceglierà 8 e lo scriviamo nel nodo genitore vuoto. Ora che l'algoritmo ha finito di riempire gli spazi vuoti per i figli di un nodo sopra di esso, il giocatore che minimizza può confrontare quei figli - 10 e 8 e scegliere 8. L'algoritmo quindi ripete questo processo fino a quando l'intero albero non viene riempito. Alla fine di questo esempio, abbiamo il punteggio 8. Questo è lo stato più alto del tabellone che l'IA può assumere assumendo che l'avversario stia giocando in modo ottimale. Quindi l'IA sceglierà la prima mossa che porta allo stato del tabellone 8, e se l'avversario gioca in modo ottimale, l'IA dovrebbe giocare tutte le mosse per arrivare allo stato del tabellone 8. (Seguire le note sulle mie foto)

So che era molto. Se sei uno di quei tipi che hanno bisogno di qualcuno che ti parli per capire qualcosa, ecco un paio di video che ho guardato per aiutarmi a capire l'idea alla base: 1, 2, 3.

Passaggio 6: Algoritmo Minimax: Pseudocodice

Dopo aver compreso la logica dietro l'algoritmo minimax, dai un'occhiata a questo pseudocodice (le funzioni universali per tutti i codici) da wikipedia:

la funzione minimax (nodo, profondità, maximizingPlayer) è

se profondità = 0 o nodo è un nodo terminale allora

restituisce il valore euristico di node

se massimizzando il giocatore allora

valore:= −∞

per ogni figlio del nodo do

valore:= max(valore, minimax(figlio, profondità − 1, FALSO))

valore di ritorno

else (* giocatore minimizzato *)

valore:= +∞

per ogni figlio del nodo do

value:= min(value, minimax(child, depth − 1, TRUE))

valore di ritorno

Questa è una funzione ricorsiva, nel senso che chiama se stessa più e più volte finché non raggiunge un punto di arresto. Innanzitutto, la funzione assume tre valori, il nodo, la profondità e di chi è il turno. Il valore del nodo è il punto in cui si desidera che il programma inizi la ricerca. La profondità è quanto lontano vuoi che il programma cerchi. Ad esempio, nel mio esempio di albero ha una profondità di 3, perché ha cercato tutti gli stati della scacchiera dopo 3 mosse. Naturalmente, vorremmo che l'IA controllasse ogni stato della scheda e scegliesse una vincita vincente, ma nella maggior parte dei giochi in cui ci sono migliaia se non milioni di configurazioni della scheda, il tuo laptop a casa non sarà in grado di elaborare tutte quelle configurazioni. Quindi, limitiamo la profondità di ricerca dell'IA e la facciamo passare allo stato migliore della scheda.

Questo pseudocodice riproduce il processo che ho spiegato nei due passaggi precedenti. Ora facciamo un ulteriore passo avanti e correggiamo questo in codice Python.

Passaggio 7: creare la tua intelligenza artificiale con Ai_template.py

Prima di dare un'occhiata al mio codice Minimax AI, prova a creare la tua AI con il file ai_template.py e lo pseudo-codice di cui abbiamo parlato nell'ultimo passaggio. Ci sono due funzioni nel template ai chiamate: def minimax_min_node(board, color) e def minimax_max_node(board, color). Invece di fare in modo che la funzione minimax si chiami ricorsivamente, abbiamo due funzioni diverse, che si chiamano a vicenda. Per creare l'euristica per valutare gli stati della scheda, dovrai creare la tua funzione. Ci sono funzioni predefinite nel file othello_shared.py che puoi usare per costruire la tua intelligenza artificiale.

Una volta che hai la tua intelligenza artificiale, prova a eseguirla contro, randy_ai.py. Per eseguire due ais l'uno contro l'altro, digita "python othello_gui.py (inserisci nome file ai).py (inserisci nome file).py" nel terminale mac o digita "run othello_gui.py (inserisci nome file ai).py (inserisci il nome del file).py" e assicurati di essere nella directory giusta. Inoltre, guarda il mio video per i passaggi esatti.

Passaggio 8: è ora di far combattere l'IA

Ora ottieni un gruppo di tuoi amici computer e falli progettare la propria intelligenza artificiale! Quindi puoi fare una competizione e far combattere la tua intelligenza artificiale. Si spera che, anche se non sei riuscito a creare la tua intelligenza artificiale, sei stato in grado di capire come funziona l'algoritmo minimax. Se hai domande, sentiti libero di postare qualsiasi domanda nei commenti qui sotto.