Obrigado pela vossa atenção.
O jogo do othello é o seguinte
INSTRUCTIONS
This is the famous reversi / othelo game. Reversi is a two player game (blue and red), and is normally played on a 8x8 grid. The object of the game is to fill the board with your own colour of pieces. You win if at the end of the game there are more pieces of your own colour on the board than your opponent\\'s. The initial setup of the board is two pieces for each player, placed diagonally to each other in the centre of the board.
Each player in turn places a piece on the board, starting with the player using the blue pieces (human player). A valid is one where you can turn at least one of your opponents pieces into a piece of your colour. You can do this if when you place on the board, it terminates a continuous line of pieces of the opposing colour, with one of your pieces at the other end of the line. All of the pieces in the line are then flipped to your colour. The lines can be in any of the eight lateral and diagonal directions from the position you have chosen. If there is more than one such line of pieces, all of them are flipped to your colour.
Basic rules of the game are:
The player with the blue pieces goes first, and then play alternates.
To make a move, you must be able to flip at least one of your opponents pieces to your colour, by completing a line of pieces as described above.
If you can make a valid move, you must.
If you can\\'t go, you must pass your turn and your opponent plays again.
Enjoy!
Tenho o jogo desenvolvido em Prolog, mas tambem nada percebo desta linguagem, deveria existir um conversor de Prolog em Lisp
--------------- // -----------------
/*******************************************************************************/
/* */
/* Programa em Prolog para o JOGO OTELO */
/* */
/* Representacao do Estado com Listas, Raciocinio usando o Minimax */
/* */
/* Luis Paulo Reis, 20 de Dezembro de 1999 */
/* */
/*******************************************************************************/
/*******************************************************************************/
/* */
/* Predicados Centrais do jogo - OTELO */
/* */
/*******************************************************************************/
:-dynamic(pos_ini).
/* Posicao Inicial do jogo! */
pos_ini([[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,1,2,0,0,0],
[0,0,0,2,1,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]]).
/* nivel do jogo */
nivel(4).
/* Inicio do Jogo! Pergunta quem joga, le a posicao inicial e deixa o primeiro
jogador fazer a primeira jogada! */
i:-inicio.
inicio:-
repeat,
write(\\'Quem Joga 1/2? (1-Hum, 2-Comp) \\'),
read©,
% fread(i,0,0,C),
pos_ini(Board),
write(\\'inicio\\'),
joga(C,Board).
/* Para deixar um jogador - J fazer uma jogada no tabuleiro actual - Board,
mostra o tabuleiro, define a jogada - Mov, escreve-a no ecran e executa-a,
criando o novo tabuleiro - NewBoard)! Depois, verifica se apos esta jogada,
o jogo acabou, caso em que finaliza, ou nao, caso em que muda o jogador a
jogar e deixa-o jogar no novo tabuleiro (NewBoard). */
joga(J,Board):-
mostra_tab(Board),
(valid_moves(J, [], Board),
write(\\'Passo! \\'),
NewBoard=Board
;
define_jogada(J,Mov,Board),
write(Mov),
execute_move(J, Mov, Board, NewBoard)
), nl, !,
(acabou(J,NewBoard), fim(NewBoard) ; outro_jog(J,J2), joga(J2,NewBoard)).
/* Define uma jogada para o jogador 1 - Humano! Pede-lhe a posicao X,Y de onde
sai a peca e a posicao X2,Y2 para onde ela vai e verifica se o movemento e\\'
valido! */
define_jogada(1,Mov,Board):-
repeat,
write(\\'X? \\'), read(X), write(\\'Y? \\'), read(Y), nl,
% write(\\'X? \\'), fread(i,0,0,X), write(\\'Y? \\'), fread(i,0,0,Y), nl,
Mov = (1,X,Y),
valid_move(1,Mov,Board).
/* Define uma jogada para o jogador 2 - Computador! Usa o predicado calcula-move
para determinar o movimento - Mov! */
define_jogada(2,Mov,Board):-
write(\\'Estou a Pensar! Aguarde um momento por favor... \\'),nl,
% ttyflush,
calcula_move(2, Mov, Board).
/* Calcula um movimento para um jogador: Quatro estrategias possiveis!
Ceguinho: Escolhe um movimento \\'a sorte!
Guloso: Escolhe o movimento que come (e cria) mais pecas!
Intelectual: Usa o minimax (simples) para determinar a melhor jogada!
Intelectual2: Usa o minimax com cortes alfa-beta (mais algumas heuristicas) */
calcula_move(2, Mov, Board):- nivel(1), ceguinho(2, Board, Mov).
calcula_move(2, Mov, Board):- nivel(2), guloso(2, Board, Mov).
calcula_move(2, Mov, Board):- nivel(3), intelectual(2, 3, Board, Mov).
calcula_move(2, Mov, Board):- nivel(4), intelectual2(2,2,Board,Mov).
calcula_move(2, Mov, Board):- nivel(5), intelectual2(3,3,Board,Mov).
/* Fim do Jogo: O outro Jogador - J e J2 nao tem jogadas possiveis */
acabou(J,Board):-
outro_jog(J,J2),
count_pieces(J,Board,V1),
count_pieces(J2,Board,V2),
V is V1+V2,!,
V==64.
/* Muda de Jogador. Se era o 1 a jogador passa a ser o 2 e vice-versa! */
outro_jog(1,2).
outro_jog(2,1).
/*******************************************************************************/
/* */
/* Escrita no Ecran do Tabuleiro (e outras coisas) */
/* */
/*******************************************************************************/
fim(Board):-
nl, write(\\'Fim do Jogo\\'), nl,
mostra_tab(Board),
count_pieces(1,Board,V1), count_pieces(2,Board,V2),
write(\\'Humano \\'), write(V1), write(\\' - Artificial \\'), write(V2), nl,
nl, venc(V1,V2), nl.
venc(V1,V2):- V1 > V2, write(\\'Venceu o Jogador Humano! Para a proxima sera diferente... \\').
venc(V1,V2):- V2 > V1, write(\\'Venceu o Jogador Artificial! Ou seja EU! Eh! Eh! Eh! \\').
venc(V1,V2):- write(\\'Isto foi um Empate mas Voce teve muita Sorte! \\').
/* Mostra o Tabuleiro: Escreve a grelha superior e mostra cada uma das linhas.
Para tal, escreve o Numero - N da linha, mostra essa linha e passa para a linha
seguinte (N+1). Mostras uma linha corresponde a escrever cada um dos seus
elementos (convertidos usando o predicado escreve). */
mostra_tab(Board):-
nl, write(\\' 1 2 3 4 5 6 7 8\\'), nl,
mostra_linhas(1,Board),
write(\\' 1 2 3 4 5 6 7 8\\'), nl,!.
mostra_linhas(_,[]).
mostra_linhas(N,[Lin|Resto]):-
write(N),
mostra_linha(Lin),
write(\\' \\'), write(N), nl,
N2 is N+1,
mostra_linhas(N2, Resto).
mostra_linha([]).
mostra_linha([El|Resto]):-
escreve(El),
mostra_linha(Resto).
/* Comverte o 0 em \\'.\\', os 1 em \\'x\\' e os 2 em \\'o\\' para ser mais agradavel
visualizar o tabuleiro! */
escreve(0):- write(\\' .\\').
escreve(1):- write(\\' x\\').
escreve(2):- write(\\' o\\').
escreve(P):- write(\\' \\'), write(P).
/*******************************************************************************/
/* */
/* Regras de Movimentacao do Jogo - OTELO */
/* */
/*******************************************************************************/
/* Determina um movimento valido de um dado jogador num dado tabuleiro ou
confirma a validade de um dado movimento. */
valid_move(J, (J,X,Y), Board):-
member_board(0,X,Y,Board),
valid_loc(X,Y),
outro_jog(J,J2),
vizinho(X,Y,X2,Y2,N),
member_board(J2,X2,Y2,Board),
pode_comer(J,J2,X2,Y2,N,Board).
/* Verifica se uma casa (X2,Y2) e\\' vizinha de uma casa (X,Y)! Para tal tem de
estar a 1 de distancia na vertical, horizontal ou diagonal! */
vizinho(X,Y,X2,Y2,1):- Y2 is Y-1, X2 is X-1.
vizinho(X,Y, X,Y2,2):- Y2 is Y-1.
vizinho(X,Y,X2,Y2,3):- Y2 is Y-1, X2 is X+1.
vizinho(X,Y,X2, Y,4):- X2 is X-1.
vizinho(X,Y,X2, Y,5):- X2 is X+1.
vizinho(X,Y,X2,Y2,6):- Y2 is Y+1, X2 is X-1.
vizinho(X,Y, X,Y2,7):- Y2 is Y+1.
vizinho(X,Y,X2,Y2,8):- Y2 is Y+1, X2 is X+1.
valid_loc(X,Y):- corner(X,Y).
valid_loc(X,Y):- edge(X,Y).
valid_loc(X,Y):- inner_square(X,Y).
valid_loc(X,Y):- outer_corner(X,Y).
valid_loc(X,Y):- outer_square(X,Y).
valid_loc(X,Y):- outer_corner2(X,Y).
/* encontra uma localizacao: corner, edge, inner square, outer square or outer corner */
corner(1,1). corner(1,8). corner(8,8). corner(8,1).
edge(X,Y):- X > 2, X <7> 2, Y <7> 2, X <7> 2, Y <7> 2, X <7> 2, Y < 7, ( X = 2 ; X = 7 ).
outer_corner(1,2). outer_corner(2,1).
outer_corner(1,7). outer_corner(2,8).
outer_corner(7,1). outer_corner(8,2).
outer_corner(8,7). outer_corner(7,8).
outer_corner2(2,2). outer_corner2(2,7). outer_corner2(7,2). outer_corner2(7,7).
/* Pode comer se a peca na direccao N for do jogador ou se for do outro jogador mas
poder comer a seguir na mesma direccao! */
pode_comer(J,J2,X,Y,N,Board):-
vizinho(X,Y,X2,Y2,N),
member_board(J,X2,Y2,Board),!.
pode_comer(J,J2,X,Y,N,Board):-
X<9, Y<9,!,
vizinho(X,Y,X2,Y2,N),
member_board(J2,X2,Y2,Board),
pode_comer(J,J2,X2,Y2,N,Board),!.
/* Determina todos os movimentos validos de um dado jogador num dado tabuleiro */
valid_moves(J, Lista_mov, Board):- findall(Mov, valid_move(J,Mov,Board), Lista_mov).
/*******************************************************************************/
/* */
/* Execucao dos Movimentos no Jogo - OTELO */
/* */
/*******************************************************************************/
/* Executa um movimento (J,X,Y) de um dado jogador J num dado tabuleiro .
Para tal, cria a peca na localizacao (X,Y) e vira todas as pecas viraveis */
execute_move(J, (J,X,Y), Board, NewBoard):-
cria_peca(J, X, Y, Board, Board2),
vira_pecas(J, X, Y, Board2, NewBoard).
cria_peca(J, X, Y, Board, Board1):- muda_board(0,J,X,Y,Board,Board1).
vira_pecas(J, X, Y, Board, Board1):-
outro_jog(J,J2),!,
findall(N,
(vizinho(X,Y,X2,Y2,N), member_board(J2,X2,Y2,Board), pode_comer(J,J2,X2,Y2,N,Board)),
Lista_viz),!,
vira_direccoes(J, X, Y, Lista_viz, Board, Board1),!.
vira_direccoes(J, X, Y, [], Board, Board).
vira_direccoes(J, X, Y, [D|Resto], Board, Board2):-
vizinho(X,Y,X2,Y2,D),
vira_direccao(J, X2, Y2, D, Board, Board1),
vira_direccoes(J, X, Y, Resto, Board1, Board2),!.
vira_direccao(J, X, Y, D, Board, Board):-
member_board(J,X,Y,Board),!.
vira_direccao(J, X, Y, D, Board, Board2):-
muda_board(J2,J,X,Y,Board,Board1),
vizinho(X,Y,X2,Y2,D),
vira_direccao(J, X2, Y2, D, Board1, Board2),!.
/* Verifica qual a peca (ou outro elemento) Peca que esta num quadrado X,Y do
tabuleiro Board. Vai buscar a Linha Y e depois a Peca X dessa Linha! */
member_board(Peca,X,Y,Board):-
member_pos_lista(Linha, Y, Board),
member_pos_lista(Peca, X, Linha).
member_pos_lista(Membro, N, Lista):-
member_pos_procura(Membro, 1, N, Lista).
member_pos_procura(Membro, N, N, [Membro|_]).
member_pos_procura(Membro, P, N, [H|T]):-
P2 is P+1,
member_pos_procura(Membro, P2, N, T).
/* Muda a peca (ou outro elemento) que esta num quadrado X,Y do tabuleiro de Peca
para Pnov. Vai copiando linhas ate chegar \\'a linha Y. Para essa linha, vai
copiando Elementos - El ate chegar ao elementoa mudar. Esse elemento e\\' mudado
de Peca para Pnov! */
muda_board(Peca,Pnov,X,Y,Board,NewBoard):-
muda_board2(1,Peca,Pnov,X,Y,Board,NewBoard),!.
muda_board2(_,_,_,_,_,[],[]).
muda_board2(Y,Peca,Pnov,X,Y,[Lin|Resto],[NovLin|Resto2]):-
muda_linha(1,Peca,Pnov,X,Lin,NovLin),
N2 is Y+1,
muda_board2(N2,Peca,Pnov,X,Y,Resto,Resto2).
muda_board2(N,Peca,Pnov,X,Y,[Lin|Resto],[Lin|Resto2]):-
N=Y, N2 is N+1,
muda_board2(N2,Peca,Pnov,X,Y,Resto,Resto2).
muda_linha(_,_,_,_,[],[]).
muda_linha(X,Peca,Pnov,X,[Peca|Resto],[Pnov|Resto2]):-
N2 is X+1,
muda_linha(N2,Peca,Pnov,X,Resto,Resto2).
muda_linha(N,Peca,Pnov,X,[El|Resto],[El|Resto2]):-
N=X, N2 is N+1,
muda_linha(N2,Peca,Pnov,X,Resto,Resto2).
/*******************************************************************************/
/* */
/* Avaliacao do Tabuleiro do Jogo - OTELO */
/* */
/*******************************************************************************/
/* Avalia o tabuleiro tendo em conta o numero de pecas do jogador J, os seus
movimentos possiveis e o numero de pecas do outro jogador */
evaluate_board(J,Board,Valor):-
evaluate_pieces(J,Board,V1),
/* count_moves(J,Board,V2), */ V2=0,
outro_jog(J,J2),
evaluate_pieces(J2,Board,V3),
/* count_moves(J2,Board,V4), */ V4=0,
(V3 == 0, V5= 1000 ; V1==0, V5= -1000 ; V5=0), !,
Valor is 10*V1+V2-10*V3-V4+V5.
evaluate_pieces(J,Board,V):-
findall(Val, ( member_board(J,X,Y,Board), evaluate_mov((J,X,Y),Val) ), Lista),
sum_list(Lista,V).
count_pieces(J,Board,V):-
findall(J, member_board(J,X,Y,Board), Lista),
length(Lista,V).
sum_list([],0).
sum_list([H|T],N):-
sum_list(T,N2),
N is N2+H.
count_moves(J,Board,V):-
valid_moves(J,Lista_mov,Board),
length(Lista_mov,V).
/* ajustar os valores para afinar o agente! */
evaluate_mov((J,X,Y),50):- corner(X,Y).
evaluate_mov((J,X,Y),10):- edge(X,Y).
evaluate_mov((J,X,Y),5):- inner_square(X,Y).
evaluate_mov((J,X,Y),5):- outer_corner(X,Y).
evaluate_mov((J,X,Y),3):- outer_square(X,Y).
evaluate_mov((J,X,Y),1):- outer_corner2(X,Y).
/*******************************************************************************/
/* */
/* Determinacao Inteligente de uma jogada */
/* */
/*******************************************************************************/
/* Determina todos os sucessores de um dado jogador num dado tabuleiro */
sucessores(J, Lista_Boards, Board):-
findall(Mov-NewBoard,
( (J==1 ; J==2),
valid_move(J,Mov,Board),
execute_move(J,Mov,Board,NewBoard) ),
Lista_Boards).
/* Determina os sucessores de um dado tabuleiro ordenados por valor para o jogador!
Desta forma, primeiro sao analisadas as jogadas mais impirtantes, o que implica
muito mais coretes alfa-beta! */
sucessores_ordenados(J, Lista_Boards, Board):-
findall(Val-(J,X,Y)-NewBoard,
( (J==1 ; J==2),
valid_move(J,(J,X,Y),Board),
execute_move(J,(J,X,Y),Board,NewBoard),
evaluate_board(1,NewBoard,Val) ),
LB1),
keysort(LB1, Lista_Boards).
/* Ceguinho: Escolhe um movimento (qq jogada valida serve) */
ceguinho(J, Board, BestMov):- valid_move(2, Mov, Board).
/* Guloso: Escolhe o melhor movimento (1 nivel da funcao de avaliacao). */
guloso(J, Board, BestMov):-
guloso(0, 1, J, Board, BestMov, Val),
wr(BestMov), wr(\\' - Val: \\'), wr(Val), wr(nl), !.
guloso(Depth, MaxDepth, J, Board, BestMov, Val):-
sucessores(J, Lista_Boards, Board),
bestguloso(Depth2, MaxDepth, J, Lista_Boards, BestMov, Val).
bestguloso(Depth, MaxDepth, J, [Mov-Board], Mov, Val):-
evaluate_board(2, Board, Val),
wr(Val), wr(\\' : \\'), wr(Board), wr(nl).
bestguloso(Depth, MaxDepth, J, [Mov1-Board1|BoardList], BestMov, BestVal):-
evaluate_board(2, Board1, Val1),
wr(Val1), wr(\\' : \\'), wr(Board1), wr(nl),
bestguloso(Depth, MaxDepth, J, BoardList, Mov2, Val2),
betterof(J, Mov1, Val1, Mov2, Val2, BestMov, BestVal).
/* Intelectual: Usa o Minimax sem Cortes Alfa-Beta para determinar a melhor jogada */
/* sucessores(J, Lista_Boards, Board) - Lista de boards suceesores na forma
Mov1-Board1, partindo do board Board e para o jogador J
evaluate_board(J, Board, Val) - Avalia o board Board na perspectiva do max!
MaxDepth - Maxima profundidade de pesquisa! */
intelectual(J, MaxDepth, Board, BestMov):-
intelectual(0, MaxDepth, J, Board, BestMov, Val),
wr(\\'Val: \\'), wr(Val), wr(\\' => \\'), !.
intelectual(Depth, MaxDepth, J, Board, BestMov, Val):-
sucessores(J, Lista_Boards, Board), length(Lista_Boards,L), wr(L), wr(nl),
Depth2 is Depth+1,
best(Depth2, MaxDepth, J, Lista_Boards, BestMov, Val).
best(Depth, MaxDepth, J, [Mov-Board], Mov, Val):-
minimax(Depth, MaxDepth, J, Board, _, Val), !.
best(Depth, MaxDepth, J, [Mov1-Board1|BoardList], BestMov, BestVal):-
minimax(Depth, MaxDepth, J, Board1, _, Val1), !,
wr(Val1), wr(\\' : \\'), wr(Board1), wr(nl),
best(Depth, MaxDepth, J, BoardList, Mov2, Val2),
betterof(J, Mov1, Val1, Mov2, Val2, BestMov, BestVal),
wr(BestVal), wr(\\' <=> \\'), wr(BestMov), wr(nl).
minimax(Depth, MaxDepth, J, Board, BestMov, Val):-
Depth <MaxDepth> Val1, ! ; J==1, Val0 < Val1, !. /* J==2 computador - max */
betterof(J, Mov0, Val0, Mov1, Val1, Mov1, Val1).
/* Intelectual2: Usa o Minimax com Cortes Alfa-Beta para determinar a melhor jogada */
intelectual2(J, NivelFinal, Board, BestMov) :-
alphaBeta(J, J, Board, -100000, 100000, BestMov, Val, 0, NivelFinal),
wr(\\'Val: \\'), wr(Val), wr(\\' => \\'), wr(BestMov), wr(nl), !.
alphaBeta( Jogador, JInicial, Board, Alpha, Beta, GoodPos, Val, Nivel, NivelFinal):-
Nivel <NivelFinal> Beta, !; % Maximizer attained upper bound
JInicial =:= Jogador, Val <Alpha> Alpha, !. % Maximizer increased lower bound
newBounds( Jogador, JInicial, Alpha, Beta, Val, Alpha, Val) :-
JInicial =:= Jogador, Val <Beta> Val1, ! ; JInicial =:= Jogador, Val < Val1, !.
betterOf2( Jogador, JInicial, _, _, Mov1, Val1, Mov1, Val1).
/*
wr(nl):- nl, !.
wr(X):- write(X), !.
*/
wr(_):-!.
--------------- // -----------------
