%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% %% Künstliche Intelligenz - ÜBUNG 7 %% %% %% %% Sascha Birkner & Rafael Grote %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Brett-Darstellung % % A | B | C % ---+---+--- % D | E | F <=> [A,B,C,D,E,F,G,H,I] % ---+---+--- % G | H | I % % x <=> 1 % o <=> -1 % - <=> 0 % Spieler x <=> 1 % Spieler o <=> -1 % move(+Player_to_move,+Game,-New_Game,-Move) % % Zuggenerator % move(Player,Game,New_Game,Move) :- % % Zuerst werden die Eingabewerte auf Korrektheit geprüft. % member(Player,[-1,1]), % Gültige Spieler sind -1 und 1. length(Game,9), % Ein Spielbrett ist eine Liste der Länge 9. checklist(between(-1,1),Game), % Es enthält nur die Werte -1, 0 und 1. sumlist(Game,N), % Die Summe der Werte muss 0 oder 1 für Spieler -1 (N is 0; N is Player * -1), % (bzw. -1 für Spieler 1) sein. % % Jetzt kann ein Zug generiert werden. % append(A,[0|B],Game), % Finde eine 0 und append(A,[Player|B],New_Game), % ersetze sie durch die Spielernummer. % % Um später die Hauptvariante auszugeben, wird zusätzlich der Name des neu belegten % Feldes und das Spielersymbol ermittelt. % length(A,Pos), % Die Länge von A ist die neubesetzte Position. XN is (Pos mod 3) + 1, % Finde die Spaltennummer. nth1(XN,[a,b,c],X), % Ersetze Spaltennummer durch Buchstaben. Y is (Pos // 3) + 1, % Finde die Zeilennummer. replace(Player,P), % Ersetze Spielernummer durch Spielersymbol. concat_atom([X,Y,'=',P],Move). % Füge alles zusammen. % check(+Game,-Winner) % % Bewertungsfunktion % check([A,B,C,D,E,F,G,H,I],Winner) :- % % Erstelle Liste mit allen Gewinnkombinationen. % L = [[A,B,C],[D,E,F],[G,H,I], % waagerecht [A,D,G],[B,E,H],[C,F,I], % senkrecht [A,E,I],[G,E,C]], % diagonal % % Prüfe, ob eine davon mit drei Symbolen eines Spielers belegt ist. % maplist(sumlist,L,S), % Bilde Summen der Gewinnreihen. (X is 3; X is -3), % Wir suchen nach einer 3 bzw. -3. member(X,S), % Und haben sie gefunden :-) !, % Es gibt immer nur ein Ergebnis! Winner is X/3. % Der Sieger ergibt sich aus dem Vorzeichen. % % Bisher hat keiner gewonnen. Falls alle Felder belegt sind, gibt es ein Remis. % check(Game,0) :- not(member(0,Game)). % minmax(+Player_to_move,+Game,-Moved_Game,-Value,-Hauptvariante) % % Implementierung des minmax-Algorithmus mit Speicherung der Hauptvariante (HV). % % Wenn die wir uns in einer terminalen Stellung befinden, geben wir das Ergebnis der % Bewertungsfunktion zurück. % minmax(_,Game,_,Value,[Winner_Str]) :- check(Game,Value), !, replace(Value,Winner), concat_atom([Winner,' gewinnt'],Winner_Str). % minmax(Player,Game,Moved_Game,Value,HV) :- % % Es werden alle möglichen Zugvarianten erzeugt. % Next_Player is Player * -1, % zuerst Spielerwechsel findall(mv(Value,New_Game,[Move|HV1]), % zu jedem Zug HV speichern (move(Player,Game,New_Game,Move), % Zug generieren und minmax(Next_Player,New_Game,_,Value,HV1)), % minmax auf ihm aufrufen Possible_Moves), % Liste aller Varianten % % Jetzt wird der Hauptvariante bestimmt. % best_move(Player,Possible_Moves,mv(Value,Moved_Game,HV)). % % Je nach Spieler führt der beste Zug zu einem Minimum oder Maximum. % best_move(_,[Move],Move). best_move(Player,[Move1,Move2|Rest],Best_Move) :- better_move(Player,Move1,Move2,Better_Move), % Besseren Zug wählen und best_move(Player,[Better_Move|Rest],Best_Move). % rekursiv weitermachen. % better_move(Player,mv(X,G,HV),mv(Y,_,_),mv(X,G,HV)) :- ((Player is 1, X > Y); % Spieler 1 sucht Maximum (Player is -1, X < Y)), !. % Spieler 2 sucht Minimum better_move(_,_,Better_Move,Better_Move). % Der zweite Wert ist besser. % print_game(+Game) % % Ausgabe des Spielbretts % print_game([A,B,C,D,E,F,G,H,I]) :- write(' a b c'), nl, write(' 1'), p(A), p(B), p(C), nl, write(' 2'), p(D), p(E), p(F), nl, write(' 3'), p(G), p(H), p(I). % % Shortcut für die Ausgabe von Symbolen % p(Code) :- replace(Code,Symbol), write(' '), write(Symbol). % % Ersetze -1,0,1 durch o,-,x % replace(1,x). replace(0,-). replace(-1,o). % tictactoe(+Player,+Start_Game,-Moved_Game,-Winner) % % Ruft minmax auf und gibt die Startstellung, den Computerzug sowie die Hauptvariante % aus. Standardwerte für den Aufruf sind Spieler x und ein leeres Feld. % tictactoe :- tictactoe(1,[0,0,0,0,0,0,0,0,0],_,_). % tictactoe(Player,Game,Moved_Game,Winner) :- minmax(Player,Game,Moved_Game,Winner,HV), % Ermittle HV durch minmax. write('Startstellung:'), nl, print_game(Game), nl, % Drucke Brett vor dem Zug. write('Computerzug:'), nl, print_game(Moved_Game), % Drucke nach dem Zug. concat_atom(HV,', ',HV_string), % Trennung der Züge in HV durch Kommata write(' Hauptvariante: '), write(HV_string), nl. % Drucke HV. % play(+My_Player,+Start_Game) % % Startet ein Spiel gegen den Computer. % play :- play(1,[0,0,0,0,0,0,0,0,0]). % % Zuerst wird geprüft, ob das Spiel vielleicht schon beendet ist. % play(My_Player,Game) :- finished(My_Player,Game), !. % % Es folgen Spieler- und Computerzug und die entsprechende Ausgabe. % play(My_Player,Game) :- nl, write('Wie lautet Dein Zug? '), read(Target), nl, % Lese Benutzereingabe replace(My_Player,My_Symbol), % Bestimme Spielersymbol concat_atom([Target,'=',My_Symbol],Move), % Baue daraus Zugbezeichnung move(My_Player,Game,Moved_Game,Move), % Führe den Benutzerzug aus !, % Benutzerzug ist hier beendet not(finished(My_Player,Moved_Game)), % Prüfe, ob Spiel beendet Computer_Player is My_Player * -1, % Bestimme Computerspieler tictactoe(Computer_Player,Moved_Game,Next_Game,_), % Computerzug und Ausgabe play(My_Player,Next_Game). % Nächste Runde % % Falls das letzte Prädikat während der Eingabe oder Ausführung des Benutzerzuges % fehlgeschlagen ist, wird es nochmal mit den gleichen Parametern aufgerufen. So hat % der Spieler die Möglichkeit, eine falsche Eingabe zu korrigieren. % play(My_Player,Game) :- write('Die Eingabe war nicht korrekt oder das Feld ist schon belegt.'), nl, write('Eingaben immer mit einem Punkt abschliessen. Beispiel: a3.'), nl, play(My_Player,Game). % % Hilfsprädikat, zum Prüfen, ob das Spiel beendet ist. % Gibt das Brett und eine Siegmeldung aus. % finished(My_Player,Game) :- check(Game,Winner), nl, print_game(Game), write(' '), ((Winner is My_Player, write('Du hast gewonnen :-)')); (Winner is My_Player * -1, write('Du hast verloren :-(')); (Winner is 0, write('Remis :-|'))).