ホームページへ戻る
第５章: ２人対戦ゲーム２人対戦型のゲームでコンピュータに次の１手を選び出させようとした時に、どのような考え方をすれば良いのか。その最も基本となるアルゴリズムがミニマックス法と呼ばれるものです。
さて、ここで「深読み名人」と言う名前の大変素晴らしい関数を紹介します。誰が作ったかは知らないが、ミニマックス法の規則に従ってゲームを完全に読み切り、両者が最善を尽した場合の勝敗を正確に判定(予想)してくれます。 ただ一つだけ欠点があって勝敗の判定はしてくれるが、次にどんな手を打てば勝てるのかは教えてくれません。 しかし、この深読み名人関数を使えば、次にどんな手を打てば勝てるのかを知るプログラムは簡単に作る事が出来ます。 総ての手をシラミ潰しに打ってみて対戦相手役の深読み名人に手を渡し、相手が「負けました」と答えた時の手が、こちらにとっては「勝てる手」になる訳です。List.5-1 深読み名人を使うことによって、こんなに簡単にプログラムが書けてしまいますが、では深読み名人なんて難しそうな関数はどうやって作れば良いのでしょうか？
今説明したプログラムそのものが、深読み名人関数と同じものなのです。深読み名人を呼び出す場所で、自分と相手の立場を逆にしてこのプログラムを「再帰呼び出し」すれば良いだけなのです。 あっけない結末ですが、本当にそうなのです。何故なら、この再帰呼び出しはゲームの勝敗が決するまで深く入り込んで全探索を行ってしまうのです。再帰ってのは本当に魔法のように便利なものですね。List.5-2
駒を置いた時の相手駒の反転処理や、またその手を元に戻す処理がちょっと面倒ですが、それ以外は先ほどの基本型に当てはめるだけです。List.5-3
ホームページへ戻る |
List.5-1
//****************************************
// 深読み名人関数を使って次の手を選択する
//****************************************
int 次の手選択()
{
if (ゲームが終了している) {
// 勝敗を調べて結果を返す。(-1:負け 0:勝ち)
if (自分が勝ち) return 0; // 勝ち
} else {
for (i=1; i<=可能な次の手の総て; i++) {
その手iを打つ;
相手の返事 = 深読み名人関数();
その手iを戻す;
// 相手が負けと答えたらこの手(i)で勝てる
if (相手の返事 == 負け) return i;
}
}
// 総ての手に対して相手が勝ちと答えたら
// こちらに勝ち目はない。
return -1; // 負け
}
List.5-2
//****************************************
// 再帰呼出しを使って次の手を選択する
//****************************************
int 次の手選択(相手)
{
自分 = 相手の反対;
if (ゲームが終了している) {
// 勝敗を調べて結果を返す。(-1:負け 0:勝ち)
if (自分が勝ち) return 0; // 勝ち
} else {
for (i=1; i<=可能な次の手の総て; i++) {
その手iを打つ;
相手の返事 = 次の手選択(自分); // 再帰呼出し
その手iを戻す;
// 相手が負けと答えたらこの手(i)で勝てる
if (相手の返事 == 負け) return i;
}
}
// 総ての手に対して相手が勝ちと答えたら
// こちらに勝ち目はない。
return -1; // 負け
}
List.5-3 例題６: ロミオゲーム |