オセロAIの開発者が語る記事が興味深かった。
オセロはあまり強くもなく、AIの作り方全く知らないが、オセロはすでに全解析されているのかと思っていた。手数を調べてみると10^60通りとでるが、これは、打てる手場所が平均で10あることと、64-4=60手で終わることから来ているようだ。初手は対称性から1通り、2手目は3通り。10^60よりは少ない気がするが。
盤面の状態を保存する方法は?
00000000
00000000
00000000
000WB000
000BW000
00000000
00000000
00000000
こんな文字列だったら、256Byte
4通り=2bit/マスだったら、288=128bit=16Byte
3通りだったら
33333333=8181=6561<2^13=13bit
13*8列=104bit=13Byte以下
64マスに手順を数字で保存するなら、白黒を保存する必要ないから、
60<64=6bit/マスだから、
6bit*64マス=384bit=48Byte
1Byte/マスで64Byte
盤面を保存するのではなく、手順のみを保存する場合、a1~h8まで使う方法なら、
2Byte60手=120Byte
１手は60通り以内だから、6bitで足りるので、
6bit60手=360bit=45Byte
1Byte使ったとして、
1Byte*60手=60KB
※無駄を０にはしてない。
※更に圧縮したら小さくなる。
結論
盤面のみの保存なら、最小で13Byte、実用的なのは16Byte
手順込みなら、48Byte〜実用的なのは64Byte
手順のみなら、45Byte〜実用的なのは60Byte
10^59通り x 16Byte/1024/1024/1024/1024≒16 x 10^47TB
これではすべてを保存しておくことも全く不可能。
平均2通りの手に枝切りできたとして、
2^60=1024^6
16Byte x 1024^6=1024 x 1024*16TB
論文には最終的に1.510^9局面を生成とあるので、それを保存するだけでも
16Byte1.510^9=161500000000=24000000000Byte≒24GB
ざっくり24GBも必要になることがわかる。
枝切りだけで、場合の数を減らすのが難しいので、
最善を打つという前提、
全体を「前半」「中盤」「後半」に分ける、
ことで、減らしているのかな？？？？
ともかく、シンプルルールのオセロで、こんなに大変だなんて知らなかった。