大学の課題でαβ法を使ったオセロAIを作れなかった話

おはようございます。S大学工学部情報工学科のreika727と申します。
先日院試も無事に終わり4月から修士課程に入るのですが、学部時代の課題で印象的だったのが「プログラミング演習Ⅲ」の最終レポートでした。そのレポート課題というのが

OpenGLを使用し、インタラクティブなGUIアプリケーションを作成せよ

というもの(だったと思う)でした。
そこで私は当時取っていた「人工知能」という講義で得た知識も活用し、αβ法によるAIを搭載した1人用オセロプログラムを作成することにしました。以下はそのオセロAIを作り損ねた記録です。

ミニマックス法

まずαβ法とはなんじゃらほいって話なんですが、αβ法はミニマックス法を改善したアルゴリズムです。そのミニマックス法はざっくり説明すると「想定される最大の損害が最小になる」ような手を考えます。以下もっと具体的に説明していきます。

まずオセロというゲームはプレイヤーが交互に石を打つことでゲームが進行していくので、各プレイヤーが各手番で盤上のどこに石を打つかで状況は分岐していくことになります。この分岐を図で表したものをゲーム木といいます。

次にゲーム木上に現れる盤面に「点数」を割り振ることを考えます。つまり、自分にとって有利な盤面は高い点数を、自分にとって不利な盤面は低い点数を持つようにします。このように盤面に得点を割り振る関数を評価関数といいます。
ゲームAIを作るにあたってこの評価関数は非常に重要なものです。たとえ最善手の探索アルゴリズムが全く同一のものであったとしても、評価関数の性能次第でAIの出来は大きく変わってきます。しかしあまり深入りしすぎると難しくなりすぎるので、ここはシンプルに行きましょう。オセロの簡単な評価関数としては以下のものがよく用いられます。

\begin{matrix}
  120 & -20 & 20 & 5 & 5 & 20 & -20 & 120 \\
  -20 & -40 & -5 & -5 & -5 & -5 & -40 & -20 \\
  20 & -5 & 15 & 3 & 3 & 15 & -5 & 20 \\
  5 & -5 & 3 & 3 & 3 & 3 & -5 & 5 \\
  5 & -5 & 3 & 3 & 3 & 3 & -5 & 5 \\
  20 & -5 & 15 & 3 & 3 & 15 & -5 & 20 \\
  -20 & -40 & -5 & -5 & -5 & -5 & -40 & -20 \\
  120 & -20 & 20 & 5 & 5 & 20 & -20 & 120
\end{matrix}

これの見方ですが、まずこの謎の行列は見ての通りオセロ盤とおなじ8x8の大きさになっています。ここで自分の石が置かれているマスの点の総和を「自分の得点」、相手の石が置かれているマスの点の総和を「相手の得点」とし、「自分の得点」-「相手の得点」を(自分から見た)盤面の得点と定義します。
よく「オセロは角を取ると強い」と言われますが、この評価関数にもそのことが現れています。四隅にあるマスの点は120点と非常に高くなっているのがわかりますね。
一方その四隅のマスを取り囲むマスたちは点数が非常に低くなっています。これは自分がそのマスに石を置いてしまうと相手に四隅のマスを取られてしまう可能性があるからですね。

次にミニマックス法の詳細について説明します。ミニマックス法を使うときは、まず「何手先まで読むのか」を決めます。当然読む手数が多いほどAIは強くなりますし、終局まで読めば最強のAIが作れてしまいますが、読む手数が多いだけ時間もメモリも消費することになります。

Wikipediaによるとオセロのゲーム木の大きさは約$10^{58}$と非常に大きく、ゲームの完全解析も未だなされていないそうです。
ところでそんなオセロは「二人零和有限確定完全情報ゲーム」に分類されます。

• 二人: プレイヤーが二人であること。言うまでもなくオセロは二人用ゲームですね。
• 零和: 一方のプレイヤーにとっての利得は他方のプレイヤーにとって(同程度の)損失であること。オセロでも自分が石を取るほど相手は不利になりますね(逆もまた然り)。
• 有限: ゲーム木の大きさが有限であること。オセロはどんなに長くても必ず60手以内で決着するので有限ゲームです。
• 確定: 各プレイヤーの手の決定に運要素が存在しないこと。例えばすごろくはさいころを使うので確定ゲームではありません。
• 完全情報: 各プレイヤーが意思決定をするときに「それまでの試合で起こった全てのこと」がわかること。例えばポーカーは「相手は今までにどんなカードを引いてきたのか」がわからない状態で意思決定をしなければならないので、完全情報ゲームではありません。またじゃんけんのような「同時手番ゲーム」も、「相手がどの手を出すのか」が分からないまま自分の手を決めなければならないので完全情報ゲームではありません。

二人零和有限確定完全情報ゲームは、2人のプレイヤーがどちらも最善手を打ち続けた場合「先手が必ず勝つ」か「後手が必ず勝つ」か「必ず引き分けになる」かのどれかになります。すでに分類が明らかになっているゲームの例としては以下が挙げられます。

• 先手必勝: 禁じ手のない五目並べ
• 後手必勝: どうぶつ将棋・6x6のオセロ
• 引き分け: 三目並べ・チェッカー

上に書かれているように6x6のオセロはすでに解析されているのですが、通常のオセロ(8x8)はまだ解析されていません。しかしこれまでの研究の結果、8x8のオセロは「たぶん引き分けになるんじゃないかな」と予想されているそうです。

ここではとりあえず3手先まで読むことにしましょう。このとき、まずは「3手先の盤面」として考えられるすべてのものに対し評価関数を用いて得点を計算します。

ここでは3手先、つまり相手が石を打とうとしているときの盤面の得点としては1, 3, 6, 9, 2, 4, 5, 1, 2, 7, 8, 2の12通りあるということになりました。

ここでオセロを打つときの気持ちを考えてみましょう。自分が石を打って相手に番を回すときには、可能な限り自分に有利な状態にしてから相手の番にしたいはずです。つまり自分が石を打った結果の盤面の得点として1, 3, 6があり得るならば、選ぶべきなのは当然6点の盤面です。

同様に石を打ったときの結果の盤面として9, 2, 4があり得るならば選ぶべきなのは9点、5, 1, 2があり得るならば選ぶべきなのは5点、7, 8, 2があり得るならば選ぶべきなのは8点となります。

というわけで下から2番目の列が埋まりました。
ここで勘違いしてほしくないのは、一番下の列、つまり四角形で囲まれた数は評価関数によって計算された「盤面の得点」ですが、そこ以外の列、つまり楕円形で囲まれた数は「盤面の得点」ではないということです。ここでは「盤面の得点」との混同を避けるため、「状況の得点」とでも呼ぶことにしましょうか。

さらに細かいことを考えると、今埋めた下から2番目の列の数たちは「その時点から1手先まで読んだ上での状況の得点」とも捉えられます。同様に今から埋めていく下から3番目の列の数たちは「その時点から2手先まで読んだ上での状況の得点」、一番上の数は「その時点から3手先まで読んだ上での状況の得点」となります。
この考え方でいくならば一番下の列の数、つまり盤面の得点は「その時点から0手先まで読んだ上での状況の得点」ともいえます。つまり今回用いた評価関数は、先読みを一切せずに盤面の得点を計算する関数ということになります。ゲーム理論においてこのような関数は「静的評価関数」と呼ばれます。

さて、今度は対戦相手の気持ちを考えてみます。対戦相手が石を打って番を回すときには可能な限りこちらが不利な状態にしたがるはずです。よって、相手は「状況の得点」が一番低くなる選択をしてくるはずだと考えられます。したがって相手が石を打ったときの状況の得点として6, 9があり得るならば相手が選んでくるのは6点の状況、5, 8があり得るならば相手が選んでくるのは5点の状況です。

あとは同じことの繰り返しです。今度はさっきと同じく自分に有利な状況を選択します。なので3手先まで読んでみた上での最終的な結論としては、赤矢印で示された選択をするべきである、ということになります。

もちろんこれは「3手先まで読んでみた上での結論」です。4手先まで読んでみれば違う結論が出てくるかもしれません。

αβ法

今説明したミニマックス法を改良したものがαβ法になります。改良したとはいっても、導かれる結論自体はミニマックス法と同じものです。αβ法はミニマックス法の計算量を改善したものになります。

さて、ひとまずはミニマックス法と同じ要領でここまで計算できたとしましょう。

次に「3手先の盤面としてあり得るもの」の4つ目を計算します。先ほど見た通りここは9点となります。

重要なのがここからの推論です。ミニマックス法の説明のときにも述べたように、自分の手番のときは「可能な限り自分に有利な状況」になる手を打ちます。なので、「自分が石を打った結果9点の状況にできる状況」の得点は小さくとも9以上になるはずです。

相手の立場からすれば、「6点の状況」と「小さくとも9点の状況」であれば選択するのは言うまでもなく6点の状況です。そういうわけで「小さくとも9点の状況」に関してこれ以上の探索は打ち切っても問題ないことがわかります。いわゆる枝刈りというやつですね。このように状況の得点の下限が定まったときに行う枝刈りをαカットといいます。

ここからまたしばらくミニマックス法と同じ要領で進めていきます。

さて、ここでさきほどと似た推論をします。相手は石を打つときにこちらが不利な状況にしたがるはずなので、「相手が石を打った結果5点の状況にできる状況」の得点は大きくとも5以下になるはずです。

自分が状況を選ぶときに「6点の状況」と「大きくとも5点の状況」であれば選択するのは言うまでもなく6点の状況です。そういうわけで「大きくとも5点の状況」に関してこれ以上の探索は打ち切っても問題ないことがわかります。このように状況の得点の上限が定まったときに行う枝狩りをβカットといいます。

最終的にはミニマックス法と同じ結論が導かれます。しかし無駄な探索を削減したので計算量は減っています。

完成品

完成品がこんな感じになりました。OpenGLにはティーポットを描画する関数があるのでそれを石代わりに使ってみました。

コンピュータグラフィックスの分野ではやたらティーポットが現れるのですが、そのはじまりはユタ大学のマーティン・ニューウェルさんだそうです。コンピュータグラフィックスの黎明期、ニューウェルさんは仕事で使うモデルとして単純すぎず複雑すぎない形状の物体を探していました。最終的には奥さんの勧めでティーポットをモデリングしたそうです。このティーポットはニューウェルさんの名前を取ってニューウェル・ティーポット、もしくは大学の名前を取ってユタ・ティーポットと呼ばれます。

自分で言うのもなんですがなかなかの自信作でした。結果、最高評価Sをいただきました。

今回のオチ

いやーよかったよかった。せっかく力を入れて書いたソースコードだし、もう一度眺めてみるとしよう。

/**
 * @fn
 * @brief αβ法を用いて算出された最善の手を打つ。
 * @param board 現在のオセロ盤。
 * @param stone 打つべき石の種類。白と黒の2種類のどれか。
 * @param depth αβ法における読みの深さ。
 * @return αβ法を用いて求められた最適解に基づきboardに石を打ち、その石の座標を返却する。
 */
othello::board::coordinate play_best_hand(othello::board &board, const othello::stone &stone, unsigned int depth)
{
    // board上でstoneを置くことが可能な座標の一覧
    auto puttable_places = board.get_puttable_places(stone);
    // stoneを置ける場所がなければ例外を投げる
    if (puttable_places.empty()) {
        throw othello::board::operation_error("no puttable place");
    }
    // αβ法に基づいて算出された最適座標(が入る予定の変数)
    othello::board::coordinate best_place;
    // stoneを置ける場所を総当たりしていき、状況の得点が最大になる場所を探す
    auto score = std::numeric_limits<int>::min();
    for (const auto &pp : puttable_places) {
        auto board_copy = board.get_put(pp, stone);
        if (auto new_score = alpha_beta(board_copy, stone, depth); new_score > score) {
            best_place = pp;
        }
    }
    // 最適座標に石を打ってその座標を返却する
    board.put(best_place, stone);
    return best_place;
}

・・・ん？

// stoneを置ける場所を総当たりしていき、状況の得点が最大になる場所を探す
auto score = std::numeric_limits<int>::min();
for (const auto &pp : puttable_places) {
    auto board_copy = board.get_put(pp, stone);
    if (auto new_score = alpha_beta(board_copy, stone, depth); new_score > score) {
        best_place = pp;
    }
}

・・・あれ？

if (auto new_score = alpha_beta(board_copy, stone, depth); new_score > score) {
    best_place = pp;
    // ここでscore = new_scoreしないといけない
}

（　Д　） °　°

私の提出したプログラムは、石を打てるマスの中で一番右下にあるマスに打つだけのプログラムとなっていました。テストプレイのときそんなのにボロ負けし続けていた私とはいったい・・・

教訓

ソースコードはリリースの前に何度でも見返しましょう。