【ITニュース解説】Building My First AI Project: Tic Tac Toe with Minimax (No ML Libraries)

システムエンジニアを目指す皆さんが、初めてのAIプロジェクトに挑戦した際の経験談を聞くと、その熱意に触発されることだろう。あるエンジニアがハーバード大学のCS50 AIコースをきっかけに、自らの手でAIプロジェクトを立ち上げた。彼が選んだのは、誰もが知るシンプルなゲーム「三目並べ（Tic Tac Toe）」で、これに「Minimax（ミニマックス）」というアルゴリズムを使ったAIをPythonで実装する、というものだった。このプロジェクトの真の目的は、単に動くゲームを作るだけでなく、AIの根幹にある概念を深く理解することにあったのだ。

CS50 AIコースでは、AIの幅広いトピックが紹介された。例えば、ある場所から別の場所へ移動する方法やゲームで最善手を見つける方法を扱う「探索」、情報を表現しそこから結論を導き出す「知識と推論」、不確実な状況で確率を用いて意思決定をする「不確実性」、単なる解決策ではなく最適な解決策を見つける「最適化」、迷惑メールを判別するように経験から性能を向上させる「学習」、そしてさらに複雑なAIタスクに使われる「ニューラルネットワークと言語処理」などだ。今回の三目並べAIのプロジェクトでは、特にゲームAIの基礎となる「探索」と、相手がいるゲームで最適な戦略を見つける「敵対的探索」に焦点を当てて学習が進められた。

実際にAIをプログラミングする前に、いくつかの重要なAIの概念を理解する必要があった。まず、「エージェント」とは、システムの中で意思決定を行う主体、つまり今回のAIプレイヤーのことだ。「状態」とは、環境のある瞬間のスナップショット、具体的には三目並べの盤面配置を指す。「アクション」は、ある状態から可能な行動、つまり盤面に「X」または「O」を置く手のことだ。「遷移モデル」は、アクションを実行したときに盤面がどのように変化するかを示す。そして「状態空間」は、最初の状態から到達しうるすべての可能な盤面配置の集まりを意味する。「ゴールテスト」はゲームが終了したかどうかをチェックする機能で、「ユーティリティ」はゲーム終了時の状態に価値を割り当てる（例えば、AIの勝ちなら+1、負けなら-1、引き分けなら0）ものだ。これらのフレームワークを理解することで、単に手をランダムにコード化するのではなく、AI中心の構造的な方法でゲームについて考えることができるようになった。

このプロジェクトでMinimaxアルゴリズムが選ばれたのは、三目並べが「小さい」かつ「敵対的」なゲームであるため、実験に最適だったからだ。Minimaxアルゴリズムの核心は、「Maximizer（最大化する側）」と「Minimizer（最小化する側）」の考え方にある。AI自身は自分のスコアを最大化しようとするが、同時に相手プレイヤーは自分のスコアを最小化しようとすると仮定して行動を決定するのだ。このアルゴリズムは「再帰」というプログラミング手法を用いて、各手番で将来可能なすべての手をシミュレーションし、その結果を評価することで最適な手を選ぶ。大きなゲーム（チェスなど）では、考えられる状態の数が膨大になるため、「Depth-Limited Search（深さ制限探索）」という方法で探索する深さを制限することが役立つ。さらに計算を最適化するために、「Alpha-Beta Pruning（アルファベータ枝刈り）」という技術が用いられる。これは、明らかに悪い手につながる可能性のある探索パスをスキップすることで、計算量を大幅に削減するものだ。Minimaxを実際に実装することで、AIが相手のあらゆる手をどのように予測するのかを、理論を読むだけでは得られない形で肌で感じることができたという。

実際のコード実装では、いくつかの中心的な関数が作成された。Actions(state)関数は、現在の盤面状態から可能なすべての合法な手を返す。Result(state, action)関数は、指定された盤面状態に特定の手を打った後の新しい盤面状態を返す。Terminal(state)関数は、現在の盤面状態がゲームの終了状態（勝ち、負け、引き分け）であるかどうかをチェックする。そしてUtility(state)関数は、ゲームが終了した状態に対して、その価値（AIの勝ち、負け、引き分け）を評価して返す。これらの基本関数を土台として、再帰的なmax_value関数とmin_value関数を用いて、AIは各手を評価していく。max_value関数は、Maximizer（AI自身）の視点から盤面を評価し、最も高いユーティリティ値に繋がる手を探す。もしゲームが終了していれば、utility(state)の値をそのまま返す。そうでなければ、可能なすべてのアクションに対してmin_value関数を呼び出し、相手が最適な手を打つと仮定した上での結果を受け取り、その中から最大値を選ぶのだ。Minimizing player（相手）の関数も同様に機能し、最終的には両サイドにとって最適なプレイが保証される。その結果、このAIは決して負けることのない、完璧な三目並べプレイヤーとなった。

このプロジェクトを通じて、いくつかの重要な教訓が得られた。Minimaxアルゴリズムは、三目並べのように「状態空間が比較的小さく」、かつ「完全情報ゲーム」（すべてのプレイヤーが盤面の情報を完全に知っているゲーム）に非常に適していることが分かった。しかし、チェスや囲碁のような現実世界のゲームでは、考えられる手の数が天文学的に多いため、単純なMinimaxだけでは対応できない。そのため、より高速な意思決定を可能にするための「ヒューリスティクス」（経験則に基づく評価関数）や、アルファベータ枝刈りのような高度な「枝刈り戦略」が不可欠となる。そして何よりも、アルゴリズムを実際にコーディングしてみることが、理論の学習だけでは得られない深い理解をもたらした。状態空間、ゴールテスト、そして再帰的な評価といった概念が、コードを通じて実践的に強化されたのだ。このプロジェクトは、敵対的探索における堅固な基礎を築き、より大きなゲームやヒューリスティクスに基づいたAIへの挑戦へと繋がる大きな一歩となった。

今後は、学んだ知識を活かして、より複雑なゲームであるチェスやコネクトフォーに深さ制限付きMinimaxを適用する計画だ。また、探索を高速化するためのヒューリスティクスや評価関数の開発にも取り組みたいと考えている。さらに、より高度なAI技術である強化学習にも挑戦し、多様なAIプロジェクトの可能性を探っていく意欲にあふれている。