Introduzione

Il Tic Tac Toe ( più comunemente chiamato Tris o filetto, ) è uno dei più semplici giochi per lo studio dell’intelligenza artificiale, questa sua semplicità lo rende estremamente facile da implementare e soprattutto da capire.

Il Tic Tac Toe è un classico esempio di gioco a decisione perfetta a somma zero, in parole semplici è possibile analizzare tutte le mosse e possibili contromosse dell’avversario sino a raggiungere la fine della partita che si può risolvere con una vittoria di uno dei 2 giocatori o con un pareggio, per cui si conosce la “strategia perfetta”( vedere l’equilibrio di Nash ), che nel caso peggiore porta ad una situazione di pareggio.

Questo tipo di gioco può essere definito mediante una serie di sezioni base:

• Inizializzazione dove sono definite e inizializzate le variabili
• Generatore di Mosse dove vengono stabilite le mosse valide e con quali criteri possono essere eseguite, nel caso non si possano eseguire mosse si tratterà di un pareggio.
• Test per il Tris dove viene controllato se uno dei due giocatori ha effettuato un tris e quindi vinto ( questo viene definito come stato terminale del gioco )

Implementazione in Visual Basic

Premetto che ci sono molti modi per implementare il Tic Tac Toe , ho cercato di utilizzare uno stile di programmazione molto semplice per facilitare la comprensione degli algoritmi utilizzati.

Qui viene postato solo il modulo per AI, se volete tutto il codice del progetto si prega di contattarci

Public Const kNULL = 0

Public Const kCROSS = 1

Public Const kCIRCLE = -1

'numero di celle

Public Const kNUMCELLE = 9

'giocatori

Public Const kMIN = -1

Public Const kMAX = 1

'valori

Public Const kVAL_MIN = -1000

Public Const kVAL_DRAW = 0

Public Const kVAL_MAX = 1000

Public Const kVAL_INFINITO = 10000

'stato di gioco

Public Const kSTATE_NOPLAY = 0

Public Const kSTATE_PLAY = 1

Public Const kSTATE_DRAW = 2

Public Const kSTATE_WINHUMAN = 10

Public Const kSTATE_WINCPU = 20

'celle

Public gCelle(10) As Integer

Public gCelleSim(10) As Integer

'turno del giocatore

Public gTurnoPlay As Integer

'Stato di gioco

Public gGameState As Integer

'numero di mosse simulate

Public gNumeroMosseSimulate As Long

'funzione principale di gioco

'ritorno lo stato

Public Function Game() As Integer

'numero di mosse

Dim nummosse As Integer

Dim mosse(10) As Byte

'indice for

Dim i As Integer

'mossa da eseguire

Dim valore As Integer

Dim MossaDaFare As Byte

Dim ValoreMossa As Integer

'tempo

Dim StartTime As Single

Dim EndTime As Single

'per comodità creo una copia delle mosse

For i = 0 To kNUMCELLE - 1

gCelleSim(i) = gCelle(i)

Next

'vado avanti

Game = kSTATE_PLAY

'azzero le mosse simulate

gNumeroMosseSimulate = 0

'inizio

StartTime = Timer

'cerco le mosse

nummosse = SearchMoves(gCelleSim, mosse)

'se non ci sono mosse valide abbiamo pareggiato

If nummosse = 0 Then

Game = kSTATE_DRAW

Exit Function

End If

'azzero il valore della mossa più alto

ValoreMossa = -kVAL_INFINITO

'-------------------    Eseguo le simulazione

For i = 0 To nummosse - 1

'faccio la mossa

MakeMove mosse(i), kCIRCLE

'controllo il tris

If CheckTris(gCelleSim, kCIRCLE) = True Then

MossaDaFare = mosse(i)

ValoreMossa = kVAL_MAX

Else

'eseguo il nodo del giocatore

valore = Min(2)

End If

'ripristino la mossa

UndoMove mosse(i)

'---------------------

'controllo se ho migliorato la mossa

If valore > ValoreMossa Then

ValoreMossa = valore

MossaDaFare = mosse(i)

End If

Next

'-------------------

'ESEGUO LA MOSSA TROVATA

gCelle(MossaDaFare) = kCIRCLE

'-------------------

'fine

EndTime = Timer

'setto il report

frmMain.rtf1.Text = frmMain.rtf1.Text + "Numero mosse :"

frmMain.rtf1.Text = frmMain.rtf1.Text + Str(gNumeroMosseSimulate)

frmMain.rtf1.Text = frmMain.rtf1.Text + vbNewLine

frmMain.rtf1.Text = frmMain.rtf1.Text + "Tempo in secondi :"

frmMain.rtf1.Text = frmMain.rtf1.Text + Str(EndTime - StartTime)

frmMain.rtf1.Text = frmMain.rtf1.Text + vbNewLine

'-------------------

'controllo se ci sono tris

If CheckTris(gCelle, kCIRCLE) = True Then

'VINTO

Game = kSTATE_WINCPU

ElseIf CheckTris(gCelle, kCROSS) = True Then

'VINTO

Game = kSTATE_WINHUMAN

Else

'CONTROLLO SE POSSO MUOVERE

nummosse = SearchMoves(gCelle, mosse)

If nummosse = 0 Then

'PAREGGIO

Game = kSTATE_DRAW

End If

End If

'-------------------

End Function

'**************************************************************

'   MIN MAX

'**************************************************************

'funzione principale di valutazione min

Private Function Min(ByVal Nodo As Integer) As Integer

'numero di mosse

Dim nummosse As Integer

Dim mosse(10) As Byte

'indice for

Dim i As Integer

'mossa da eseguire

Dim valore As Integer

Dim ValoreMossa As Integer

'cerco le mosse

nummosse = SearchMoves(gCelleSim, mosse)

'se non ci sono mosse valide abbiamo pareggiato

If nummosse = 0 Then

Min = kVAL_DRAW

Exit Function

End If

'azzero il valore della mossa più alto

ValoreMossa = kVAL_INFINITO

'-------------------    Eseguo le simulazione

For i = 0 To nummosse - 1

'faccio la mossa

MakeMove mosse(i), kCROSS

'controllo il tris

If CheckTris(gCelleSim, kCROSS) = True Then

MossaDaFare = mosse(i)

ValoreMossa = kVAL_MIN + Nodo

Else

'eseguo il nodo del giocatore

valore = Max(Node + 1)

End If

'ripristino la mossa

UndoMove mosse(i)

'---------------------

'controllo se ho migliorato la mossa

If valore < ValoreMossa Then

ValoreMossa = valore

End If

Next

'-------------------

Min = ValoreMossa

'-------------------

End Function

'funzione principale di valutazione max

Private Function Max(ByVal Nodo As Integer) As Integer

'numero di mosse

Dim nummosse As Integer

Dim mosse(10) As Byte

'indice for

Dim i As Integer

'mossa da eseguire

Dim valore As Integer

Dim ValoreMossa As Integer

'cerco le mosse

nummosse = SearchMoves(gCelleSim, mosse)

'se non ci sono mosse valide abbiamo pareggiato

If nummosse = 0 Then

Max = kVAL_DRAW

Exit Function

End If

'azzero il valore della mossa più alto

ValoreMossa = -kVAL_INFINITO

'-------------------    Eseguo le simulazione

For i = 0 To nummosse - 1

'faccio la mossa

MakeMove mosse(i), kCIRCLE

'controllo il tris

If CheckTris(gCelleSim, kCIRCLE) = True Then

MossaDaFare = mosse(i)

ValoreMossa = kVAL_MAX - Nodo

Else

'eseguo il nodo del giocatore

valore = Min(Node + 1)

End If

'ripristino la mossa

UndoMove mosse(i)

'---------------------

'controllo se ho migliorato la mossa

If valore > ValoreMossa Then

ValoreMossa = valore

End If

Next

'-------------------

Max = ValoreMossa

'-------------------

End Function

'**************************************************************

'   MOSSE

'**************************************************************

'funzione per cercare le mosse

'e restituisce il numero di mosse trovate

Private Function SearchMoves(ByRef celle() As Integer, ByRef moves() As Byte) As Integer

Dim i As Integer

'azzero

SearchMoves = 0

'ciclo per tutte le possibili posizioni

For i = 0 To kNUMCELLE - 1

'se le posizioni sono nulle

If celle(i) = kNULL Then

moves(SearchMoves) = i

SearchMoves = SearchMoves + 1

End If

Next i

End Function

'funzione per fare una mossa

Private Sub MakeMove(ByVal casella As Byte, ByVal valore As Integer)

gCelleSim(casella) = valore

gNumeroMosseSimulate = gNumeroMosseSimulate + 1

End Sub

'funzione per ripristinare la mossa

Private Sub UndoMove(ByVal casella As Byte)

gCelleSim(casella) = kNULL

End Sub

'funzione per trovare un tris

Public Function CheckTris(ByRef pCelle() As Integer, ByVal Tipo As Integer) As Boolean

Dim check(10, 3) As Byte

Dim i As Integer

'azzero

CheckTris = False

'controllo i tris

'---------------------

'X X X

'- - -

'- - -

check(0, 0) = 0

check(0, 1) = 1

check(0, 2) = 2

'- - -

'X X X

'- - -

check(1, 0) = 3

check(1, 1) = 4

check(1, 2) = 5

'- - -

'- - -

'X X X

check(2, 0) = 6

check(2, 1) = 7

check(2, 2) = 8

'---------------------

'---------------------

'X - -

'X - -

'X - -

check(3, 0) = 0

check(3, 1) = 3

check(3, 2) = 6

'- X -

'- X -

'- X -

check(4, 0) = 1

check(4, 1) = 4

check(4, 2) = 7

'- - X

'- - X

'- - X

check(5, 0) = 2

check(5, 1) = 5

check(5, 2) = 8

'---------------------

'---------------------

'X - -

'- X -

'- - X

check(6, 0) = 0

check(6, 1) = 4

check(6, 2) = 8

'---------------------

'- - X

'- X -

'X - -

check(7, 0) = 2

check(7, 1) = 4

check(7, 2) = 6

'---------------------

'ciclo per il check

For i = 0 To 7

If pCelle(check(i, 0)) + pCelle(check(i, 1)) + pCelle(check(i, 2)) = Tipo * 3 Then

CheckTris = True

Exit Function

End If

Next

End Function