ゆーいちろーブログ

コンピュータに関することや思ったことをふわふわ書きます.

オセロAIを作る

この記事は 熊本高専 Advent Calendar 2017 - Adventar の18日目の記事です.

こんにちは,ゆーいちろーです. 寒くなってきましたね,お元気ですか?
わたしはげんきです.

気がついたら以前の投稿から1年近く経っていました.
日常的に色々アウトプットしていけたらいいなあと思います.

みなさんはオセロは得意ですか? 私は苦手です. 友達に勝負を持ちかけてボコボコにされることがしょっちゅうです. 途中までは勝ってることもあるのですが(汗)

将棋や囲碁ならまだしも,盤面や合法手の少ないオセロで負けたくはないです. 練習するためにもそもそも一緒にオセロをする友達もいない,ということで,今回はオセロを一緒にプレイしてくれるAI(AIという言葉を気軽に使いたくはないのですが)を作りました. 強いオセロプレイヤーのお気持ちが分かるかもしれない!!!

TL;DR

お前の説明なんて聞きたくねえ,コード読ませろ/実行させろという方は以下へ.
GitHub - y1r/reversi: reversi/othello game in c++.

ゲームAIの手法

ゲームには,たいていの場合盤面が存在します. その盤面に対して,プレイヤーが何らかの操作を行うことで,新しい盤面が生成されます. そのため,ある盤面に対して親の盤面や子の盤面が存在するため,ゲームの状態を保存するために木を用います.

ゲーム木について,大きな特徴が2つあります.

ゲームには相手がいること

そのため,現在の盤面から,勝ちを意味する盤面への経路が見つかったとしても,相手がその経路を選ばなければ勝つことができません. そのため,相手が最善の手を指すことを仮定してグラフの探索を行います.

ゲーム木は巨大であること

言うまでもありません.

その木を探索する手法として,以下のものがあると言われています.

雑に説明します.

ミニマックス法について

ポピュラーな手法です.名前を聞いたことがある方も多いと思います. この探索の方法は,相手が最善の手を指すことを仮定します. また,ゲーム木を終局まで全て読んでしまうことは非常につらいので,盤面にスコアをつける評価関数を定義します.

探索の例を何個か挙げてみます.

1手先を読んで手を決める場合

現在の盤面から自分が指しうる盤面を全て列挙します. その中で,最も良いと評価される盤面を選びます. 非常に簡単ですね.

2手先を読んで手を決める場合

現在の盤面から自分が指しうる盤面を全て列挙し,その盤面をB_i, 評価関数の値を  f(B_i) とします.
その盤面 B_i から,相手が指しうる盤面を全て列挙し,それらを {B_{ij}} とします.
相手は最善の手を打つので,つまり,
(相手の)評価関数が最大になるように打つ⇔(自分の)評価関数が最小になるように打つ.
よって相手の打ち手は, 自分の打ち手が {B_{i}} だと決まっている時,  \displaystyle
\min_j f(B_{ij})
です. この手を最大化したいので,実際に自分が打つべき手は,  \displaystyle
\max_i \min_j f(B_{ij})
になります. これがミニマックス法です.これを再帰的にmaxとminを入れ替えながら繰り返していきます.

α-β法について

得られる結果はミニマックス法と同じですが,計算が高速になっています. maxやminを使うため,ある盤面の評価値は,子盤面を全て調べなくても,値の範囲を少しずつ絞っていくことができます. そのため,明らかに計算しなくて良い盤面が存在し,その枝刈りを行うことで計算を高速化することができます.

MCTS; Monte Carlo Tree Searchについて

しかし,盤面の評価関数を作ることは一般にそう簡単ではありません. オセロの場合だと,現在自分の石が何個ある,という関数を作れば,これを最大化することは,勝利に結びつくことは分かります. しかし,囲碁の場合だと,そう簡単ではないと思います(私は囲碁は分かりません)(?)

そのため,評価関数なしで使える探索の手法があると便利だと思います. MCTSは,評価関数なしで使える探索の手法です. ゲーム木をある程度展開したあと,その盤面から,ランダムに合法手を繰り返し,終局までゲームを進めます. 終局してしまえば,ゲームの勝ち負けを判定することは難しくないため,勝ち負けを評価し, より多く勝った盤面が良さそうであり,次に選ぶべき手である,ということになります(Pure Monte Carlo Tree Search). 実際に使われる場面では,より多く勝った盤面についてはまた展開して,より詳細に調べる,ということを行ったりするらしいです. 詳しいことはMonte Carlo tree search - Wikipediaを読んでいただけると良いかもしれません.

今回実装した手法

手法について説明したので,次は今回の実装について.

ミニマックス法

reversi/mini_max.h at master · y1r/reversi · GitHub

auto Search(const GameBoard<N> &game_board, int remain_depth, bool min_mode) {
    int good_score = min_mode ? INT_MAX : INT_MIN;
    bool placeable = false;
    int good_x, good_y;

    // 深度制限
    if (remain_depth == 0)
        return std::make_pair(game_board.count(my_disk_), Position(-1, -1));

    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            // 総当り
            if (game_board.CanPlaceDisk(x, y)) {
                // 合法手
                placeable = true;
                GameBoard<N> next = game_board;
                next.PlaceDisk(x, y);
                auto result = Search( next,
                                      remain_depth - 1,
                                      !min_mode); // min<->max
                if (min_mode) {
                    if (result.first < good_score) {
                        // 最小値更新
                        good_score = result.first;
                        good_x = x;
                        good_y = y;
                    }
                } else {
                    if (good_score < result.first) {
                        // 最大値更新
                        good_score = result.first;
                        good_x = x;
                        good_y = y;
                    }
                }
            }
        }
    }

    // 終局
    if (!placeable)
        return std::make_pair(game_board.count(my_disk_), Position(-1, -1));

    // bestな解を返す
    return std::make_pair(good_score, Position(good_x, good_y));
}

深さ制限をつけて全探索,min or maxを毎回入れ替えていく感じです.

α-β法

reversi/alpha_beta.h at master · y1r/reversi · GitHub

ミニマックス法に枝刈りを追加したものです.

実行してみる

git clone https://github.com/y1r/reversi
cd reversi
cmake .
make
./reversi -a 8 -m 7
# This means "run reversi with alpha-beta(depth=8) and MiniMax(depth=7)"
./reversi [BLACK] [WHITE]
[BLACK|WHITE]
         -a [search_depth]; alphabeta-method
         -m [search_depth]; minimax-method
         -u; user
         -r; random

ミニマックス法とα-β法の実行時間比較

$ ./reversi -a 8 -m 8
(省略)
Black_elapsed:0.350052[s] # α-β法
White_elapsed:95.5096[s] # ミニマックス法

まとめ

ゲーム木探索楽しい! α-β法はミニマックス法よりもかなり早いので,評価関数を定義できるときはα-β法を使おう. MCTSまで手が回ると良かったんですが...(手が空いたら試してみます)

あと,今日で21歳になりました. もし,なにか私にプレゼントを贈りたいという物好きな方がいらっしゃいましたら,http://amzn.asia/25RsGYQからお願いします.

明日は体調不良芸人❄ (@lmdexpr) | Twitterさんの記事です!楽しみです!

読んでいただきありがとうございました. アドベントカレンダーのようなきっかけがないと記事はなかなか書かないので,非常に良い機会でした. アドベントカレンダーを立ててくださった@owatahatenaさんありがとうございます!面白かったです.

Java8の関数インターフェースの(de)Serializationで発生しがちなトラブル

こんにちは,ゆーいちろーです. 初記事になります.

Java8から,関数インターフェース,ラムダ式が導入されました. Serializationまで行え,非常に便利で実装の幅が広がりますが, 気をつけておかないと問題になることがあります. 僕はこれでクリスマスを溶かしました(笑)

続きを読む