オセロAIの教科書 3 【基礎】 1手読みAIを作る

にゃにゃん(山名琢翔)

2021年12月5日 00:00

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

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

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

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

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

オセロのルール
基礎的なプログラミングの知識・経験
C++

一番単純なAIを作る

この記事では最小構成でとりあえず動くオセロAIを作ることを目指します。サンプルコードを適宜挟むので、見ながら、動かしながらご覧ください。

評価関数

評価関数は単純ながらも結構強いと言われている、マス一つ一つに重みをつける手法を使います。

(その手番の石が置かれているところのマスの重みの合計) - (その手番でない方の石が置かれているところのマスの重みの合計)を評価値とします。評価値は値が大きければその手番が有利と判断します。

マスの評価は以下の画像のものを使います。

値はこちらのサイトを参考にしました。

私による実装です。

インデックスで管理していたボード情報をそのまま使うため、以下のevaluate_init関数で行のパターン6561種類について評価値を前計算しておきます。

void evaluate_init() {
    int idx, i, place, b, w;
    for (idx = 0; idx < n_line; ++idx) {
        b = create_one_color(idx, 0);
        w = create_one_color(idx, 1);
        for (i = 0; i < hw / 2; ++i)
            cell_score[i][idx] = 0;
        for (place = 0; place < hw; ++place) {
            for (i = 0; i < hw / 2; ++i) {
                cell_score[i][idx] += (1 & (b >> place)) * cell_weight[i * hw + place];
                cell_score[i][idx] -= (1 & (w >> place)) * cell_weight[i * hw + place];
            }
        }
    }
}

そして、evaluate関数で先程前計算した値を使います。
こうすることで評価関数が高速になり、後々嬉しくなります。

inline int evaluate(board b) {
    int res = 0, i;
    for (i = 0; i < hw / 2; ++i)
        res += cell_score[i][b.board_idx[i]];
    for (i = 0; i < hw / 2; ++i)
        res += cell_score[hw / 2 - 1 - i][b.board_idx[hw / 2 + i]];
    if (b.player == white)
        res = -res;
    return res;
}

前計算しない場合、インデックスを一般的な配列形式に変換して、さらにそこから64マス見ていくようなので結構遅いです(とは言え1手読みなら別に実用上問題はないのですが…)。今後読み手数を増やしていったときにかなりパフォーマンスに差が出るはずです。

なお、評価値は必ず整数値を取るようにしましょう。浮動小数点演算が遅いのはもちろん、後々のアルゴリズムで評価値が実数だと結構困ります。ちなみに私はやらかしたことがあります。

探索アルゴリズム

探索アルゴリズムは最小構成ということで、1手読み、つまり、与えられた局面から考えうる合法手それぞれを全部打ってみて、一番良さそうな手を選びます。

私による実装は以下です。

search関数で1手読みをしています。

evaluate関数(評価関数)はその盤面から打つ手番目線、つまりこの場合、AI目線ではなくて相手目線で評価される仕様にしているため、AI目線に戻すために-1を乗じた評価値の中で最大となる手を打ちます。以下はサンプルコードの抜粋です。

int search(board b) {
    int coord, max_score = -inf, res = -1, score;
    for (coord = 0; coord < hw2; ++coord) {
        if (b.legal(coord)) {
            score = -evaluate(b.move(coord));
            if (max_score < score) {
                max_score = score;
                res = coord;
            }
        }
    }
    return res;
}

動かしてみる

サンプルコードを使っている場合、こちらに書いた通りに実行すると以下の画面が出てきます。

使い方:

実行画面

$ g++ -O3 ai1_forward1.cpp -o ai.out
$ python3 main.py
AIの手番 0: 黒(先手) 1: 白(後手) :

手番(0か1)を入力してEnterを押すと、このような画面が出ます。

青いところが合法手です。クリックで着手できます。AIの手番になると自動で着手されます。下の石数表示の隣にアスタリスクがついている方が着手する番です。

どうでしたか？私はこんな感じで終局しました。私(黒) vs AI(白)です。

適当に打つと負けてしまうくらいには強いと思います。

1手読みで単純な評価関数を使ってもそれなりに強いAIが作れます。

まとめ

今回は一番単純な構成でオセロAIを作ってみました。単純な構成ではあるものの、それなりの強さのAIが作れたと思います。

盤面の重みの参考にしたサイトにある通り、この評価関数ではとても強力なオセロAIは作れません。しかし、多くの人よりも強い評価関数としてかなり優秀なので今後もしばらく使っていきます。

今後何回かは探索アルゴリズムを深めていきます。

次回予告

次回は1手より多く、2手、3手と読む場合に有効なアルゴリズムであるminimax法を学びます。

スキと投げ銭で喜びます

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

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

ここから先は

0字

¥ 100

期間限定 PayPay支払いすると抽選でお得に！

ログイン

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