Quantum Tic-Tac-Toe AI

Question

Nella mia classe di strutture dati, ci è stato assegnato un progetto in cui ci viene richiesto di realizzare un gioco Quantum Tic-Tac-Toe perfettamente funzionante in cui un giocatore affronta un robot che gioca a vincere.

Il professore ha suggerito di utilizzare un albero di gioco nella nostra IA. Tuttavia, come al solito, sto cercando qualcosa di più impegnativo.

Qualcuno può suggerire un approccio migliore e più avanzato che potrei ricercare e implementare?

---

io non sono alla ricerca di qualcosa di completamente ridicolo che rende il problema più complesso. Piuttosto, sto cercando un approccio avanzato - come usare un algoritmo A * piuttosto che un BFS.

Answer 1

Il tuo desiderio di imparare cose nuove (da solo) è buono. Tuttavia, una soluzione complicata è spesso not the best solution.

C'è una buona ragione per cui il tuo professore ha suggerito di usare un albero di gioco per l'intelligenza artificiale. È suggerito perché è lo strumento giusto per il lavoro. Non esiste un approccio migliore che puoi ricercare perché è l'approccio migliore.

Hai detto che ti trovi in ​​una classe di strutture dati (che di solito è una prima o seconda classe). Immagino che il punto del tuo compito sia quello di conoscere le strutture dei dati dell'albero. Se vuoi rendere le cose più complicate, scrivi prima la versione ad albero e poi cerca altri modi per risolvere lo stesso problema.

Answer 2

di fornire una caratteristica di apprendimento per l'implementazione, si può guardare in un emulatore per Donald Mitchie s' MENACE (Matchbox educable tris Motore) ...

Edit:
Nel guardare in esso, questo è stato fatto un po ', si veda ad esempio questo su CodeProjet
Inoltre, e mentre si acquisisce un modello statistico del mondo (o qui del mondo ridotto Tic-Tac-Toe) e basando le azioni future su tale modello è intelligente comportamento, può essere considerato fuori dal campo di applicazione dal tuo professore, perché non tocca i concetti chiave che tu pr Obbligatoriamente coperta in classe (rappresentazione della conoscenza, alberi decisionali ...)

Answer 3

Ci sono 2 parti per valutare un gioco a turni.

1. L'albero del gioco.
2. Una funzione di utilità.

L'albero di gioco consente di riprodurre le mosse in anticipo per vedere dove porteranno. Se il gioco è abbastanza complesso da non poter calcolare tutte le possibilità (http://en.wikipedia.org/wiki/Solved_game), allora hai bisogno di un modo per determinare come "buono" uno scenario di una particolare tavola è. Una scarsa funzione di utilità per gli scacchi potrebbe semplicemente contare i valori dei pezzi e ignorare la posizione.

È inoltre necessario un modo efficiente di attraversare l'albero del gioco. Leggi di Minimax, potatura alfa-beta, Negascout, ecc.

Answer 4

realtà sto lavorando su questo problema specifico in questo momento: http://www.rickb.com/quantum-tic-tac-toe

avevo pensato di fare qualcosa di più avanzato pure, ma sto solo attenersi al buon algoritmo di ricerca ol' alfa-beta.Il mio problema principale è venire con un buon algoritmo per "segnare" ogni particolare stato della scheda. Il QTTT è molto più complicato del tic tac toe standard, il numero di stati da cercare è esponenzialmente più grande. Ho in memoria l'intero albero standard di gioco del tic tac toe che uso per cercare rapidamente il punteggio per ogni stato di "classica" scheda, ma poi devo valutare lo stato di sovrapposizione in qualche modo. Il numero di stati è così grande che non è possibile andare troppo in profondità nell'albero, quindi una funzione di punteggio appropriata per potare l'albero in anticipo è un must.