Edited at

オセロAIを作ってみた結果【Kawaz Advent Calendar 2015】

More than 3 years have passed since last update.

この記事は、Kawaz Advent Calendar 2015の12月15日ぶんの記事です。札幌ゲーム制作者コミュニティKawazのサイト内に書いた記事 http://www.kawaz.org/blogs/h_hiro_/2015/12/17/800/ と同一のものです。


はじめに

今年10月より、Sapporo.cppの企画として「オセロAIの作成に取り組む」ということを行っています。ということで私が作ったものを紹介します。

なお、開発の際の話などは、C++ Advent Calendar 2015の12月16日ぶん(12月19日公開)「C++でコードレビューを受けて気づいたこととか」に書いています。

なおこのオセロAI企画は、Sapporo.cppのオンラインもくもく会(おおむね毎週1回実施。上記リンク先を参照)にて継続実施しています。オンラインで参加できますので、もし興味を持った方がいらっしゃったらご参加ください。

コードは https://github.com/sapporocpp/othello-shell/tree/hhiro-AdC2015 にあります。


おことわり

既存のオセロAIの戦術を勉強したわけではありません。あしからず。


基本方針


  • まずは「打つ手を選ぶ条件を手で次々記述していく」ことを実装する。

  • 次いで、「コンピュータに自動探索させる」ことを実装する。


方針1:打つ手を選ぶ条件を手で次々記述していく


  • 最初は、盤面全体を順に見ていって、置く場所は「ルール上置いてよい場所で最初に見つかったもの」を選ぶという処理を実装(M1)。

  • 次に、プログラムが簡単に書けそうな「石を打ったあと、自分の石がなるべく多くなるようにする」ものを実装(M2)。

  • 続いて、自分が小さいころに教えてもらった「角に置けるなら優先的に置く」「角の隣には極力置かない」をM2に加えたものを実装(M3)。

  • M3をもう少し発展させ、自分がオセロでどうやって手を選んでいるかを踏まえ、以下の判断を行うものを実装(M4)。


    • 角のマスは「優先度:最高」。

    • 辺上のマスは、それをもう相手に取られないことが確定するならば(注)「優先度:高」(角よりは優先しない)。

    • 角のマスの隣に置くのは「優先度:低」。ただし、対応する角のマスが自分の石であれば「優先度:普通

    • それ以外は「優先度:普通」。

    • 以上の評価基準により、優先度が並ぶ置き場所が複数あるならば、その石を置いた結果、自分の石で「角のマスにある石」「辺上のマスにある石」「周囲八方に他の石がある石」の数の合計が多くなるものを選ぶ(相手に取り返されにくい、という基準)。



(注)

ここでは、判定が容易な「辺上から自分の石を辿ることで、角にある自分の石に到達できる」ものに限って、「もう相手に取られないことが確定する」と扱う。例えばこの局面で、黒がAやCに石を置いた場合、左上の自分の黒石まで黒石が繋がった状態になり、AやCはもう相手に取られることはない。しかしBやDではそうとは限らない。

Fig-take-edge.png

これらを対局させた結果はこちら。各組み合わせについて先手・後手をそれぞれ持たせて対局させている。同じAI同士の対戦結果も掲載している。

先手\後手
M1
M2
M3
M4

M1
19\45

23\41

7\57

21\43

M2
30\34

19\45

22\42

3\60

M3

29\0

43\21
20\44

18\46

M4

49\15

50\0

39\25
26\38


  • M1: 1勝5敗(自身との対局除く。以下同様)

  • M2: 1勝5敗

  • M3: 4勝2敗

  • M4: 6勝0敗

私自身が打つつもりで組んだM4が最高の成績であった。とはいえ、対局結果を見ていると疑問な手もあった。例として、これはM4同士を対戦させたものなのだが、下の図で白がAに石を置いていた。これは直後にBが石を置くとすべて取り返されてしまうので、必ずではないとはいえ無駄な手のことが多い。今後(打つ手を選ぶ条件を手で次々記述していくという条件のもとでは)こういった状況を試しながら見つけていくことになるだろう。

Fig-noeffect.png


方針2:コンピュータに先読みさせる

ここで「コンピュータに先読みさせる」とは、相手の手の先読みを行うことで、最善の結果が出そうな自分の手を見つける、ということである。いわゆるゲーム木の探索である。

今回用いているのは、一番シンプルなミニマックス法というもので、自分の手と相手の手をシミュレーションする際に、自分の手はなるべく自分にとって評価値が高くなるものを、相手の手は自分にとってなるべく評価値が低くなるものを選ぶことを所定の手数(あるいは別の打ち切り条件)まで続ける。この処理は再帰を用いるとかなりシンプルにかける(ソースコード AI_M*_D*.hpp 中のtry_placeメソッド)。

なおミニマックス法を用いるには、評価値を用意しておく必要がある。これらは上記のM2~M4に合わせ、以下のように定める。


  • M2:盤面上の石の個数の両プレイヤー間の差(自分-相手)を評価値とする。

  • M3:角に石を置いた回数の両プレイヤー間の差(自分-相手)を評価値とする。それが一緒であれば、角の隣に石を置いた回数の両プレイヤー間の差(相手-自分)を評価値とする。それも一緒なら評価値は同じとする。

  • M4:「優先度最高」「優先度高」「優先度低」「優先度普通」の順で【自分の該当する石の個数-相手の該当する石の個数】を計算し(優先度低のみは自分と相手が逆)、高かったものを採用する(上位の優先度の基準で差が付いたら、下位の優先度の基準は考慮しない)。それでもすべて一致するなら、石の個数で判断する。


補足

さて先読みをする際に、今回は手数を決めて打ち切ったわけだが、もし「すべての手数まで先読みできる」とすれば(実際には計算時間上困難なのだが)、


  • 自分が必ず勝てる手を指せる

  • 自分がどう頑張っても勝てないとわかる(相手が必ず勝てる手を指せる)

  • 引き分けになる

のどれかに行き着く。これはオセロに限らず囲碁や将棋などでもほぼ同様なのだが、自分も相手も「指せる手の可能性」「それによって起こる盤面の変化」が明確に定められている(=自分がシミュレーションできる)ことに起因する。二人零和有限確定完全情報ゲーム - Wikipediaあたりを参照。


成績

実際に対戦させた結果は以下の通り。「D2」「D4」はそれぞれ、先読みする深さ(depth)を2手先・4手先までにしたことを意味する。

まずは先読みなしのAI。

AI名
先読みなしの
相手との戦績
先読みありの
相手との戦績
合計戦績

M1
1勝5敗
1勝11敗
2勝16敗

M2
1勝5敗
0勝12敗
1勝17敗

M3
4勝2敗
5勝 7敗
9勝 9敗

M4
6勝0敗
5勝 7敗
11勝 7敗

続いて先読みありのAI。

AI名
先読みなしの
相手との戦績
先読みありの
相手との戦績
合計戦績

M2-D2
4勝4敗
0勝10敗
4勝14敗

M2-D4
4勝4敗
3勝 7敗
7勝11敗

M3-D2
8勝0敗
8勝 2敗
16勝 2敗

M3-D4
5勝3敗
4勝 6敗
9勝 9敗

M4-D2
8勝0敗
7勝 3敗
15勝 3敗

M4-D4
8勝0敗
8勝 2敗
16勝 2敗

先読みありのAIは、先読みなしのAIと対局させた場合、M3やM4こそ強いもののM2はそこまで強くならなかった。これは、先読みを打ち切った直後に相手にいい反撃の手がある場合もあることに起因するとされている。

また、先読みなしのM3やM4は、M4-D2やM4-D4にこそ勝てていないものの、他の先読みありの方法には勝っていたりする。オセロでは、先読みの効果もあるにはあるものの、それ以上に手作業での手の構築が重要なのかな?と感じた結果であった。


まとめ


  • オセロAIを、まず自分で条件を逐一書いていって手を決める方法で作り、次いでそれに先読みさせることを加えるという形で作った。

  • オセロの場合、先読みで強くなるにはなるが、元となる指す手の条件がうまくできていないと先読みの効果は出てこない。


詳細な対戦戦績

先手\後手
M1
M2
M3
M4
M2-D2
M2-D4
M3-D2
M3-D4
M4-D2
M4-D4

M1
19\45

23\41

7\57

21\43

0\27

0\27

18\46

14\50

0\43

0\52

M2
30\34

19\45

22\42

3\60

5\59

0\31

9\55

18\46

8\56

20\44

M3

29\0

43\21
20\44

18\46

39\25

39\25
18\46

33\31
19\45

13\51

M4

49\15

50\0

39\25
26\38

37\26

45\19
27\37

36\28
11\52

25\39

M2-D2

55\7

47\17
20\44

0\41

4\60

27\37

21\43

27\37

18\46

12\52

M2-D4
17\47

48\16

35\29
5\59

38\26

36\28
29\35

23\41

15\49

3\60

M3-D2

35\29

39\25

46\18

43\21

56\8

49\15

37\27

38\26
29\35

36\28

M3-D4

34\30

46\18
31\33

39\25

43\21
31\33

30\34

42\22
29\35

50\14

M4-D2

50\0

62\2

47\17

46\18

56\4

56\8
27\37

37\27

35\29
12\52

M4-D4

62\2

55\9

44\20

46\18

59\1

54\10

44\20

59\5

41\23

37\27