-
Notifications
You must be signed in to change notification settings - Fork 1
/
othelloOLD.pl
194 lines (161 loc) · 9.52 KB
/
othelloOLD.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
%%%%%%%%%%%%%%%%%%
% OTHELLO PROLOG %
% BRANCHEREAU C. %
% GRAVEY THIBAUT %
% DE ANDRIA Q. %
% ROB LOUIS %
% MIGNOT THOMAS %
% OECHSLIN K. %
%%%%%%%%%%%%%%%%%%
%Rules : https://www.ultraboardgames.com/othello/game-rules.php
%Heuristics : https://courses.cs.washington.edu/courses/cse573/04au/Project/mini1/RUSSIA/Final_Paper.pdf
%Objective : The goal is to get the majority of colour disks on the board at the end of the game.
%Creation of the boarding game at the begin of the play
%%The board will start with 2 black discs and 2 white discs at the centre of the board.
%%They are arranged with black forming a North-East to South-West direction.
%%White is forming a North-West to South-East direction.
%%Black always moves first.
:- writeln('Bienvenue sur Prolog_Othello-IA !').
:- dynamic(board/1).
:- retractall(board(_)).
:- writeln('Chargement des Heuristics : ').
:- [heuristic_cornersCaptured].
:- [heuristic_potential_mobility].
init :-
retractall(board(_)),
length(Board,64),
nth0(27,Board,'w'),
nth0(28,Board,'b'),
nth0(35,Board,'b'),
nth0(36,Board,'w'),
assertz(board(Board)),
writeln('Initialisation du board OK'),
displayBoard,
play('b').
%Playing turn
%%if there is no winner, we made a normal turn for the next player
%%If you cant outflank and flip at least one opposing disc, you must pass
%%your turn. However, if a move is available to you, you cant forfeit your turn.
%%if a player cannot make a valide move, he pass his turn and the opponent continues
play(_) :- sleep(1), gameover(Winner), !, format('Game is over, the winner is ~w ~n',[Winner]), displayBoard.
play(Player) :- board(Board), canMakeAMove(Board,Player), format('New turn for : ~w ~n',[Player]), displayBoard,
ia(Board,Player,Move), playMove(Board,Move,Player,NewBoard), applyIt(Board,NewBoard), switchPlayer(Player,NextPlayer), play(NextPlayer).
play(Player) :- format('Player "~w" can not play.~n',[Player]), switchPlayer(Player,NextPlayer), play(NextPlayer).
%Check if a move is still available for the player
%%find one valid move then stop backtrack
%TODO : IMPROVE PERF
canMakeAMove(Board,Player) :- setof(X, isValid(Board,Player,X), List), member(_,List).
%Get all valid moves for a player
allValidMoves(Board, Player, List) :- setof(X, isValid(Board,Player,X), List), writeln('Available Moves : '),writeln(List).
%Check if a move is valid
isValid(Board,Player,Index) :-
emptyCell(Board,Index),
(isSandwich(Board,Player,Index,top);
isSandwich(Board,Player,Index,down);
isSandwich(Board,Player,Index,left);
isSandwich(Board,Player,Index,right);
isSandwich(Board,Player,Index,diagNW);
isSandwich(Board,Player,Index,diagNE);
isSandwich(Board,Player,Index,diagSE);
isSandwich(Board,Player,Index,diagSW)).
%Check if a cell is empty
emptyCell(Board,Index) :- nth0(Index,Board,X), var(X).
%Check in all direction if there is a sandwich (at least one opposite disk then a player disk)
isSandwich(Board,Player,Index,Direction) :- switchPlayer(Player,Opponent), listDiskInDirection(Board,Index,Direction,[],[Opponent|FinalList]), check_sandwich(Player, FinalList).
%List all the disk in a precise direction from the index to the last cell of the direction
listDiskInDirection(_,Index,Direction,List,FinalList) :- \+ nextCell(Index,Direction,_), !, FinalList = List.
listDiskInDirection(Board,Index,Direction,List,FinalList) :- nextCell(Index,Direction,NextCellIndex), getDisk(Board, NextCellIndex, Disk), append(List,[Disk],NewList), listDiskInDirection(Board,NextCellIndex,Direction,NewList,FinalList).
%Get the next cell depends on the direction, false if there is no more
nextCell(CellIndex, top, NextCellIndex) :- NextCellIndex is CellIndex-8, NextCellIndex > -1.
nextCell(CellIndex, down, NextCellIndex) :- NextCellIndex is CellIndex+8, NextCellIndex < 64.
nextCell(CellIndex, left, NextCellIndex) :- Mod is CellIndex mod 8, Mod =\= 0, NextCellIndex is CellIndex-1.
nextCell(CellIndex, right, NextCellIndex) :- Mod is CellIndex mod 8, Mod =\= 7, NextCellIndex is CellIndex+1.
nextCell(CellIndex, diagNW, NextCellIndex) :- Mod is CellIndex mod 8, Mod =\= 0, X is CellIndex-9, X > -1, NextCellIndex is CellIndex-9.
nextCell(CellIndex, diagNE, NextCellIndex) :- Mod is CellIndex mod 8, Mod =\= 7, X is CellIndex-7, X > -1, NextCellIndex is CellIndex-7.
nextCell(CellIndex, diagSE, NextCellIndex) :- Mod is CellIndex mod 8, Mod =\= 7, X is CellIndex+9, X < 64, NextCellIndex is CellIndex+9.
nextCell(CellIndex, diagSW, NextCellIndex) :- Mod is CellIndex mod 8, Mod =\= 0, X is CellIndex+7, X < 64, NextCellIndex is CellIndex+7.
%Get the disk at a precise index
getDisk(Board, Index, Disk) :- nth0(Index, Board, Disk).
%Check if its a sandwich or not
check_sandwich(_, []) :- !, fail.
check_sandwich(_, [H|_]) :- var(H), !, fail.
check_sandwich(Player, [H|_]) :- H == Player.
check_sandwich(Player, [H|T]) :- H \== Player, check_sandwich(Player,T).
%Play a regular move
playMove(Board, Move, Player, NewBoard) :- nth0(Move,Board,Player), flipAll(Board,Move,Player,List), writeln('Liste a remplacer depuis flipAll :'),writeln(List),majBoard(Board,Player,List,NewBoard),!.
%Get the list of all flipped disk
flipAll(Board,Move,Player,List) :-
flip(Board,Move,Player,top,L1),
flip(Board,Move,Player,down,L2),
flip(Board,Move,Player,left,L3),
flip(Board,Move,Player,right,L4),
flip(Board,Move,Player,diagNE,L5),
flip(Board,Move,Player,diagNW,L6),
flip(Board,Move,Player,diagSE,L7),
flip(Board,Move,Player,diagSW,L8),
append([L1,L2,L3,L4,L5,L6,L7,L8],List),!.
%Try to Flip in a precise direction, give the flipped disk index (FinalList)
flip(Board,Move,Player,Direction,FinalList) :-
switchPlayer(Player,Opponent),
listDiskInDirection(Board,Move,Direction,[],CompleteDiskList),
((\+(member(_,CompleteDiskList)) ; [H|_] = CompleteDiskList, \+(H==Opponent)) -> FinalList = [] ;
[_|DiskList] = CompleteDiskList,
checkSandwichEmptyList(Player, DiskList, List), (\+ member(_,List) -> FinalList = [] ;
countAlignedDisk(Player, DiskList, 1, FinalValue), flipNDisk(Move, Direction, FinalValue, [], FinalList))).
%Count the number of aligned disk (of the same color) on the list
countAlignedDisk(_,[], Value, FinalValue) :- FinalValue is Value, !.
countAlignedDisk(_,[H|_], Value, FinalValue) :- var(H), FinalValue is Value, !.
countAlignedDisk(Player,[H|_], Value, FinalValue) :- H == Player, FinalValue is Value, !.
countAlignedDisk(Player, [H|T], Value, FinalValue) :- H \== Player, X is Value+1, countAlignedDisk(Player, T, X, FinalValue).
%Give the index list of n disk in a precise direction
flipNDisk(_, _, 0, List, FinalList) :- FinalList = List, !.
flipNDisk(Index, Direction, N, List, FinalList) :- nextCell(Index, Direction, NextCellIndex), N1 is N-1, append(List, [NextCellIndex], NewList), flipNDisk(NextCellIndex, Direction, N1, NewList, FinalList).
%Check sandwich which return an empty list if false
checkSandwichEmptyList(_, [], List) :- !, List = [].
checkSandwichEmptyList(_, [H|_], List) :- var(H), !, List = [].
checkSandwichEmptyList(Player, [H|_], List) :- H == Player, List = [true].
checkSandwichEmptyList(Player, [H|T], List) :- H \== Player, checkSandwichEmptyList(Player,T, List).
%Maj the board with by flipping the disk in the list
majBoard(Board,_,[],NewBoard) :- NewBoard = Board, !.
majBoard(Board,Player,[H|T],NewBoard) :- replace(Board,H,Player,BoardUpdated), majBoard(BoardUpdated,Player,T,NewBoard).
%Replace an element at a given index to another element
replace([_|T], 0, X, [X|T]).
replace([H|T], I, X, [H|R]):- I > -1, NI is I-1, replace(T, NI, X, R), !.
%Implement IA
%%TODO : Different algorithm, here is a random move from the list
ia(Board,Player, Move) :- allValidMoves(Board,Player,List), length(List,Length), random(0,Length, Index), nth0(Index,List,Move), format('IA plays move number ~w ~n',[Move]),!.
%Save the new board and remove the old one from the knowledge base
applyIt(Board,NewBoard) :-
retract(board(Board)),
assertz(board(NewBoard)).
%Switch player
switchPlayer('b','w').
switchPlayer('w','b').
%End of the game
%%When it is no longer possible for either player to move, the game is over.
%%The discs are now counted and the player with the majority of his or her color
%%discs on the board is the winner.
%%A tie is possible.
gameover(Winner) :- board(Board), \+ canMakeAMove(Board,'w'), \+ canMakeAMove(Board,'b'), findWinner(Board,Winner).
%Find the winner
findWinner(Board, Winner):- countDisk(Board,0,0,B,W), selectWinner(B,W,Winner),
format('~w black disks against ~w white disks.~n',[B,W]).
%Count the number of disk for each player B and W
countDisk([],B,W,FinalB,FinalW) :- FinalB is B, FinalW is W.
countDisk([H|T],B,W,FinalB,FinalW) :- H == 'b', X is B+1, countDisk(T,X,W,FinalB,FinalW).
countDisk([H|T],B,W,FinalB,FinalW) :- H == 'w', Y is W+1, countDisk(T,B,Y,FinalB,FinalW).
countDisk([_|T],B,W,FinalB,FinalW) :- countDisk(T,B,W,FinalB,FinalW).
countDiskPerPlayer([],_,NbDisk,FinalNbDisk) :- FinalNbDisk is NbDisk.
countDiskPerPlayer([H|T],Player,NbDisk,FinalNbDisk) :- H == Player, X is NbDisk+1, countDiskPerPlayer(T,Player,X,FinalNbDisk).
countDiskPerPlayer([_|T],Player,NbDisk,FinalNbDisk) :- countDiskPerPlayer(T,Player,NbDisk,FinalNbDisk).
%Select the winner depends on B and W the count of the disk
selectWinner(B,W,Winner) :- B=:=W, Winner='Draw'.
selectWinner(B,W,Winner) :- B=\=W, B<W, Winner='White'.
selectWinner(B,W,Winner) :- B=\=W, B>W, Winner='Black'.
%Display the othello board
displayBoard :- writeln('--------'), board(Board), displayRow(Board,0), writeln('--------').
displayRow([],_) :- writeln('').
displayRow(Board,8) :- writeln(''), displayRow(Board,0).
displayRow([H|T],X) :- Y is X+1, display(H), displayRow(T,Y).
display(Elem) :- var(Elem), write('O').
display(Elem) :- write(Elem).