コンピュータとオセロ対戦13 ～機械学習、考察～

前回

今回の目標

シリーズの11及び12でなかなか上手くいかなかったので、その考察を行いたいと思います。

ここから本編

11

11では最適なデータ集め方法について検討しました。
オセロAIの説明でよく「対戦データを学習」といいますが、具体的に何を学習するべきかを考えました。

1hand_2select

この手法のアルゴリズムは以下の通りです。

1. 次の手で、「一番多くひっくりかえせる場所」「二番目に多くひっくりかえせる場所」を探す。
2. そのうちどちらかにランダムで置く。
3. たまたま勝った時のデータを記録しておく。
4. 機械学習。

ここでデータとは、具体的には

• 現在のスコア
• 一番多くひっくりかえせる場所に置いた時のスコア
• 二番目に多くひっくりかえせる場所に置いた時のスコア
• 「一番多くひっくりかえせる場所」と「二番目に多くひっくりかえせる場所」、どちらに置いたか

の四つです。ここでスコアとは、「自分の駒の数 - 相手の駒の数」のことです。

なお正解率は約0.5となりました。
選択肢が二つなので、ほとんど学習していません。

ここで考えたいのは「なぜ学習しなかったか？」ですが、よく考えれば当然のことでした。
なぜなら「現在のスコア」「一番多くひっくりかえせる場所に置いた時のスコア」「二番目に多くひっくりかえせる場所に置いた時のスコア」は、盤面状況やこの後どこに置くかといった状態にかかわらず常にほぼ一定ですよね。その大きさが「現在＜二番目＜一番目」となる関係は常に変わらず、このデータがのちの判断に及ぼす影響はほぼないといえるでしょう。

1hand_3select

上の1hand_2selectに加え、「三番目に多くひっくりかえせる場所」を考慮し、データにも「三番目に多くひっくりかえせる場所に置いた時のスコア」を追加しました。が、上手く行きませんでした。
おそらく上と同じ理由ですね。

1hand_3select_n

上の1hand_3selectに加え、現在のターン数も判断基準に加えてみました。
これについては一見成功しそうに見えました。なぜなら、オセロゲームにおいて中盤の有利は終盤で簡単に覆されるからです。むしろ中盤は相手を抑えすぎずに中立からやや劣勢を保ったほうが終盤で有利に立ちやすいとも言えます。そのためターン数を考慮に入れた学習は効果がありそうでした。

それでも成功しなかった理由として、ターン数という考え方自体は間違っていなかったと思いますが、やはり他のデータ(現在のスコアなど)があまりにも判断に影響がなかった、ということがあると思います。そのため説明変数が実質1つしかないような学習状況となり、学習が失敗したと考えられます。

3history

次に考えたのは、過去のスコアから次に置く場所を決定するアルゴリズムです。
具体的には、過去三回のスコアから判別します。

これも一見成功しそうですが、しませんでした。

理由として考えられるのは、やはり過去のスコアは判断材料になりえない、ということだと思います。確かに今考えてみれば、私たち人間がオセロをプレイするときも過去の戦況は気にしないですし、過去の戦況が未来の戦況に影響を与えることもないです。

3history_n

今度は、「今までに選んだ1～3番目の記録」から、「今から1～3番目にひっくりかえせる場所のうちどれを選ぶか？」を決定することを考えました。
名前で3historyになにか追加したものだと思うかもしれませんが履歴を使うということ以外共通点はありません。

これも上手く行かなかったのですが、理由としてはやはり3historyと同じように過去の戦況が判断材料になることはない、ということです。

逆に言えば、「未来に起こるかもしれない戦況」「未来の履歴(日本語がおかしいですが・・・)」は判断材料になりえるのでは？　と考えられます。

turnnum_and_num

「今が何ターン目なのか」、「自分の駒の数」、「相手の駒の数」から「1～3番目にひっくりかえせる場所のうちどれを選ぶか？」を考えてみました。

上記したとおり、終盤と中盤では異なる戦略が必要となります。そのため「今が何ターン目なのか」、「自分の駒の数」、「相手の駒の数」を考慮しながら駒を進めれば上手く行くのでは、という考えでした。例えば終盤なのに不利な状況ならたくさんひっくりかえせる場所に置くべきですし、中盤で有利なら終盤を見据えてそれ以上とりすぎないように工夫しなければならないですよね。

が、これもあまり関係なかったです。「自分の駒の数」と「相手の駒の数」の関係は必ずしもスコアの大小には依存しません。そのため、1hand_2select等とは違う理由で上手く行かなかったはずです。

理由の一つとして考えられるのは、「今が何ターン目なのか」と「自分の駒の数」から「相手の駒の数はある程度予想できます。そのため説明変数が実質2つしかなかったとも言えます。

考察してみると悪くない手法に思えてきました。意味のある説明変数を増やすことができれば上手く行くかもしれません。

customscore

ボード上の四隅など、とっていると有利になれる場所に重みを付け、その累計を「カスタムスコア」と名付けました。
そのカスタムスコアから予測してみます。
つまり、「現在のターン数」、「自分のカスタムスコア」、「相手のカスタムスコア」を考慮して学習させてみました。

これも上手く行きませんでした。
turnnum_and_numと違い説明変数はきちんと3つあります(「今が何ターン目なのか」と「自分のカスタムスコア」から「相手のカスタムスコア」は予想できないため)。それに単なるスコアに比べ戦況を正しく眺められる利点もあるので上手く行くはずです。

それでも上手く行かなかった理由として、まず、カスタムスコアの設定が甘かったことが考えられます。今回、隅を10点、隅以外の対角線上を5点、それ以外を1点と設定していました。しかしよく考えれば隅のすぐ横には極力置きたくないのに、5点も与えられることがあるのは問題です。そもそも位置ごとにスコアを固定せず、戦況を正しく得点化できるような適したカスタムスコアを設定する必要があるはずです。

しかし、こちらも逆に考えれば、適したカスタムスコアさえ設定できれば上手く行く可能性は非常に高いといえます。

turnnum_and_num_

「今が何ターン目なのか」、「置いた後の自分の駒の数」、「置いた後の相手の駒の数」から「1～3番目にひっくりかえせる場所のうちどれを選ぶか？」を考えました。

他の方法と比べるとなぜか正解率は向上していました。

理由は主に2つ考えられます。

1つ目の理由として、そもそもたくさんひっくりかえせる場所に置くほど、「置いた後の自分の駒の数」と「置いた後の相手の駒の数」の差は大きくなる！　というのはあると思います。
身も蓋もないですが、この予想が正しければ、学習はしているもののオセロが強くなるわけではない、という本末転倒な事態になっていることが分かります。

2つ目の理由として、今までの考察からもわかる通り過去の情報、履歴はあまり判断に影響を及ぼしません。そういう意味では今回初めて「未来の情報」を判断に使った、と言えます。とはいえ実装するにおいて、「この箇所に置いた時の情報」だけを使う！　というのは現実的ではないため改善の必要性は大いにあると思います。

11のまとめ

全体として、

• 現在のスコアは説明変数として価値が低い
• 履歴や過去のスコアは説明変数として価値が低い
• 逆に、未来の情報は説明変数として価値が高いかもしれない
• ターン数を用いるのはありかもしれない
• 適したカスタムスコアを設定できれば、非常に有用かもしれない

と言えそうです。また、今後使えそうなアイディアとして以下が挙げられます。

• 未来の戦況を説明変数として使う
• ターン数と現在の戦況(カスタムスコアにより得点化)を説明変数とする
• 各箇所に置いた後の情報全てを説明変数として使う

12

12では11で考案した方法を改良し、より学習の正解率が上がるようにデータ集め方法と学習方法の2つの観点から改良を行いました。

データ集め方法の検討

まずは前回決めたデータ集め方法を少しいじり、より正解率が上がらないか試しました。
それぞれの案で前回のプログラムを少し変更したものを使いました。

turnnum_and_num_

これは11で考案した、「今が何ターン目なのか」、「置いた後の自分の駒の数」、「置いた後の相手の駒の数」から「1～3番目にひっくりかえせる場所のうちどれを選ぶか？」を考えるアルゴリズムです。
これを基盤とし、少し改造したものがいかに示す8つです。

turnnum_and_num_all

これまでは、ゲーム終了時にボードが埋まっている状況のデータだけを集めていましたが、わずかではありますがそうではない終わり方も存在します。
そういったデータも集め、すべての対戦データから学習を行ってみました。

結論から言うと正解率はほぼ変わりませんでした。

理由は明白で、ボードが埋まっていない状況で終了することなんてほぼないため全体としてみれば影響なんてごくわずかのはずです。

turnnum_and_num_very

上記のturnnum_and_num_ではゲーム終了時にボードが埋まっている状況のデータだけを集めていましたが、逆に、ゲーム終了時にボードが埋まっていない時のデータのみを集めてみました。つまり、圧勝したデータのみを集めたということです。

学習の正解率はかなり高くなりました。理由としては二つ考えられると思います。

一つ目の理由として考えられるのは、圧勝したということは「一番多くひっくりかえせる場所」により多く置いた中で、たまたま勝てたデータだけが集まったからというのが考えられます。
つまりturnnum_and_num_の考察と同様、学習はしているもののオセロが強くなっているわけではない、という状況に陥っている可能性があります。

なおPythonプログラムを用いて「一番目に多くひっくりかえせる場所」、「二番目に多くひっくりかえせる場所」、「三番目に多くひっくりかえせる場所」、それぞれ何回置いたかを調べました。
調べたプログラムと結果は以下の通りです。

research.py

x = []
y = []

with open("whitedata.txt", "r") as data:
    for num in data:
        x.append([])
        for i in range(3):
            x[-1].append(int(num[0:3]))
            num = num[3:]
        y.append(int(num.strip("\n")))
        if y[-1] == -1:
            del x[-1]
            del y[-1]

num = [0, 0, 0]

for i in y:
    num[i] += 1

for i in range(3):
    print("num%d: " % (i + 1), num[i])

num1:  8118
num2:  5723
num3:  5543

やはり「一番多くひっくりかえせる場所」に置いた回数が多いですね。
参考までに他のデータ集め方法での値は以下の通りです。

turnnum_and_num_:
num1:  9327
num2:  9112
num3:  9080
turnnum_and_num_all:
num1:  14609
num2:  8939
num3:  8861

謎が増えてしまいました。
実はデータ集めの際、打てる場所が3つもない場合をデータから省いていたので、総数の差があることは問題ではありません。特に「turnnum_and_num_very」の圧勝データは、一つ一つの試合のターン数が少ないことから総データ量も自然に少なくなりますし、記録する試合数が増えるため「turnnum_and_num_all」のデータ数が「turnnum_and_num_」より多くなるのは当然です。
この結果になった理由として考えられることとすれば、「ボードが埋まらずに終了する試合数が、予想より多かったのでは？」というものです。
しかし、以下のプログラムで一万回試合を行い調べたところそうでもないようです。

data_full.c

void main(void) {
    double start = clock();

    int turn_num;
    int full = 0, notfull = 0;
    bool can, old_can;

    for (int num = 0; num < NUM; num++){
        setup();
        srand((unsigned int)time(NULL) + num);

        while (!win()){
            turn = BLACK;
            can = true, old_can = true;
            turn_num = 0;
            setup();
            // printb();
            while ((can = check_all()) || old_can){
                if (can){
                    think(turn_num);
                    // printb();
                    turn_num++;
                }
                old_can = can;
                turn = 3 - turn;
            }
        }

        if (turn_num == SIZE * SIZE - 4) full++;
        else notfull++;
    }

    printf("full: %d, not full: %d\n", full, notfull);
    printf("実行時間: %.4lf[s]\n", (clock() - start) / 1000000);
}

full: 9986, not full: 14

全ての現象について考察するつもりでしたが、これは謎すぎて分かりません。

二つ目の理由として、ポジティブな見方をすれば、圧勝した試合には何かしらの共通点があったのでは？　とも予想できます。つまり、ボードが埋まらない状態でゲームが終了するという特殊な状況ということは、よりテクニカルに勝つことができた、と言えるのでは？　ということです。

turnnum_and_num_time

序盤、中盤、終盤にデータを分け学習させました。
が、上手く行きませんでした。

これに関してはシンプルに、コンピュータ自身が時間経過とともに戦略を変えたりしたわけでもないという単純さが浮き彫りになっただけだと考えます。
時間ごとのデータもばらつきはありませんでした。
序盤と終盤でデータ数の総量が少ないのは、そもそも三か所も置ける場所がないという状況が多かったためだと思います。

whitedata1.txt: 
num1:  4563
num2:  4554
num3:  4594
whitedata2.txt: 
num1:  5837
num2:  5710
num3:  5614
whitedata3.txt: 
num1:  4600
num2:  4646
num3:  4610

turnnum_and_num_state

現在のスコアから、優勢である時と劣勢である時を分けて学習させました。
記事には書きませんでしたが、勝っているときのデータのほうが量が多かったです。最終的に勝ったデータを集めると、やはり全体として優勢であることが多いようです。
下のデータを見ると、負けているときほど「三番目」が多く、勝っているときほど「一番目」が大きいことが分かります。
つまり正解率が高かった理由としては、単純に置いた後の結果から予測がしやすかったのではないでしょうか。

whitedatalose.txt: 
num1:  2425
num2:  3663
num3:  4846
whitedatawin.txt: 
num1:  12454
num2:  11311
num3:  10092

turnnum_and_num_random

プレイヤー(役)がランダムに打ち返した時のデータを集め学習させました。
なぜか正解率が高かったものです。

一つの理由として考えられるのは、今までと違い相手が様々な手法で打ち返してきたことでよりいろいろなデータを集めることができたから、というのが言えるのではないでしょうか。
今までは型にはまった対戦しかしていませんでしたが、自由な対戦データを得ることは重要なことなのかもしれません。

turnnum_and_num_various

turnnum_and_num_randomは相手が常にランダムに打ち返してきていましたが、ここでは

• ランダムに返す
• 一手先まで読んで返す
• 二手先まで読んで返す
• n手先まで読んで返す

のいずれかをランダムで選ぶデータを集めました。

正解率が若干上がった理由はturnnum_and_num_randomと同様だと考えます。
turnnum_and_num_randomほどではなかったのは、ある程度型にはまった打ち返しが多かったからでしょう。

turnnum_and_num_middle

最初の何手かと最後の何手かのデータを集めずに学習させてみました。
正解率は改善しませんでした。

理由としてはやはり、最初の何手かと最後の何手かにおいて、打てる場所が三か所もないということ、またturnnum_and_num_timeと同じように、コンピュータ自身が時間経過とともに戦略を変えたりしたわけではないからという2つが挙げられると思います。

turnnum_and_num_state_various

turnnum_and_num_stateとturnnum_and_num_variousを合体させました。
つまり、プレイヤー(役)は

• ランダムに返す
• 一手先まで読んで返す
• 二手先まで読んで返す
• n手先まで読んで返す

のいずれかの手法で打ち返し、コンピュータは、自分が優勢である時と劣勢である時のデータを分けて保存しそれぞれ学習します。

turnnum_and_num_variousを選んだのは、randomの方は現実的ではないと考えたからですが、上の考察からむしろrandomのほうが適している可能性があると考えられます。

また正解率が向上したのは単純に相乗効果ではないでしょうか。

データ集め方法のまとめ

11考察のまとめから、そもそも基盤となった方針が間違っていたことが分かりましたが、一応改善案は見つかりました。

まず、集めるデータの種類ですが、「圧勝したものだけを集める」というのはあまりよくないのでは？　と考えました。
理由は考察に書いたように、データ内に「1番目」の数が多いだけではないかという疑惑がぬぐえないからです。
かといってすべての試合結果を用いるのも、データに偏りが出る理由が分からない以上危険と判断しました。
これまで通り盤面が埋まった状態で終わったデータを集めるべきと思います。

試合展開ごとにデータを集めるのもあまりいい方法に思えません。正解率があまり高くならなかっただけでなく、「最終的に勝ったのだからそりゃそうなるよね」というデータしか集まらないからです。

プレイヤー(役)がコンピュータと異なる手法で打ち返す案ですが、これについては検討の余地があると思います。正解率が向上した理由に、強いAIづくりにおいて有利に働きそうな「相手が様々な手法で打ち返してきたことでよりいろいろなデータを集めることができたから」というのがあるからです。
とはいえ予想が間違っている可能性もあるので、まだ断定はできませんが。

学習方法の検討

次に学習方法についての検討を行いました。
正解率が軒並み高かったから、という理由で決定木に絞り学習を行いました。

criterion

不純度に使う手法の指定です。
giniとentropyを試しましたが、どちらもほぼ同じ正解率となりました。
今回学習してもらったのは分類問題ですが、なぜか差がない結果に。
ひょっとして三つの分類なのがいけなかったのか？と思い1hand_2selectのデータで試してみたものの、下に示すように似たような結果になりました。
機械学習は詳しくないですが、これに関しては決定木自身の仕様のようなものだと考えました。
調べてみたところ、グラフの形自体はどちらも同じようです。(参考文献)

entropy: 
train score:     0.5234653415650253
test score:  0.4985361283522661 

gini: 
train score:     0.5274808010841741
test score:  0.5020494203068275

splitter

これに関しては知識がないため何とも言えませんが、正解率がほぼ変わらない以上どちらでもいいのでは？　と考えました。

max_features

今回説明変数が三つしかなかったため、max_featuresをどう指定しようと同じ正解率になりました。
これに関しては説明変数を増やして再検証しないことには何とも言えません。

max_depth

これは分かりやすい結果になりました。
「深くすればするほど正解率は上がるが過学習も起こりやすくなる」という教科書通りの特徴が表れていました。

min_samples_split

調べたところ、少数を指定すると全サンプルサイズに対する割合になるそうですね。本来は0.01とかでやるみたいです(参考文献)。
実際にやってみた。
分割に使うデータ数は少ないほうがいい理由が分かりませんが、とにかく少ないほうがいいということが分かりました。
少ないほうがザックリではなくハッキリ対応できるからでしょうか？

min_samples_leaf

こちらも教科書丸写しかのように、きれいに特徴が表れていました。
特に考察することはありません。

max_leaf_nodes

数を増やすほど過学習が起きやすくなっていることは納得できるのですが、今までは過学習が起きてもテストデータでの正解率が下がるというのはあまりなかったです。

max_depthについても横軸の数字を極端に増やして学習させてみたところ、やはりmax_leaf_nodesのように正解率が下がるということはありません。

なのでこれはmax_leaf_nodes特有の特徴ではないかと考えました。
深さに関しては、説明変数が少ないことで「これ以上深さを増やしても意味がない」というポイントがどこかに存在するのではないか、と思いました。もし説明変数が多ければ、max_leaf_nodesのようにどこかで正解率が下がるのでは？　ということです。

説明変数の数が少ないにもかかわらずmax_leaf_nodesで正解率が下がった理由ですが、葉の数が増えれば増えるほど「過学習よりも学習しすぎな状態」に陥るのではないか、と考えました。
とくにmax_leaf_nodesが500の時、一つ一つの葉に属するデータ数はこの場合平均してわずか6個です。あまりにもトレーニングデータに適合しすぎた結果、新しいデータ(テストデータ)に全く対応できず、正解率を下げる要因になったのでは？　と考えました。
なお今回使用したデータの数は以下の通りです。

num1:  10581
num2:  10591
num3:  11734

学習完成版

上記の検証で特に上手く行ったパラメータを集めて学習しなおしましたが、ぱっとしない正解率になりました。検証ではどれも0.6程度の正解率が出ていたにもかかわらず、です。
理由としてはやはり、実際の学習では様々なパラメータを使うのだから、一つ一つのパラメータで結果を出すより組み合わせることによって正解率が高くなるパラメータを探すべきだった、ということだと思います。

学習方法のまとめ

説明変数が少ないため、まだ分からないことが多いです。
分かったこととしては、パラメータは総当たりで調べるべき！　ということです。

改善案まとめ

• 未来の戦況を説明変数として使う
• ターン数と現在の戦況(カスタムスコアにより得点化)を説明変数とする
• 各箇所に置いた後の情報全てを説明変数として使う
• プレイヤー(役)にはランダムで打ち返してもらう(あまり意味はないかも)
• 機械学習のパラメータは総当たりで調べる

フルバージョン

実は、今回様々な検証をするにおいて、どの検証にどのデータやプログラムを使ったかを把握しきれなくなってしまいました。
今後はこういうことがないよう気を付けます。

実際にやってみた

やってません。

次回は

勉強会やります。

次回