オセロAIの教科書 2 【基礎】 ボードの実装
こんにちは、にゃにゃんです。
この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。
この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。
この記事を読むのに必要な知識
この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。
オセロのルール
基礎的なプログラミングの知識・経験
C++
Python
ボードの実装方法あれこれ
2023/06/24追記
この記事ではインデックス化を紹介しますが、現在の私はビットボードが一番速いと思っています。ビットボードについての記事をいつか書いて、ここにリンクします。
オセロプログラム(特にオセロAIに限らないオセロに関するプログラム)では、もちろんオセロのボードを操る方法を実装しなくてはなりません。
ボードの実装には様々な方法が考えられ、方法の名前だけ先に示すと
配列
ビットボード
インデックス化
という3つの異なる方法がよく見られます。一つずつ見ていきましょう。
配列
一番直感的な実装です。オセロであれば8x8盤面なので、8x8の二次元配列を使ってボードを表します。
例えば、それぞれのマスについて黒石が置かれていれば0、白石なら1、空きマスなら2、などとすればボードの状態を表せます。
合法手(置けるマス)生成や着手の処理については、任意のマスから縦横斜めの8方向に見ていって判定します。詳しくは以下のサンプルプログラムのothelloクラスをご覧ください。
余談ですが、このサンプルコードは今後オセロAIを作っていく中で対戦するために使うコードです。
配列による実装は直感的な反面、時間的にもメモリ的にも効率が悪いです。
配列に使う値は3種類(黒と白と空)のみなのにintやcharを使っては、intやcharの取れる値を使い切れていない点でメモリの効率が悪いです。また、配列参照が多くなったりループが多くなったりして、計算時間も多めです。
ただ、わかりやすく、実装しやすく、バグりにくいのはとても良い点なので、高速に処理する必要がない場合、つまり、何万回、何十万回も実行することがない場合には好んで使用されます。
ビットボード
ビットボードは少ないメモリ使用量でとても高速にオセロのボードを実装できる優秀な方法です。ただし、少し理解が難しい部分があるかもしれません。
具体的には、64マスのオセロの盤面を64bitの整数2つで表します。1つ目の整数では、黒石があればビットを立てて、なければ(空きマスか白石)ビットを立てません。2つ目の整数では白石について同じようにビットを立てます。
画像では1行だけで解説していますが、64マス全てにおいて同じことを行って、黒石と白石についてそれぞれ0以上2^64未満の整数で表します。
本記事集では次に解説するインデックス化を使うので、ビットボードはきちんと解説しません。気になる方は以下のリンクが役に立つと思います。
https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43
http://www.amy.hi-ho.ne.jp/okuhara/bitboard.htm
インデックス化
ビットボードではボードの状態を黒石と白石に分けて考えました。インデックス化では、各マスについて黒、白、空の3種類の状態しかないことを使って、3進数を使ってボードの状態を表します。
しかし、現代のコンピュータでは3進数で64マス全てを表す、つまり3^64種類の状態を簡単に表すことはできません。そこで、各行・列・斜めについてそれぞれ3進数で状態を表します。
ボードの状態は行が8つ、列が8つ、右肩下がりの斜めが11個、右肩上がりの斜めが11個の合計38個の整数で表します。
行と列はともかく、斜めが11個なのは以下の画像の太い線のところのマスの連続を1つの整数で表しているためです。
端っこを使わない理由については後ほど説明します。
このように38種類の整数で状態を表すことで、合法手生成と着手処理がとても簡単に書けてしまいます。
オセロにおいて、着手すると相手の石がひっくり返りますが、その処理は縦横斜め8方向について、完全に独立です。よって、このように直線部分それぞれについて着手の処理をすれば、ボード全体で着手の処理ができたことになります。合法手生成についても同じで、各直線部分について合法なマスを見つければ済みます。
斜めにおいて端っこを使わないのは3マス未満の直線部分の情報を持っていたところで3マス未満の直線内で石を返すことはできないので無駄だからです。
さらに、各直線部分は3マスから8マスの連続で表されるので、現れるパターンは高々3^8=6561種類だけです。これだけであれば、オセロAIを開始した直後に一瞬で前計算できます。前計算したらあとは実際の処理ではその計算結果を使うだけ(つまり配列参照を行うだけ)です。
インデックス化はメモリ参照がとても多いのでビットボードよりも遅くなりますが、前計算だけしてしまえば処理がわかりやすいです。
この記事集ではインデックス化で実装していきます。しかし、インデックス化は特段速い手法ではないため、もしかしたら近い未来にビットボードに書き換えているかもしれません。
なお、インデックス化については私自身が以下のサイトで得た知識です。
https://sealsoft.jp/thell/algorithm.html#board
私による具体的な実装はサンプルコードをご覧ください。
まとめ
今回は実際にAIを実装する前段階としてボードの実装方法を学びました。これからの記事ではここで紹介したサンプルコードを使いまわしていくことになります。
サンプルコードはわかりやすさ重視なので一定以上の高速化は行っていません。MITライセンス(自由度の高いライセンス)ですので好きに書き換えて使ってください。むしろ書き換えることで理解が深まります。
次回予告
次回はついにオセロAIの制作に入ります。具体的には、1手先を読むAIです。
サンプルコードや書き換えたものと実際に遊びながら学んでいきましょう！
スキと投げ銭で喜びます
noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！
この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。
ここから先は
¥ 100
この記事が気に入ったらサポートをしてみませんか？