最強の立体四目並べAIを作る part2 | bit boardの実装
ゲームの基本となる、盤面の作成を行います。
一般的には、盤面はリスト形式で作ることが多いですが、高速化をするときはbit boardを使用します。
コードはこちらで公開しています↓↓↓
https://github.com/mikanakim/score4_AI/tree/main/score4
bit boardとは
bit boardとは、2進数の整数で表現された盤面のことです。
ボードゲームを作る時、よくあるのがリストによる実装です。扱いやすく、わかりやすいのが良い点ですが、速度を求めるときは避けられます。bit baordは高速化を目指すには必須の技術です。慣れると実装も楽でした。
bitとは
コンピュータで扱う情報は全て電気信号のON、OFFとして表されています。「情報」というのは、文字や写真などの「表現」や、足し算をするという「命令」などです。深掘りすると長くなるので一旦おいておきます。
この電気信号のONを1、OFFを0とすると数学的に2進数として表現することができます。つまり、2進数はコンピュータと相性がいいのです。その2進数の桁数をbitという単位で数えているのです。また、0を1にすることをbitを立てると言ったりします。
よく使うbit演算
bitを扱うにあたって、知っておくべき演算があります。論理和(OR)、論理積(AND)、排他的論理和(XOR)、否定(NOT)、シフト演算です。入力をA、Bとし、出力を表にまとめたのがこちらです。bit boardはこれが利用できるから速いんです。
なぜ速いのか？どれくらい速いのか？
高速化ができる最も大きな理由はbit演算と並列処理にあります。以下の盤面での三目並べの勝利判定を例に実験してみましょう。
リストを使用した方法(method1)、bit boardを使用した方法(method2)で実装しました。それぞれを1000万回ずつ実行し、その終了までにかかる時間を測ってみます。
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
// method1の勝利判定のライン
vector<vector<int>> line1 = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8},
{0, 2, 4}, {1, 3, 5}, {2, 6, 8},
{0, 4, 8}, {2, 4, 6}};
// method2の勝利判定のライン
vector<int> line2 = {0b111000000,
0b000111000,
0b000000111,
0b100100100,
0b010010010,
0b001001001,
0b100010001,
0b001010100};
// method1の盤面
vector<int> board1 = {0, 0, 1, 0, 1, 0, 1, 0, 0};
// method2の盤面
int board2 = 0b001010100;
// vectorによる実装
void method1() {
for (const auto& l : line1) {
int count = 0;
for (const auto& idx : l) {
if (board1[idx] == 1) {
count += 1;
}
}
if (count == 3) {
break;
}
}
}
// bit boardによる実装
void method2() {
for (const auto& l : line2) {
if ((l & board2) == l) {
break;
}
}
}
int main() {
const int iterations = 10000000; // 繰り返し回数
// method1の計測
clock_t start1 = clock();
for (int i = 0; i < iterations; ++i) {
method1();
}
clock_t end1 = clock();
double time1 = static_cast<double>(end1 - start1) / CLOCKS_PER_SEC;
std::cout << "method1 execution time: " << time1 << " seconds" << std::endl;
// method2の計測
clock_t start2 = clock();
for (int i = 0; i < iterations; ++i) {
method2();
}
clock_t end2 = clock();
double time2 = static_cast<double>(end2 - start2) / CLOCKS_PER_SEC;
std::cout << "method2 execution time: " << time2 << " seconds" << std::endl;
return 0;
}出力は以下のようになりました。
>> ./test
method1 execution time: 3.48919 seconds
method2 execution time: 0.704213 secondsbit boardで実装すると、5倍弱速いです。理由としては、そもそもbit演算が非常に高速であること、加えて、bit boardでは、method1でループを回さなければいけなかった処理をbit演算を活用することでスキップしていることが挙げられます。後者について、一度のbit演算で盤面全体のbitを計算できるのは、並列処理を行えるということになります。つまり、bit演算の速さと並列処理を利用できる点で非常に効率の良い実装方なのです。
なお、今回は三目並べで実験したので5倍程度の差でしたが、実際はもっと複雑な処理を実行するので、処理速度には今回以上の差がでると予想されます。
【本編】立体四目並べのbit board
前置きが長くなりましたが立体四目並べにおいてはどのように活用できるのでしょうか？都合がいいことに、盤面は64bitで表せるのでとても切りが良いです。
player、opponentともに64bit、合計128bitで盤面を管理しています。
事前に、mask.hにWIN_MASKSのようなbit maskをたくさん用意しておき、処理の効率化を図っています。
勝敗判定
勝敗判定は先程の三目並べと同様のコードです。
bool is_win(int player) {
uint64_t board = playerBoard[player];
for (uint64_t mask : WIN_MASKS) {
if ((board & mask) == mask) {
return true;
}
}
return false;
}盤面への着手
ボードに球を置く関数です。重力に従って、かつ重複しないように気をつけて球を置いていきます。ちなみに手番も0, 1で管理しています。手番が変わるたびに1とXORするだけでいいので非常に便利です。
bool move(int player, int idx){
update_zobrist_hash(idx, player);
for (int i = 0; i < 4; ++i){
if ((allMoves & (1ULL << (16*i + idx))) == 0) {
playerBoard[player] |= (1ULL << (16*i + idx));
allMoves |= (1ULL << (16*i + idx));
teban ^= 1;
return true;
}
}
cout << "重複しています。選択し直してください。" << endl;
return false;
}合法手の検出
合法手とその具体的な位置を求める関数です。
特にlegal_actions()は非常によく使うので最大限にコンパクトな関数としました。立体四目並べの合法手はz=4が空いている列を見ればわかります。legal_actions()は0-15の平面的な場所情報のみを32bit maskとして返します。そのため、これらが具体的にどの高さ(z)にいるのかはわかりません。それを補うために、ground_detector()は合法手の立体的な位置を検出し、64 bitのmaskで返します。groundは地面のことです。合法手があるということは、そのマスは宙に浮いているのではなく、直下に盤面の床か球があるわけです。
// 合法手を求める
int legal_actions(){
return ((~allMoves) & 0xFFFF000000000000) >> 32;
}
// 合法手の立体的な座標まで求める
uint64_t ground_detector(){
uint64_t ground = (((allMoves << 16) | 0x000000000000FFFF) ^ allMoves);
return ground;
}リーチ検出
リーチの検出は、通常の対戦時に使用するreach_detector()、alpha beta法の関数内で使う差分計算による高速リーチ検出関数(reach_detector_alpha_beta())の2つを用意してあります。
なお、リーチには盤面の床や球の上に存在するものと、空きマスの上に存在するものがあり、それぞれgroundリーチ、floatingリーチと呼んでいます(※floatingリーチは次の記事以降で登場する決勝点と同義です)。以後、特に区別せず「リーチ」という場合は「groundリーチ」を指しています。
ここで紹介する関数で検出しているのはgroundリーチです。
通常検出版は単に勝敗判定のline上に自分の球が3つ並んでいて残り１つが空きマスであるもののうち、groundにあるものを検出しているだけです。
高速検出版は、新たに置いた球に関連するlineのみ調べています。球を置くと、当然その球が含まれるlineにリーチができる可能性があります。加えて、その球の直上(idx + 16の位置)にもリーチができうることを忘れてはいけません。floatingリーチの下に球をおいた場合や、z方向に3つ自分の球を積んだ場合などです。
// 通常検出版
uint64_t reach_detector(int player){
uint64_t ground = ground_detector();
for (uint64_t mask : WIN_MASKS){
if (__builtin_popcountll(mask & ground) == 1){
if (__builtin_popcountll((playerBoard[player] & mask)) == 3){
return mask & ground;
}
}
}
return 0;
}
// 高速検出版
vector<uint64_t> reach_detector_alpha_beta(int player, int idx){ // playerがidxに置いた。
uint64_t ground = ground_detector();
uint64_t player_reach = 0;
uint64_t opp_reach = 0;
for (int i = 0; i < 4; ++i){
int irev = 3 - i;
if ((allMoves & (1ULL << (16*irev + idx))) != 0) {
idx = idx + 16*irev;
break;
}
}
// idxにおいたとき、リーチができうる場所はidxをlineに含む場所 + idx+16をlineに含む場所
for (auto& id_mask: POT_4_MASK[idx]){
if (__builtin_popcountll(id_mask & ground) == 1){
if (__builtin_popcountll((playerBoard[player] & id_mask)) == 3){
player_reach = id_mask & ground;
break;
}
}
}
if (idx < 48){
for (auto& id_mask: POT_4_MASK[idx+16]){
if (__builtin_popcountll(id_mask & ground) == 1){
if ((player_reach != 0) && (opp_reach != 0)){
break;
if ((__builtin_popcountll((playerBoard[player] & id_mask)) == 3)){
player_reach = id_mask & ground;
}
if ((__builtin_popcountll((playerBoard[player^1] & id_mask)) == 3)){
opp_reach = id_mask & ground;
}
}
}
}
}
return {player_reach, opp_reach};
}この他にもリーチ関連の関数として、alpha beta法の高速化や詰み検出に使用した関数があります。また別の記事で説明します。
次回
探索アルゴリズムと詰み検出について解説します。