Semplice tic-tac-toe AI

Question

So che questo è stato chiesto molto e ho cercato altro codice ma la maggior parte di ciò che ho visto non sembra perfetto (non perde mai) e semplice, elegante ed efficiente. E non sono in grado di decidere quale tipo di soluzione si adatta a questa descrizione.

Le soluzioni che ho visto sono:

(1) Utilizzando minimax con alfa-beta potatura. Questo mi sembra complicato e forse non necessario per un gioco così semplice? Probabilmente è troppo complicato? In caso contrario, dovrei fare un sacco di hard coding o sto fraintendendo l'algoritmo?

(2) Scrivi il tuo codice utilizzando la strategia pseudocodice da Wikipedia ... Non sono esattamente sicuro di come implementarlo. Ad esempio, dice semplicemente "check for fork". La maggior parte di questi controlli sarebbe stata eseguita con una serie di linee vincenti e controllando se sarebbero stati compilati o qualcosa del genere? In caso contrario, qualcuno può darmi suggerimenti su quali strutture dati o suggerimenti di base su come implementare i controlli posti nello pseudocodice qui: http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy. Ho anche visto algoritmi che danno un valore numerico a un quadrato "X" e un quadrato "O" e poi usano la somma per decidere il vincitore, ma non vedo perché questo sia particolarmente utile.

Qualsiasi altra soluzioni ragionevole?

Answer 1

Per essere onesti, quando si ha a che fare con l'intelligenza artificiale e l'euristica, i compiti più semplici possono complicarsi molto rapidamente. L'approccio minimax ti darà i migliori risultati e non dovrebbe essere troppo difficile considerando il fatto che stai implementando l'intelligenza artificiale. È uno standard consolidato con logica di gioco basata su turni a 2 giocatori.

Dai un'occhiata a questo sito Web ... offre alcune informazioni utili sull'IA tic-tac-toe e l'implementazione minimax.

http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

Edit:

notare che qualcuno ha scritto "Brute Force" ... questo sta per finire per essere un modo inefficiente di attuazione delle euristiche coinvolti nella Minimax. L'iterazione di ogni mossa possibile basata sull'ultima mossa dei giocatori è solo un altro modo per attuare un'euristica .. eccetto che sembra, a mio parere, più lavoro. L'implementazione di Minimax sarà semplice ed efficace.

Edit2:

"più semplice implementazione" è in qualche modo relativo. Minimax è lo standard e come ho detto nel commento è possibile manipolare l'euristica per adattarsi ai casi che stai cercando ...

Vorrei poterti dire il modo più semplice ma ci sono così tante variabili dipendenti dall'impianto del tuo gioco in codice.

Prendi i suggerimenti, guarda l'implementazione del gioco e poi guarda cosa ti si addice meglio!

Ciò che è semplice per una persona potrebbe essere complicato a un altro. Sto solo cercando di darti delle opzioni e minimax è abbastanza solida. Forse prova ad adattarlo alle tue esigenze.

Edit3:

fatemi sapere se avete bisogno di più direzione. Sono felice di aiutare.

Answer 2

Utilizzare il formato desiderato per "codificare" this image in un insieme di mosse. L'IA vincerà o vincerà sempre.

Ad esempio, è possibile codificare come segue:

var turns = { 
    "mefirst":{ 
    "move":0, 
    "next":[ 
     null, 
     { 
     "move":4, 
     "next":[ 
      null, 
      null, 
      {"move":8}, // win 
      {"move":8}, // win 
      null, 
      {"move":8}, // win 
      {"move":8}, // win 
      {"move":8}, // win 
      { 
      "move":6, 
      "next":[ 
       null, 
       null, 
     /* AND SO ON... */ 
    ] 
    } 
}; 

allora si può iniziare con:

if(ai_goes_first) { 
    game = turns.mefirst; 
    makeMove(game.move); 
} 
else game = turns.themfirst; 
playerTurn(); 

Dove playerTurn è qualcosa di simile:

function playerTurn() { 
    when player clicks a valid squeare { 
     game = game.next[chosenSquare]; 
     makeMove(game.move); 
     if(game.next) playerTurn(); 
    } 
}