見出し画像

オセロAIの教科書 11 【探索】 高速化

にゃにゃん(山名琢翔)

こんにちは、にゃにゃんです。

この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。

この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。


はじめに

今回は探索における発展的な高速化を紹介します。さすがにこれらを網羅したサンプルコードは規模が大きくなるため、書いていません。

その代わり、参考までに私の世界1位AIのコードを載せます。

効果が大きいものほど見出しに星マークを多く書いておくので、星マークの多いものから優先してやってみてください。


この記事を読むのに必要な知識

この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。

  • オセロのルール

  • プログラミングの知識・経験

  • C++

  • データ構造(ハッシュテーブル)


簡易alphabeta法の利用 ★★★★★

これまで、negascout法で葉ノードまで探索していましたが、最終N手はmove orderingや置換表のない簡易的なalphabeta法で探索すると、探索ノード数は増えるものの時間的には高速になることがあります。

なお、ただの簡易alphabetaよりも手間をかけずに効率化するため、探索開始前に予めマスの重みで手を並べ替えておく(例えば、隅は最初に探索できるようにするなど)のがおすすめです。

参考までに、私が作った世界1位AIでは中盤は最終3手、終盤は最終8手を簡易alphabetaにしています。


ハッシュテーブル自前実装 ★★★★

実は、置換表として使うハッシュテーブルは厳密なハッシュテーブルである必要はなくて、ハッシュテーブルにおける連結リスト部分をなくしても問題なく動きます。

ハッシュが衝突したときには新しいキーと値でハッシュテーブルの要素を置き換えてしまいます。

ハッシュテーブルが十分に大きくて、ハッシュ関数の性能が十分に良い(衝突しにくい)場合はハッシュテーブルへの登録や検索の最適化がしやすくなり、かなり高速になります。

なお、記事では上限と下限で別のハッシュテーブルを使いましたが、私の世界1位AIでは上限と下限の両方を持つハッシュテーブルを使っています。

参考までに世界1位AIのハッシュテーブルの実装を抜粋して載せます。

#define search_hash_table_size 16384
constexpr int search_hash_mask = search_hash_table_size - 1;

struct search_node{
    bool reg;
    int k[4];
    int l;
    int u;
};

search_node search_replace_table[2][search_hash_table_size];

inline unsigned long long calc_hash(const int *p){
    return
        p[0] + 
        p[1] * 17 + 
        p[2] * 289 + 
        p[3] * 4913 + 
        p[4] * 83521 + 
        p[5] * 1419857 + 
        p[6] * 24137549 + 
        p[7] * 410338673;
}

inline bool compare_key(const int a[], const int b[]){
    return (a[0] + a[1] * n_line == b[0]) && (a[2] + a[3] * n_line == b[1]) && (a[4] + a[5] * n_line == b[2]) && (a[6] + a[7] * n_line == b[3]);
}

inline void search_hash_table_init(const int table_idx){
    for(int i = 0; i < search_hash_table_size; ++i)
        search_replace_table[table_idx][i].reg = false;
}

inline void register_search(const int table_idx, const int *key, int hash, int l, int u){
    ++hash_reg;
    search_replace_table[table_idx][hash].reg = true;
    for (int i = 0; i < 4; ++i)
        search_replace_table[table_idx][hash].k[i] = key[i * 2] + key[i * 2 + 1] * n_line;
    search_replace_table[table_idx][hash].l = l;
    search_replace_table[table_idx][hash].u = u;
}

inline void get_search(const int *key, const int hash, const int table_idx, int *l, int *u){
    if (search_replace_table[table_idx][hash].reg){
        if (compare_key(key, search_replace_table[table_idx][hash].k)){
            *l = search_replace_table[table_idx][hash].l;
            *u = search_replace_table[table_idx][hash].u;
            ++hash_get;
            return;
        }
    }
    *l = -inf;
    *u = -inf;
}

世界1位AIでは、ハッシュテーブルのswapも行わなくて済むよう、ハッシュテーブル自体を2次元配列にして、片方を現在の探索で、もう片方を前回の探索に使っています。また、ハッシュ計算やテーブルの検索を可能な限り最適化した設計にしています。

さらに、ハッシュテーブルの大きさを2^nにすることで、ハッシュ値に-1+2^nでビットAND演算をするだけでハッシュテーブルを参照できるインデックスを生成できるようにしています。


最終1手最適化 ★★★

必勝読みや完全読みでは、最後の1マスへの着手を最適化できます。具体的に言えば、最終1手は石差がわかれば良いので、新たなboardオブジェクトを作ったりと無駄なことをする必要はないのです。着手する関数を改造して石差を高速に求める関数を作ってしまいましょう。


最終N手最適化 ★★

最後の2マスを考えましょう。move orderingなんてあってもなくても変わらないのはもちろん、最後の2マスについて人力で着手するコードを書けばforも外せて、コンパイラが最適化しやすくなります。これは最終3手でも4手でも同じようにできます。ですがやりすぎると可読性がなくなってしまうので注意が必要です。

参考までに、世界1位AIでは最終3手まで人力で最適化しています。


一時オブジェクトの削減 ★★★★

まず、一時オブジェクトをむやみに作らないようにしましょう。

例えば、サンプルコードでは

// negascout法
int nega_scout(board b, int depth, bool passed, int alpha, int beta) {
    略
}

のように、boardオブジェクトをコピーで受け取っていますが、世界1位AIでは

int nega_scout(const board *b, const long long strt, bool skipped, int depth, int alpha, int beta){
    略
}

のように、boardオブジェクトのポインタで受け取っています。こうすることで余計なオブジェクトを作らずに済むので高速になることが期待されます。


配列のランダムアクセスを避ける ★★★★

メモリアクセスは、実は下手な書き方をするととても遅くなります。

プログラムの実行中は、CPUに近い領域にメモリの一部が自動でコピーしてあります。この領域をキャッシュと言います。プログラムが使いたいメモリ領域がキャッシュにあれば高速にアクセスできますが、なければアクセスに時間がかかります。

キャッシュはある程度連続したメモリ領域でメモリをコピーしておくため、同じ配列から複数要素を取り出す場合は、各要素がなるべく隣り合ったり近くにあったりする配置になるように配列を設計すると高速になります。

例としてサンプルコードのボードの実装部分を見てみます。

int move_arr[2][n_line][hw][2];     // move_arr[プレイヤー][ボードのインデックス][マスの位置][0: 左 1: 右] = 何マスひっくり返せるか

この行でmove_arrを宣言しています。move_arrは盤面に着手するときに使うので、move_arr[2][n_line][hw][2]の太字にした2要素は必ずセットで参照します。そのため、メモリの連続した領域に置いてあります。さらに、move_arr[2][n_line][hw][2]の太字にした部分も、ある程度短い時間の間に参照することが想定されるのでメモリの近い領域に置いています。

ただ、特に2つ目はかなり効果が怪しいのでおまじないレベルかもしれません。


並列化 ★★★

これについては、私はほとんどやっていません。私が出たコンテストでは並列化できなかったからです…

negascoutでは、最初の1手以外はNWSをするので、NWSを一気に並列処理してしまう手法があるらしいです。

ただ、NWSを一気に行うと、一気にやらなければ縮んでいた探索窓が縮まないまま探索をしてしまうので、訪問ノード数が増えることが予想されます。それを補って余りあるほどに並列化が有効な場合は使ってみても良さそうです。

並列化については私が現在挑戦中なので、そのうち書き足すかもしれません。


for人力展開 ★

for文はそのまま実行するよりも、展開した方が速くなります。コンパイルオプションでコンパイラに展開させることも可能ですが、特殊な場合では人力で展開した方が大幅に高速化できます。

例えば世界1位AIの合法手判定では4要素か3要素(最後の1要素はダミーが入っています)のboolの配列参照をしているので、以下のように書いています。

bool legal;
legal = legal_arr[b->p][b->b[place_included[p0][0]]][local_place[place_included[p0][0]][p0]] || 
        legal_arr[b->p][b->b[place_included[p0][1]]][local_place[place_included[p0][1]][p0]] || 
        legal_arr[b->p][b->b[place_included[p0][2]]][local_place[place_included[p0][2]][p0]];
if (place_included[p0][3] != -1)
    legal |= legal_arr[b->p][b->b[place_included[p0][3]]][local_place[place_included[p0][3]][p0]];

このコードは、とりあえず3要素を見て、4要素目は-1(ダミー)でなければ見るようにしています。

力技かつメンテナンス性が落ちるので、これは最終手段だと思ってください。


まとめ

高速化は地味ですがとても強力なので、ぜひ限界まで高速化を試みてください。


次回予告

次回はついに最終回です。

私はオセロAIに半年以上の時間を注ぎましたが、もちろんその中ではここに書いていないボツにしたアイデアや技術があります。それらを紹介します。


スキと投げ銭で喜びます

noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！

この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。

ここから先は

0字

¥ 100

この記事が気に入ったらサポートをしてみませんか？