半年前に下記の本を見て、将棋AIについて学んだものの、将棋だとあまりにも実装が難しく、学習時間もかかるのでオセロAIを作ってました。その後画像生成AIとかに興味が移ってしまったのですが、せっかくこんなのを立ち上げたので、忘れないうちに復習しておく。
book.mynavi.jp
人より強い・・・ｗ
第一回はオセロそのものの実装編です。オセロの実装はビットボードというものを使った効率的な方法がありますが、私の目的はそこではないのと、AIに入力するときには結局配列になるので、単純な実装にしています。オセロの実装部分だけC++でやってます。そこまで最適化できてないだろうけどこれでもPythonよりましです。
実装にあたって特に参考にしたものはないのですが、むかーしこの本を読んだので、その記憶をもとにしている可能性が高いです。
https://www.yodobashi.com/product/100000009000200371/
ボードは100次元配列(board)を使って、左上から右下へ並べることで、10×10の表現します。オセロのボードは8×8ですが、端っこに壁があるとすごい分かりやすいです。オセロの左からaマス、上からbマスが十進数abで表現できます。たとえば左から4マス、上から5マス（オセロ的にはd5）はboard(45)と書けます。初期状態ではboard(45)=WHITEですね。
| W | W | W | W | W | W | W | W | W | W |
| W | W | ||||||||
| W | W | ||||||||
| W | W | ||||||||
| W | 白 | 黒 | W | ||||||
| W | 黒 | 白 | W | ||||||
| W | W | ||||||||
| W | W | ||||||||
| W | W | W | W | W | W | W | W | W | W |
最初の状態、Wは壁。
使ったライブラリ。pythonのnumpyとの連携のためにpybindやEigenを使ってます。通常の配列ではなくEigenのベクトルをつかうので、[]じゃなくて()を使ったりしています。
#include <string> #include <iostream> #include <vector> #include <stdlib.h> #include <time.h> #include <pybind11/pybind11.h> #include <pybind11/stl.h> #include <Eigen/Dense> using Eigen::MatrixXd; using Eigen::VectorXi; #include <pybind11/eigen.h> using namespace std;
定数
const int BLACK = 1; const int BLANK = 0; const int WHITE = -1; const int WALL = 2; const int BOARD_SIZE = 10; const int RIGHT = 1; const int LEFT = -1; const int UP = -BOARD_SIZE; const int DOWN = BOARD_SIZE; const int RIGHT_UP = RIGHT+UP; const int RIGHT_DOWN = RIGHT + DOWN; const int LEFT_UP = LEFT+UP; const int LEFT_DOWN = LEFT+DOWN; const int DIRECTIONS[8] = {RIGHT,LEFT,UP,DOWN,RIGHT_UP,RIGHT_DOWN,LEFT_UP,LEFT_DOWN};
右に移動するには+1、左に移動するには-1、上に移動するには-10、下に移動するには+10といった感じですね。こうすれば右上は右+上で表せられます。
メンバ変数は３つだけです。ボード（100次元配列）と白黒どっちのターンかと、合法手一覧です。
public: VectorXi board = VectorXi::Zero(100); int turn; std::vector<int> legal_moves;
コンストラクタです。初期配置とターンの設定と合法手の計算（後述）をしています。オセロの先手は黒なんですね。私はしばらくチェスと同じ白だと勘違いしてました。
Board(){ turn = BLACK; for(int i=0;i<100;i++){ if(i%10==0 || i%10 == 9 || i/10==0 || i/10 == 9){ board(i) = WALL; } board(44) = WHITE; board(55) = WHITE; board(45) = BLACK; board(54) = BLACK; } update_legal_moves(); }
1手指す動きを計算するメソッドです。入力は指す位置のみです。メンバ変数turnがあるので白黒どっちが指したかは分かります。個人的につくったので、p,q,zとか分かりにくい変数ばっかりですね。よくないですねこういうの。
int move(int z){ int p,q; //空白でないならエラーをだす if(board(z) != BLANK){ throw std::logic_error("エラー"); } //上下左右斜めそれぞれに対して、石ひっくり返す動きをする。 for(int i=0;i<8;i++){ p = z + DIRECTIONS[i]; q = 1; //隣が敵の石だったら、隣に移動するのという動作繰り返す。 while(board(p) == -turn){ p += DIRECTIONS[i]; q += 1; } //自分の石を見つけたら、 if(board(p) == turn){ //そこまでにあった石を全部自分の石にする。 //j=0からスタートなので、指した場所そのものも自分の石になる。同じこと8回やってるけどまあいいや。 for(int j=0;j<q;j++){ board(z+DIRECTIONS[i]*j) = turn; } } //コードはないですが、自分の石に会う前に、空白や壁にたどり着いた場合、何も起こりません。 } turn = -turn; update_legal_moves(); if(legal_moves.size()==0){ turn = -turn; //敵に合法手がない場合、再度自分のターンになる。 update_legal_moves(); if(legal_moves.size()==0){ return 1; //両方なかったらゲーム終了。 } } return 0; }
合法手計算です。全てのマスを確認します。
void update_legal_moves(){ std::vector<int> moves; int p,py,d; //すごい単純な全探索アルゴリズムです for(int y=1;y<9;y++){ py = y * 10; for(int x=1;x<9;x++){ //空白なら非合法手 if(board(py+x)!=BLANK){ continue; } //全ての方角で for(int i=0;i<8;i++){ d = DIRECTIONS[i]; p = py + x + d; //隣が敵の石じゃなかったら即アウト！ if(board(py+x+d) != -turn){ continue; } //隣が敵の石じゃなくなるまで一直線に探索。 while(board(p) == -turn){ p += d; } //自分の石にたどり着いたら合法、空白や壁だったら違法 if(board(p) == turn){ moves.push_back(py+x); break; } } } } legal_moves = moves; }
これでmove関数を繰り返すことで、ゲームにはなります。
まあこれだけじゃまともにオセロを遊ぶことはできませんが、そこには興味がないので。
//8×8ボードでの計算用 int output_move(int move){ return move%10 + move/10*8 -9; } //numpy用、機械学習のためにいらない壁を壊す vector<MatrixXd> feature(){ MatrixXd feature1 = MatrixXd::Zero(8,8); MatrixXd feature2 = MatrixXd::Zero(8,8); vector<MatrixXd> features; features.push_back(feature1); features.push_back(feature2); int t = turn==1 ? 0:1; for(int y=0;y<8;y++){ for(int x=0;x<8;x++){ if(board(y*10+x+11)==1)features[t](y,x)=1; if(board(y*10+x+11)==-1)features[1-t](y,x)=1; } } return features; } //python用 Board copy(){ Board board; board = *this; return board; } //確認用 void display(){ std::string stone[4] = {"○","□","●","■"}; for(int i=0;i<100;i++){ if(i%10==0)std::cout << "\n"; std::cout << stone[board(i)+1]; } } }; namespace py = pybind11; PYBIND11_MODULE(cboard,m) { py::class_<Board>(m, "CBoard") .def(py::init<>()) .def("move", &Board::move) .def("feature", &Board::feature) .def("output_move", &Board::output_move) .def("copy", &Board::copy) .def_readwrite("legal_moves", &Board::legal_moves) .def_readwrite("board", &Board::board) .def_readwrite("turn", &Board::turn); }
