Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Lösungsbeispiel Minimax
Ist das Lösungsbeispiel vom Minimax-Algorithmus schon irgendwo online verfügbar?
Ich würde jetzt mal diese Abgabe posten, die wurde von Kai empfohlen weil sie funktioniert 
Ich bin mir nicht sicher von welchem Student die ist (gerne credit claimen, falls Interesse).
%%%%% IMPORTANT %%%%%
% In order to make this program run for an entire board, set the following option:
% set_prolog_stack(local, limit(2 000 000 000)).
% The computation might take some seconds.
% A Tic-Tac-Toe program in Prolog. S. Tanimoto, May 11, 2003.
% To play a game with the computer, type
% playo.
% To watch the computer play a game with itself, type
% selfgame.
%
% original at https://courses.cs.washington.edu/courses/cse341/03sp/slides/PrologEx/tictactoe.pl.txt
% Predicates that define the winning conditions:
win(Board, Player) :- rowwin(Board, Player).
win(Board, Player) :- colwin(Board, Player).
win(Board, Player) :- diagwin(Board, Player).
rowwin(Board, Player) :- Board = [Player,Player,Player,_,_,_,_,_,_].
rowwin(Board, Player) :- Board = [_,_,_,Player,Player,Player,_,_,_].
rowwin(Board, Player) :- Board = [_,_,_,_,_,_,Player,Player,Player].
colwin(Board, Player) :- Board = [Player,_,_,Player,_,_,Player,_,_].
colwin(Board, Player) :- Board = [_,Player,_,_,Player,_,_,Player,_].
colwin(Board, Player) :- Board = [_,_,Player,_,_,Player,_,_,Player].
diagwin(Board, Player) :- Board = [Player,_,_,_,Player,_,_,_,Player].
diagwin(Board, Player) :- Board = [_,_,Player,_,Player,_,Player,_,_].
% Helping predicate for alternating play in a "self" game:
other(x,o).
other(o,x).
game(Board, Player) :- win(Board, Player), !, write([player, Player, wins]).
game(Board, Player) :-
other(Player,Otherplayer),
move(Board,Player,Newboard),
!,
display(Newboard),
game(Newboard,Otherplayer).
move([b,B,C,D,E,F,G,H,I], Player, [Player,B,C,D,E,F,G,H,I]).
move([A,b,C,D,E,F,G,H,I], Player, [A,Player,C,D,E,F,G,H,I]).
move([A,B,b,D,E,F,G,H,I], Player, [A,B,Player,D,E,F,G,H,I]).
move([A,B,C,b,E,F,G,H,I], Player, [A,B,C,Player,E,F,G,H,I]).
move([A,B,C,D,b,F,G,H,I], Player, [A,B,C,D,Player,F,G,H,I]).
move([A,B,C,D,E,b,G,H,I], Player, [A,B,C,D,E,Player,G,H,I]).
move([A,B,C,D,E,F,b,H,I], Player, [A,B,C,D,E,F,Player,H,I]).
move([A,B,C,D,E,F,G,b,I], Player, [A,B,C,D,E,F,G,Player,I]).
move([A,B,C,D,E,F,G,H,b], Player, [A,B,C,D,E,F,G,H,Player]).
display([A,B,C,D,E,F,G,H,I]) :- write([A,B,C]),nl,write([D,E,F]),nl,
write([G,H,I]),nl,nl.
selfgame :- game([b,b,b,b,b,b,b,b,b],x).
% Predicates to support playing a game with the user:
x_can_win_in_one(Board) :- move(Board, x, Newboard), win(Newboard, x).
% The predicate orespond generates the computer's (playing o) reponse
% from the current Board.
orespond(Board,Newboard) :-
move(Board, o, Newboard),
win(Newboard, o),
!.
orespond(Board,NewBoard) :-
minBoard(Board, Move, _),
move(Board, o, Move, NewBoard).
orespond(Board,Newboard) :-
move(Board, o, Newboard).
orespond(Board,Newboard) :-
not(member(b,Board)),
!,
write('Cats game!'), nl,
Newboard = Board.
%%%%% The Minimax Algorithm %%%%%
% maxBoard(OldBoard, PossibleMoves, MoveToMakeForOptimalResults, UtilityForThisMove).
maxBoard(Board, noMove, Utility) :-
utility(Board, Utility), not(Utility=none). %game already over
maxBoard(Board, Move, Utility) :-
possibleMoves(Board, PossibleMoves),
maxBoardHelper(Board, PossibleMoves, (noMove, none), Move, Utility).
% maxBoardHelper(Board, PossibleMoves, (BestMove, BestUtility), Move, Utility).
% (BestMove, BestUtility) = Best move and best Utility so far
maxBoardHelper(_, [], (BestMove, BestUtility), BestMove, BestUtility).
maxBoardHelper(Board, [PossMove|PossMoves], (BestMove, BestUtility), Move, Utility) :-
move(Board, x, PossMove, NewBoard1),
minBoard(NewBoard1, _, Utility1),
maxUtility((PossMove, Utility1), (BestMove, BestUtility), NewBest),
maxBoardHelper(Board, PossMoves, NewBest, Move, Utility).
% maxUtility((Move1, Utility1),(Move2, Utility2),(MoveX, UtilityX))
% for UtilityX = UtilityMax, X=1;2
maxUtility((_, none), V, V).
maxUtility(V, (_, none), V).
maxUtility((Move1, Utility1),(_, Utility2),(Move1, Utility1)) :- number(Utility1), number(Utility2), Utility1@>=Utility2.
maxUtility((_, Utility1),(Move2, Utility2),(Move2, Utility2)) :- number(Utility1), number(Utility2), Utility1@<Utility2.
% minBoard(OldBoard, PossibleMoves, MoveToMakeForOptimalResults, UtilityForThisMove).
minBoard(Board, noMove, Utility) :-
utility(Board, Utility), not(Utility=none). %game already over
minBoard(Board, Move, Utility) :-
possibleMoves(Board, PossibleMoves),
minBoardHelper(Board, PossibleMoves, (noMove, none), Move, Utility).
% minBoardHelper(Board, PossibleMoves, (BestMove, BestUtility), Move, Utility).
% (BestMove, BestUtility) = Best move and best Utility so far
minBoardHelper(_, [], (BestMove, BestUtility), BestMove, BestUtility).
minBoardHelper(Board, [PossMove|PossMoves], (BestMove, BestUtility), Move, Utility) :-
move(Board, o, PossMove, NewBoard1),
maxBoard(NewBoard1, _, Utility1),
minUtility((PossMove, Utility1), (BestMove, BestUtility), NewBest),
minBoardHelper(Board, PossMoves, NewBest, Move, Utility).
% minUtility((Move1, Utility1),(Move2, Utility2),(MoveX, UtilityX))
% for UtilityX = UtilityMin, X=1;2
minUtility((_, none), V, V).
minUtility(V, (_, none), V).
minUtility((Move1, Utility1),(_, Utility2),(Move1, Utility1)) :- number(Utility1), number(Utility2), Utility1@=<Utility2.
minUtility((_, Utility1),(Move2, Utility2),(Move2, Utility2)) :- number(Utility1), number(Utility2), Utility1@>Utility2.
%%%%% Further Helper Functions %%%%%
% Utility function
% 0 is draw, 1 is "x wins", -1 is "o wins", none if "game not over"
% utility(Board, UtilityForBoard)
utility(Board, -1) :- win(Board, o).
utility(Board, 0) :- draw(Board).
utility(Board, 1) :- win(Board, x).
utility(Board, none) :- not(win(Board, x)), not(win(Board, o)), not(draw(Board)).
draw(Board) :- not(existsBlank(Board)), not(win(Board, o)), not(win(Board, x)).
existsBlank([b,_,_,_,_,_,_,_,_]).
existsBlank([_,b,_,_,_,_,_,_,_]).
existsBlank([_,_,b,_,_,_,_,_,_]).
existsBlank([_,_,_,b,_,_,_,_,_]).
existsBlank([_,_,_,_,b,_,_,_,_]).
existsBlank([_,_,_,_,_,b,_,_,_]).
existsBlank([_,_,_,_,_,_,b,_,_]).
existsBlank([_,_,_,_,_,_,_,b,_]).
existsBlank([_,_,_,_,_,_,_,_,b]).
possibleMoves(Board, PossibleMoves) :- possibleMovesHelper(Board, 1, PossibleMoves).
possibleMovesHelper(_, I, []) :- I@>9.
possibleMovesHelper([b|RestBoard], I, [I|PossibleMoves]) :- J is I+1, possibleMovesHelper(RestBoard, J, PossibleMoves).
possibleMovesHelper([X|RestBoard], I, PossibleMoves) :- not(X=b), J is I+1, possibleMovesHelper(RestBoard, J, PossibleMoves).
%%%%% End of Minimax and helper functions %%%%%
% Predicates for making a single move (like xmove)
% Z is x or o
move([b,B,C,D,E,F,G,H,I], Z, 1, [Z,B,C,D,E,F,G,H,I]).
move([A,b,C,D,E,F,G,H,I], Z, 2, [A,Z,C,D,E,F,G,H,I]).
move([A,B,b,D,E,F,G,H,I], Z, 3, [A,B,Z,D,E,F,G,H,I]).
move([A,B,C,b,E,F,G,H,I], Z, 4, [A,B,C,Z,E,F,G,H,I]).
move([A,B,C,D,b,F,G,H,I], Z, 5, [A,B,C,D,Z,F,G,H,I]).
move([A,B,C,D,E,b,G,H,I], Z, 6, [A,B,C,D,E,Z,G,H,I]).
move([A,B,C,D,E,F,b,H,I], Z, 7, [A,B,C,D,E,F,Z,H,I]).
move([A,B,C,D,E,F,G,b,I], Z, 8, [A,B,C,D,E,F,G,Z,I]).
move([A,B,C,D,E,F,G,H,b], Z, 9, [A,B,C,D,E,F,G,H,Z]).
% The following translates from an integer description
% of x's move to a board transformation.
xmove([b,B,C,D,E,F,G,H,I], 1, [x,B,C,D,E,F,G,H,I]).
xmove([A,b,C,D,E,F,G,H,I], 2, [A,x,C,D,E,F,G,H,I]).
xmove([A,B,b,D,E,F,G,H,I], 3, [A,B,x,D,E,F,G,H,I]).
xmove([A,B,C,b,E,F,G,H,I], 4, [A,B,C,x,E,F,G,H,I]).
xmove([A,B,C,D,b,F,G,H,I], 5, [A,B,C,D,x,F,G,H,I]).
xmove([A,B,C,D,E,b,G,H,I], 6, [A,B,C,D,E,x,G,H,I]).
xmove([A,B,C,D,E,F,b,H,I], 7, [A,B,C,D,E,F,x,H,I]).
xmove([A,B,C,D,E,F,G,b,I], 8, [A,B,C,D,E,F,G,x,I]).
xmove([A,B,C,D,E,F,G,H,b], 9, [A,B,C,D,E,F,G,H,x]).
xmove(Board, X, Board) :- write('Illegal move: '), write(X), nl.
% The 0-place predicate playo starts a game with the user.
playo :- explain, playfrom([b,b,b,b,b,b,b,b,b]).
explain :-
write('You play X by entering integer positions followed by a period.'),
nl,
display([1,2,3,4,5,6,7,8,9]).
playfrom(Board) :- win(Board, x), write('You win!').
playfrom(Board) :- win(Board, o), write('I win!').
playfrom(Board) :- read(N),
xmove(Board, N, Newboard),
display(Newboard),
%write('foo'), writeln(Board),
orespond(Newboard, Newnewboard),
%writeln('bar'),
display(Newnewboard),
playfrom(Newnewboard).