三目並べを再帰関数（バックトラック）で解いてみました。
三目並べ
三目並べは、非常に簡単なゲームです。子供のころに楽しんだ人も多いのではないでしょうか。わたしは、「マルペケ」とか「マルバツ」と呼んでいました。英語では、”Tic tac toe” と呼ぶようです。
先手（○）と後手（×）がお互い最善手を選択すると、引き分けになります。
バックトラックで解いてみる
三目並べは、手番をパスすることがないため盤面が分かれば、○が勝っているか、×が勝っているか、引き分けなのか、まだ置ける場所があるのか判定できます。
判定関数 judge は、盤面の状態を入力として、勝負の結果を返します。勝負の結果を、RESULT 型を enum で定義しました（6行目）。コードは長いですが、横縦斜めと空きマスを判定しているだけです。
再帰関数 rec を用いてゲームの最終的な勝ち負けを判定します。最初に判定関数 judge を呼び出し、まだ置ける場所がある場合に次の手を探して置きますす。一度置いた石は、元に戻します（79行目）。バックトラックと呼ばれる手法です。
最終的な勝ち負けについては、以下の手順で処理します。
- 先手（○）の手番の場合
- 選択できる手番で、○勝ちがあれば、その手を選べばよいので、先手勝ちとなります。
- 次に引き分けがあれば、その手を選べばよいので、引き分けとなります。
- どれを選択しても、×勝ちであれば、後手勝ちとなります。
- 後手（×）の手番の場合
- 選択できる手番で、×勝ちがあれば、その手を選べばよいので、後手勝ちとなります。
- 次に引き分けがあれば、その手を選べばよいので、引き分けとなります。
- どれを選択しても、○勝ちであれば、先手勝ちとなります。
Main 関数は、盤面を初期化して rec を呼び出すだけです。以下が、C＋＋プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
typedef enum {O_WIN, X_WIN, DRAW, NOTYET} RESULT;
typedef enum {O, X, EMPTY} BOARD;
RESULT judge(vector<BOARD> b)
{
RESULT result = NOTYET;
// column
for (int i = 0; i < 3; ++i) {
if ((b[3 * i] == b[3 * i + 1])&&(b[3 * i] == b[3 * i + 2])) {
if (b[3 * i] == O) {
result = O_WIN;
} else if (b[3 * i] == X) {
result = X_WIN;
}
}
}
// row
for (int i = 0; i < 3; ++i) {
if ((b[i] == b[i + 3])&&(b[i] == b[i + 6])) {
if (b[i] == O) {
result = O_WIN;
} else if (b[i] == X) {
result = X_WIN;
}
}
}
// diagonal
if (((b[0] == b[4])&&(b[0] == b[8]))
||((b[2] == b[4])&&(b[2] == b[6]))) {
if (b[4] == O) {
result = O_WIN;
} else if (b[4] == X) {
result = X_WIN;
}
}
if (result != NOTYET) {
return result;
}
bool done = true;
for (int i = 0; i < 9; ++i) {
if (b[i] == EMPTY) {
done = false;
}
}
if (!done) {
result = NOTYET;
} else {
result = DRAW;
}
return result;
}
RESULT rec(int n, vector<BOARD> b)
{
RESULT result;
result = judge(b);
if (result == NOTYET) {
bool this_o = false;
bool this_x = false;
bool this_draw = false;
for (int i = 0; i < 9; ++i) {
RESULT this_result = NOTYET;
if (b[i] == EMPTY) {
if (n % 2 == 0) {
b[i] = O;
} else {
b[i] = X;
}
this_result = rec(n + 1, b);
b[i] = EMPTY;
}
if (this_result == O_WIN) {
this_o = true;
}
if (this_result == X_WIN) {
this_x = true;
}
if (this_result == DRAW) {
this_draw = true;
}
}
if (n % 2 == 0) {
if (this_o) {
result = O_WIN;
} else if (this_draw) {
result = DRAW;
} else {
result = X_WIN;
}
}
if (n % 2 == 1) {
if (this_x) {
result = X_WIN;
} else if (this_draw) {
result = DRAW;
} else {
result = O_WIN;
}
}
}
return result;
}
int main()
{
vector<BOARD> b(9, EMPTY);
RESULT result = rec(0, b);
if (result == O_WIN) {
cout << "O WIN" << endl;
} else if (result == X_WIN) {
cout << "X WIN" << endl;
} else if (result == DRAW) {
cout << "DRAW" << endl;
}
return 0;
}プログラムの結果は、「DRAW」と出力されました。
結果を検証する
プログラム自体は1行の結果しか出力しないため、正しく動作しているか分かりません。
最初の手（○）をどこに置いても勝敗は確定しません。次の手（×）をどこに置くかによって、3手目の時点で、○ の勝ちが確定する場合があります。
3点目の時点で、○ の勝利が確定する場合を検証してみます。プログラムを改造してログを出力して確かめました。
最初の手（○）を左上に置いた場合
次の手（×）を真ん中以外に置いた場合は、○の勝ちとなります。
最初の手（○）を中上に置いた場合
次の手（×）を以下に置いた場合は、○の勝ちとなります。
最初の手（○）を真ん中に置いた場合
次の手（×）を以下に置いた場合は、○の勝ちとなります。
それぞれの結果を頭の中で確かめると、このプログラムは正しく動作しているようです。
最後に
簡単なゲームをバックトラックを使って解いてみました。勉強になりました。
