バナー

コンピュータ対戦型Tic-Tac-Toeゲームを作成しよう


1万円 FPGAスタータキットで作る RISC-V CPU


［Webinar/KIT/data］新人技術者のためのRISC-V CPU設計 初めの一歩（5月31日～6月7日，2日コース）


RISC-Vで実装するシンプルAIゲーム

図1　Tic-Tac-Toeゲームは3×3のマスで行う二人零和有限確定完全情報ゲーム．すべての手がオープンに共有される構造で，アルゴリズムの実装と検証に非常に適する．画像クリックで動画を見る．または記事を読む．参考:［VOD/KIT］ 実習キットで一緒に作る！オープンソースCPU RISC-V入門

「1万円 FPGAスタータキットで作る RISC-V CPU」の実例として紹介されているのが，コンピュータと対戦できるTic-Tac-Toeゲームです．これは3×3のマスで行う二人零和有限確定完全情報ゲームであり，すべての手がオープンに共有される構造のため，アルゴリズムの実装と検証に非常に適した題材です．

このプロジェクトでは，FPGA上のSapphire SoCに搭載されたRISC-Vプロセッサを活用し，UART経由でPC上のターミナルと通信しながら対戦を行います．人間プレイヤはキーボード入力を使い，RISC-V搭載のAIと対戦します．ゲームのロジックはMiniMax法を用いて構成されており，最適解を短時間で導き出せます．

3KB未満に収まる実用プログラム

このTic-Tac-Toeゲームは非常に省メモリに設計されており，プログラムの全体サイズは3KB未満です．これはRISC-Vの短縮命令による命令サイズの圧縮による恩恵です．また，Sapphire SoCのAPIを利用することで，ハードウェア仕様や周辺の詳細な理解が不要となり，学習のハードルが低くなっています．

本プロジェクトでは以下のような手順で開発を進めていきます．

  1. RISC-V IDEを起動してWorkspaceを指定
  2. 新規にEfinix Makefile Projectを作成
  3. プロジェクト名をXyloni_TicTacToeとし，BSPを指定
  4. UART制御用のライブラリをインクルード
  5. 盤面状態を表現するための配列変数boardを準備
  6. ターミナルに盤面を描画する関数を作成

UART通信とMiniMax法の融合

RISC-Vボードが担うのは，盤面の状態管理とAIによる手の決定です．人間側からの入力はUART通信を通じて送られ，RISC-VはMiniMax法で全探索を行って最善手を選択します．すべての盤面を評価するため，ゲームは原理的には引き分けに帰結します．小規模な盤面であれば，全探索でも十分にリアルタイムで動作可能です．

MiniMax法の基本

MiniMax法は，ゲーム理論における古典的な探索アルゴリズムです．Tic-Tac-Toeのような二人零和ゲームにおいて，相手がもっとも賢くプレイすることを前提に，自分の利益を最大化する手を選ぶ戦略です．これはゲーム木の全探索を行い，葉ノードでの評価値を親ノードへと逆伝播させていく手法です．

MiniMax法では，ゲームの状態をノード，可能な手を枝とする木構造を作成します．交互にプレイヤが動くため，奇数深度では最小化（相手の最善手を想定），偶数深度では最大化（自分の最善手を選択）になります．このようにして，ツリーのルートにおける最適な一手を選定することが可能です．

Tic-Tac-Toeでの応用

Tic-Tac-Toeは盤面が3×3のため，全探索してもノード数はそれほど多くありません．初期状態から最大でも$9!$とおりしかないため，メモリや演算性能に制約があるFPGA上のRISC-VプロセッサでもMiniMax法が現実的に実装可能です．

このアルゴリズムにより，RISC-V側のAIは常に最善の手を選びます．人間側がどんな手を打っても，引き分けにもち込むか負けるしかないという構造になります．

MiniMax法には評価関数が必要です．Tic-Tac-Toeでは最終局面での勝敗を数値化し，勝ちを+1，負けを-1，引き分けを0とすることで，全探索が可能になります．また，現在の状況で終了していない局面では，再帰的に次の状態を評価していきます．

MiniMax法の限界と発展

MiniMax法は簡潔で理解しやすい一方，ノード数が爆発的に増加するため，大規模ゲームには不向きです．将棋や囲碁のようなゲームでは，Alpha-Beta枝刈りなどの技術を組み合わせる必要があります．Tic-Tac-Toeのように状態空間が小さければ，MiniMax法は非常に強力です．

本プロジェクトでは，MiniMax法の実装が学習の核になります．AIやアルゴリズム設計の基礎を理解するよい機会です．

〈著:ZEPマガジン〉

動画を見る，または記事を読む

著者紹介

  • 出身地：京都市左京区
  • 仕事：1986年，日立製作所に入社し，SHマイコンの開発に従事．以降，ルネサステクノロジ，ベンチャー企業，大手半導体メーカにて，画像処理用SoCや各種マイコンおよび関連半導体デバイスの開発を統括．現在もマイコン製品設計に取り組んでいる．
  • 趣味：1978年からマイコン・FPGA・GPUと戯れ
  • 執筆活動：2000年からマイコンを絡めた雑誌記事と書籍を執筆

著書

  1. ［VOD/KIT］実習キットで一緒に作る！オープンソースCPU RISC-V入門，ZEPエンジニアリング株式会社．
  2. ARMベース・システムLSI開発の事例研究，Design Wave Magazine 2006年5月号，CQ出版社．
  3. ARM汎用プロセッサで使える汎用JTAGデバッガを自作する，Design Wave Magazine 2008年6月号，CQ出版社．
  4. 並列処理プロセッサxCORE徹底研究，インターフェース 2014年11月号～2015年6月号（連載),CQ出版社．
  5. Cで直叩き！超並列コンピュータGPU全速力，トランジスタ技術　2019年9月号（特集），CQ出版社．ほか
  6. 今すぐ使えるH8マイコン基板　初版2010年，増補版2011年，CQ出版社．
  7. 2枚入り小型ARMマイコン基板　2011年，CQ出版社.
  8. ARM PSoCで作るMyスペシャル・マイコン　基板付き　2013年，CQ出版社．
  9. ARM PSoCで作るMyスペシャル・マイコン　開発編　　2013年，CQ出版社．
  10. SHマイコン活用記事全集　2014年，CQ出版社．
  11. FPGA電子工作スーパキット　2016年，CQ出版社．
  12. MAX10実験キットで学ぶFPGA＆コンピュータ　2016年，CQ出版社．
  13. 完全版FPGA電子工作オールインワン・キット　2016年，CQ出版社．

参考文献

  1. Lチカ入門！ソフトウェア屋のためのHDL事はじめ，ZEPエンジニアリング株式会社．
  2. Zynqで作るカスタム・コンピュータ・チップ，ZEPエンジニアリング株式会社．
  3. ［VOD/KIT］一緒に動かそう！Lチカから始めるFPGA開発【基礎編＆実践編】，ZEPエンジニアリング株式会社．
  4. ［VOD/KIT］Xilinx製FPGAで始めるHDL回路設計入門，ZEPエンジニアリング株式会社．
  5. ［VOD/KIT］Zynqで初めてのFPGA×Linux I/O搭載カスタムSoC製作，ZEPエンジニアリング株式会社．
  6. ［VOD］カメラ×ラズパイで一緒に！初めての画像処理プログラミング
  7. ［VOD/KIT］ 実習キットで一緒に作る！オープンソースCPU RISC-V入門，ZEPエンジニアリング株式会社．
  8. ［VOD/KIT］ARM Cortex-A9＆FPGA内蔵SoC Zynqで初体験！オリジナル・プロセッサ開発入門，ZEPエンジニアリング株式会社．