TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

高速なPythonのリバーシ(オセロ)ライブラリ

将棋で強化学習のアルゴリズムをいろいろ試そうとしたが、DQNが全く学習しないので、もう少し簡単なゲームを先に試そうと思う。
ということで、リバーシ(オセロ)で試すことにした。

Pythonで使えるリバーシのライブラリがないか探したが良さそうなのが見つからなかったので、自分で作ることにした。
石をひっくり返す処理をPythonのfor文で実装すると遅くなることが予測できるので、cshogiと同じようにC++で実装して、Pythonから呼び出す形式にした。

ビットボードの実装

C++でビットボードを使って高速に実装する方法について調べたところ、SIMD(AVX2とBMI)を使った実装が公開されていたので流用させてもらうことにした。
実装の詳細は、以下のページで解説されている。
オセロの着手可能位置生成 【ビット演算テクニック Advent Calendar 2016 23日目】 - prime's diary
オセロの終盤ソルバーを100倍以上高速化した話

Visual C++GCC対応

上記のコードはインテルコンパイラ向けに作られていたので、Visual C++GCCで動作するように移植を行った。

GCCは、_bittest64などのx64のCPU命令の組み込み関数が用意されていないので、ビット演算で実装する必要があった。
SIMD命令も一部用意されていないものがあったので、以下のようにマクロ定義で対応した。

#define _mm_setr_epi64x(v0, v1) _mm_set_epi64x((v1), (v0))
#define _mm256_set_m128i(v0, v1)  _mm256_insertf128_si256(_mm256_castsi128_si256(v1), (v0), 1)
#define _mm256_setr_m128i(v0, v1) _mm256_set_m128i((v1), (v0))

Pythonのインターフェース

cshogiの元にしたpython-shogiに近い形で実装した。
将棋では手を戻す操作を可能にしているが、オセロの場合は盤面は128bitで表現できるため、盤面のコピーで対応した方が早いため、手を戻す操作は実装していない。

以下は、ランダムに手を選んで終局までプレイする例である。

from creversi import *
import random
board = Board()
while not board.is_game_over():
    print(board)
    print('black' if board.turn else 'white')
    moves = list(board.legal_moves)
    if len(moves) == 0:
        board.move_pass()
        print('pass')
    else:
        move = random.choice(moves)
        print(move_to_str(move))
        board.move(move)

盤面はprint()で以下のように表示できる。

 |abcdefgh
-+--------
1|........
2|........
3|........
4|...ox...
5|...xo...
6|........
7|........
8|........

cshogiと同じようにSVGで表示する機能もそのうち実装したい。

creversi

ライブラリ名は「creversi」とした。
ソースはGitHubで公開した。
github.com


このライブラリを使って、DQNなどのアルゴリズムを試してみるつもり。
強化学習に必要な機能は随時追加する予定。