Problem
Minimax ist die Art, wie Spielprogramme Züge wählen: Nimm an, dass beide Spieler perfekt spielen, bewerte jedes beendete Spiel und gib die Bewertungen im Spielbaum nach oben weiter. Der Spieler am Zug wählt das Kind mit der für ihn höchsten Bewertung.
Das Brett ist eine Zeichenkette aus 9 Zeichen, zeilenweise gelesen (Indizes 0-8), mit "X", "O" oder "." für ein leeres Feld. X zieht immer zuerst, also ist X am Zug, wenn beide gleich viele Zeichen haben, und sonst O.
Bewerte ein beendetes Spiel aus der Sicht des Spielers am Zug: +1 für einen Sieg, 0 für ein Unentschieden, -1 für eine Niederlage. Gib das leere Feld zurück, dessen Zug die beste Minimax-Bewertung hat; sind mehrere gleich gut, gib den kleinsten Index zurück.
Implementiere best_move(board).
Eingabe
board: Eine gültige Stellung, in der noch niemand gewonnen hat und mindestens ein Feld leer ist.
Ausgabe
Gib den Index (0-8) des besten Zugs zurück.
Einschränkungen
board hat genau 9 Zeichen, jedes ist X, O oder .
Die Stellung kann in einem echten Spiel vorkommen, niemand hat gewonnen und mindestens ein Feld ist leer
Beispiele
Eingabe:
board = "XX.OO...."
Erwartete Ausgabe:
expected = 2Eingabe:
std::string board = "XX.OO....";
Erwartete Ausgabe:
long long expected = 2;Eingabe:
string board = "XX.OO....";
Erwartete Ausgabe:
long expected = 2;Erläuterung
X und O haben je zwei Zeichen, also ist X am Zug. Ein Zug auf 2 vervollständigt die obere Reihe und gewinnt sofort (+1).
Eingabe:
board = "X..OO...X"
Erwartete Ausgabe:
expected = 5Eingabe:
std::string board = "X..OO...X";
Erwartete Ausgabe:
long long expected = 5;Eingabe:
string board = "X..OO...X";
Erwartete Ausgabe:
long expected = 5;Erläuterung
X ist am Zug. O droht, die mittlere Reihe auf 5 zu vervollständigen. Jeder andere Zug lässt O gewinnen (-1), während das Blocken auf 5 zu einem Unentschieden (0) führt, also ist die Antwort 5.
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.