tic tac toe con prolog come batterlo???

[musica1000w]

Ciao a tutti, stavo cercando di capirci qualcosa del prolog grazie ad un giochino del tris trovato su internet, il massimo che riesco a fare però è raggiungere la parità, ma non riesco a vincere, questo perché è tecnicamente impossibile, o semplicemente non sono in grado io??? :D

di seguito vi riporto il codice, magari se qualcuno riesce anche a delucidarmi alcune funzioni come lo split ne sarei grato.

/*

Prolog code developped for use in the lecture

'Programmierparadigmen (PGP)'
Sommer 2007

program taken from M.L.Scott: 'Programming Language Pragmatics', 2000

Ch. 11.3

adapted to SWI prolog; All rights reserved, copyright 2006, 2007 D. Rösner

*/

:- dynamic o/1.
:- dynamic x/1.

/* the various combinations of a successful horizontal, vertical
or diagonal line */

ordered_line(1,2,3).
ordered_line(4,5,6).
ordered_line(7,8,9).
ordered_line(1,4,7).
ordered_line(2,5,8).
ordered_line(3,6,9).
ordered_line(1,5,9).
ordered_line(3,5,7).

/*
we use the line predicate to complete lines (cf. below),
so the elements of an ordered_line may be completed in any order,
i.e. as permutations of (A,B,C)
*/

line(A,B,C) :- ordered_line(A,B,C).
line(A,B,C) :- ordered_line(A,C,B).
line(A,B,C) :- ordered_line(B,A,C).
line(A,B,C) :- ordered_line(B,C,A).
line(A,B,C) :- ordered_line(C,A,B).
line(A,B,C) :- ordered_line(C,B,A).

/* a move to choose, i.e. field to occupy, should be good
according to some strategy and the field should be empty */

move(A) :- good(A), empty(A).

/* a field is empty if it is not occupied by either party */

full(A) :- x(A).
full(A) :- o(A).

empty(A) :- not(full(A)).

%%% strategy

good(A) :- win(A).
good(A) :- block_win(A).
good(A) :- split(A).
good(A) :- block_split(A).
good(A) :- build(A).

%%% default case of picking the center, the corners and the sides
%%% in that order

good(5).
good(1). good(3). good(7). good(9).
good(2). good(4). good(6). good(8).

%%% we win by completing a line

win(A) :- x(B), x(C), line(A,B,C).

%%% we block the opponent to win by completing his possible line

block_win(A) :- o(B), o(C), line(A,B,C).

%%% a split creates a situation where opponent can not block a win in the next move

split(A) :- x(B), x(C), different(B,C), line(A,B,D), line(A,C,E), empty(D), empty(E).

same(A,A).
different(A,B) :- not(same(A,B)).

%%% block opponent from creating a split

block_split(A) :- o(B), o(C), different(B,C), line(A,B,D), line(A,C,E), empty(D), empty(E).

%%% simply pick a square that builds towards a line

build(A) :- x(B), line(A,B,C), empty(C).

%%%****************************************************************
%%% predicates to interactively run the game

%%% when is game definitely over?
all_full :- full(1),full(2),full(3),full(4),full(5),full(6),full(7),full(8),full(9).

%%% options for earlier success

done :- ordered_line(A,B,C), x(A), x(B), x(C), write('I won.'),nl.

done :- ordered_line(A,B,C), o(A), o(B), o(C), write('You won.'),nl.

done :- all_full, write('Draw.'), nl.

%%% interaction

getmove :- repeat, write('Please enter a move: '),read(X), between(1,9,X), empty(X), assert(o(X)).

%%% the computer's moves

makemove :- move(X),!, assert(x(X)).
makemove :- all_full.

%%% printing the board

printsquare(N) :- o(N), write(' o ').
printsquare(N) :- x(N), write(' x ').
printsquare(N) :- empty(N), write(' ').

printboard :- printsquare(1),printsquare(2),printsquare(3),nl,
printsquare(4),printsquare(5),printsquare(6),nl,
printsquare(7),printsquare(8),printsquare(9),nl.

%%% clearing the board

clear :- x(A), retract(x(A)), fail.
clear :- o(A), retract(o(A)), fail.

%%% main goal that drives everything:

play :- not(clear), repeat, getmove, makemove, printboard, done.

Grazie a coloro che interverranno!

[gbhu]

A quel gioco non si può vincere (a meno che l'avversario non conosca il pattern di base).
Al massimo si può giungere alla parità.
E' una cosa puramente algoritmica e di algorirmo semplice da formalizzare per cui non è difficile fare un programma che giochi benissimo.

P.S. Era stato usato anche nel film War Games per indurre il supercalcolatore intelligente a comprendere che per certe situazioni non esiste la soluzione. Una guerra atomica tra USA e URSS infatti avrebbe portato solo alla distruzione di entrambi.

[musica1000w]

Ti ringrazio della risposta, gentilissimo!
Una domanda, probabilmente potrai darmi la giusta risposta, dalla parte della strategia fino ai predicati sono le regole imposte al gioco giusto? dove c'è scritto good(5).
good(1). good(3). good(7). good(9).
good(2). good(4). good(6). good(8).

il fatto di essere scritto in questo modo assegna un certo peso alla posizione?
Conosci qualche altro giochino semplice fatto in prolog? ti ringrazio!

[musica1000w]

Scusate ancora ma man mano che leggo informazioni, mi vengono domande e posto qui, se devo creare una nuova discussione per le altre domande, vi prego di segnalarmelo.
Mentre leggo nella letteratura, ho notato che per quanto riguarda la teoria dei giochi, in giochi come il tris, gli scacchi, la dama ecc si utilizzano gli algoritmi Min-Max e le potature alfa-beta. In questo caso specifico però non riesco ad individuare dove siano state implementati questi algoritmi, questo perchè visto la semplicità del gioco e la quantità limitata delle mosse non è necessario implementarli??

[oNaSsIs]

dove c'è scritto good(5).
good(1). good(3). good(7). good(9).
good(2). good(4). good(6). good(8).

il fatto di essere scritto in questo modo assegna un certo peso alla posizione?
Premesso che non sono un esperto in Prolog, per quel che ne so io, quella scrittura non assegna nessuna priorità, se non che nel patter matching la posizione 5 sarà valutata per prima, poi la 1, la 3, la 7 e così via.

[musica1000w]

Grazie gentilissimo per la risposta. Quindi questo dovrebbe confermare quello che avevo notato, che utilizzando questo pattern maching e l'utilizzo di assert non utilizza l'algoritmo min/max perché in pratica valuta con assert come è composta la griglia, e sceglie dove posizionare il segno in base a quel pattern, giusto?

[musica1000w]

Ciao a tutti, sto provando a modificare il codice e l'ultima domanda riguarda questa riga di comando:

getmove :- repeat, write('Please enter a move: '),read(X), between(1,9,X), empty(X), assert(o(X)).


In pratica ogni volta che devo fare la mia mossa mi esce scritto 'Please enter a move: ' e questo va bene nel momento in cui io metto un numero compreso da 1 a 9 e non è occupato.
Se volessi invece che mi uscisse a video un messaggio che ho sbagliato mossa perché non entra in quel range di 1-9? o quella mossa non è possibile farla perché la casella è piena?
Allo stato attuale con quel codice se sbaglio numero o è occupato mi esce nuovamente la scritta 'Please enter a move: ' senza indicarmi l'errore.
Spero di esser stato chiaro...grazie!

[oNaSsIs]

Questo codice non funziona correttamente, perché il computer nonostante l'errore continua a giocare. Però ti mostra come fare controlli sull'input. Secondo me modificandolo un po', dovresti riuscire a sistemare il gioco.
getmove :- write('Please enter a move: '), read(X),
( not(between(1,9,X)) -> write('Out of the range 1-9'), !;
( not(empty(X)) -> write('Busy cell'), !;
( between(1,9,X), empty(X) -> assert(o(X))))).

[musica1000w]

Ho cercato di implementare questo codice che mi hai proposto, ma purtroppo come dici tu non funziona correttamente, forse dovrei mettere insieme anche l'altra parte di codice che fa riferimento alle mosse del computer, ma ovviamente questa cosa non sono riuscito a farla! :(

[oNaSsIs]

Mi spiace, ma in questo periodo sono molto impegnato e non ho molto tempo libero.
Ad una prima occhiata non riesco a determinare correttamente quello che è il flusso del programma e quindi dove intervenire.
Se posso darti un consiglio, io proverei a scriverlo da zero e nel caso tu non riesca ad implementare qualche funzionalità dai pure una sbirciata al codice che hai. In questo modo secondo me riuscirai ad avere maggiore controllo del programma e apportare più facilmente delle modifiche.
Per qualsiasi problema chiedi pure, se posso sarò felice di aiutarti.

[musica1000w]

Ti ringrazio dei consigli che hai saputo darmi, purtroppo anche provando a riscrivere il codice non ho la giusta competenza per risolvere il problema, l'unica via di funzionamento che credo coerente per quello che vorrei implementare io è come hai suggerito tu, ma non capisco il motivo per il quale non si blocca il gioco quando sbaglio una mossa....altre idee non riesco proprio a metterle in pratica... Non voglio disturbarti, cercherò di arrangiarmi :rolleyes: ;)

[banryu79]

Ad una prima occhiata non riesco a determinare correttamente quello che è il flusso del programma e quindi dove intervenire.

La stessa cossa che ho pensato io mentre leggevo il programma e tentavo di ricostruire mentalmente il flusso d'esecuzione.

@musica1000w:
E' chiaro che senza ricostruire il flusso di esecuzione del programma non è possibile fare una modifica precisa quindi... non ti resta che armarti di carta e penna e ricostruire il flusso del programma man mano che lo leggi :D

Sarà rognoso ma una volta fatto questo immagino sarà molto più semplice e rapido capire dove/come intervenire per apportare modifiche.
Almeno è quello che farei io, ma non ho mai giocato con Prolog o linguaggi simili.

Spera in consigli più circostanziati da parte di qualche utente scafato con questo linguaggio.

[oNaSsIs]

E' sufficiente che sposti il makeMove nel getMove in questo modo.
getmove :- write('Please enter a move: '), read(X),
( not(between(1,9,X)) -> write('Out of the range 1-9'), !;
( not(empty(X)) -> write('Busy cell'), !;
( between(1,9,X), empty(X) -> assert(o(X)), makemove))).

Magari non è la più elegante delle soluzioni, ma funziona.

[musica1000w]

Ragazzi grazie delle risposte! Ci siamo quasi però, perchè ora succede che quando io faccio una mossa, il computer ne fa 2! :D

[oNaSsIs]

Forse sottolineare sposti non è bastato ad evidenziarlo! :D
Devi cancellare makemove da play e lasciarlo solo in getmove. In questo modo il computer fa una mossa soltanto quando anche la tua mossa viene accettata. ;)

[musica1000w]

Eheheh...avevo detto che ero proprio una frana, il codice ora l'ho modificato come volevo io! Ringrazio tutti dell'aiuto!

[musica1000w]

Ciao ragazzi, mentre ho provato a giocare a tris con il prolog seguendo questo codice mi sono reso conto che effettivamente non funzionava correttamente, perchè mi dava la possibilità di effettuare uno split (mettermi in una condizione tale da poter battere il computer in una mossa successiva) e nel momento che completavo una mia sequenza, non mi dava la vittoria e continuava a giocare lui fino a vincere. Non so se mi sono spiegato perchè l'ho scritta con i piedi questa cosa, vabbè il senso è che le strategie non funzionavano correttamente, mettendomi alla ricerca ho trovato su un libro le 5 strategie che funzionano bene e sono le seguenti:


% Si vince quando si completa una riga (o colonna o diagonale)

win(A) :- x(B), x(C), line(A,B,C).

% Si può bloccare la vincita dell'avversario se si blocca una linea

block_win(A) :- o(B), o(C), line(A,B,C).

/* uno "split" crea una situazione in cui avversario non può bloccare
una vittoria nella prossima mossa */

split(A) :- x(B), x(C), different(B,C), line(A,B,D), line(A,C,E), empty(D), empty(E).

same(A,A).
different(A,B) :- not(same(A,B)).

/* Per bloccare un avversario in modo da non fargli creare una situazione di "split" */

strong_build(A) :- x(B), line(A, B, C), empty(C), \+(risky(C)).
risky(C) :- o(D), line(C, D, E), empty(E).

% Bloccare lo split

weak_build(A) :- x(B), line(A, B, C), empty(C), \+(double_risky(C)).
double_risky(C) :- o(D), o(E), different(D, E), line(C, D, F),
line(C, E, G), empty(F), empty(G).

Le prime e tre sono uguali a quelle che c'erano prima e le riesco ad interpretare, ma le ultime 2 non riesco a capire il significato, come si interpretano? cioè so quello che fanno ma non capisco come sono state dichiarare come si "leggono"...:)

[oNaSsIs]

Sai che \+ significa not?

[musica1000w]

Ora lo so... :D ma come si interpreta la clausola ancora non l'ho capito però...

[oNaSsIs]

strong_build viene eseguito quando le prime clausole sono vere e risky è falso, quindi vero dopo aver applicato il not.
Non saprei come altro spiegarlo, si tratta di logica di base.

[musica1000w]

Ciao, forse non mi sono spiegato bene, non è che non ho capito il funzionamento di base della logica, non riesco a capire la configurazione della griglia, non riesco a farmi lo schema mentale delle posizioni, line(A, B, C) dovrebbe essere una riga orizzontale, ma line(C, D, E) non dovrebbe essere una riga orizzontale...boh? Cerco di studiare meglio il significato delle posizioni... Grazie per tutto! :)