Tictactoe

Bei unserer KI werden wir auf eine Minmax-Engine setzen, d.h. wir werden den Computer alle möglichen Züge vorrausberechnen lassen. Bei Tictactoe gibt es nur 549945 Züge, die der Computer berechnen muss - und das auch nur, wenn das Spiel gerade beginnt und der Computer anfängt, später sind es viel weniger Züge.
Im Beispielcode gehe ich davon aus, das es eine Struktur BOARD gibt, die die Member getResult(), isFull(), isValidMove(int move), makeMove(int player, int move) und eraseMove(int move) hat. Player ist dabei 1 für den ersten Spieler und -1 für den zweiten Spieler, move eine Zahl von 0 bis 8.
Als Rückgabewert haben wir dann den besten Zug. Nur wie berechnen wir ihn?

Ganz einfach: wir geben einfach jedem Zug eine Zahl. 1 für Sieg, -1 für Niederlage, den Durchschnitt für Züge, nach denen das Spiel nicht beendet ist.

Nun lasst uns den Code Stück für Stück durchgehen:

int solve(BOARD b, int player, int &wins, int &looses, float &moves) {
	int best=-1;
	float best_result;
	int move;
	float rank;
	int w=0, l=0;
	moves = 0;

Unsere Funktion heißt solve und bekommt das Spielbrett, den aktuellen Spieler und drei Variablen, die zur Übergabe von weiteren Werten benutzt werden, als Rückgabe gibt es dann den besten Zug.
Die Variablen w und l stehen für die Siege und Niederlagene, moves für die Anzahl der möglichen Züge, move für den aktuellen Zug.

	for(move=0; move<9; move++) {
		if(!b.isValidMove(move)) continue;

		moves_possible++;
		b.makeMove(player, move)

Wir gehen alle Züge durch. Als erstes überprüfen wir, ob der Zug möglich ist, wenn ja, machen wir den Zug und setzen den Zähler um eins höher.

		if(b.getResult() == player) {
			w++;
			if(best == -1  ||  best_result < 1) {
				best = move;
				best_result = 1;
			}
		}

Nun überprüfen wir, ob der Spieler gewonnen. Wenn ja, erhöhen wir die Anzahl der Siege und, falls bisher nur schlechtere Ergebnisse erzielt wurden, speichern wir diesen Zug als bisher besten.

		else if(b.isFull()) {
			if(best == -1  ||  best_result < 0) {
				best = move;
				best_result = 0;
			}
		}

Falls der Spieler nicht gewonnen hat, gucken wir, ob es nicht ein Unentschieden gibt. Diesen Zug bewerten wir mit 0.

		else {
			solve(b, -player, wins, looses, moves)

			l += wins;
			w += looses;
			moves_possible += moves

			rank = (looses-wins)/moves;
			if(best == -1  ||  best_result < rank) {
				best = move;
				best_result = rank;
			}
		}

Wenn weder der Spieler gewonnen hat, noch ein Unentschieden eingetreten ist, starten wir unsere Funktion nochmal für den anderen Spieler. Dann zählen wir die Siege des Gegners als Niederlagen für uns dazu und umgekehrt. Danach berechnen wir eine Bewertung für diesen Zug.

		b.eraseMove(move);
	}

	wins = w;
	looses = l;
	moves = moves_possible;
	return best;
}

Nun machen wir unseren Zug rückgängig und wiederholen das ganze für die anderen Züge. Dann setzen wir die Variablen, die übergeben werden und liefern den besten Zug zurück.

So, das wars schon. Hier gibt es nochmal den ganzen Source für die KI