PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

ありかつこうい
9 years ago
Views:

1 ゲーム木の探索についてミニマックス法のアルゴリズムアルファベータ法のアルゴリズ三目並べゲームの例 1

2 ゲーム TicTacToe Othello Chess Let us find game and play! 三目並べオセロ将棋 2

3 ゲーム木の探索問題ゲームは AI における最も古くから力を入れられている分野の 1 つです限られた時間の中で答えを見つけることはとても難しいゲーム木は人工知能で重要であり最良の手はゲーム木を探索することで得られミニマックス法などのアルゴリズムを使用する三目並べのゲーム木は小さいので探索も容易だがチェスなどの完全ゲーム木は大きすぎて全体を探索することができないその場合は代わりに部分ゲーム木を使う. チェスゲームでは 35 通りの置き方がありレイヤーは 50 回移動することができるつまり探索木には合わせるともの葉が存在することになりますこのような複雑なゲームにはある程度の場所で妥協する必要がありますこれは情報がないのではなくいかなる動きに対する正確な結果を計算する時間がないからですこの点でゲームは標準的な検索問題よりも現実の世界に似ていますまずはじめに三目並べを例に理論上最高の手を見つける方法を分析することから始めましょう 3

4 2 人のゲームの探索ゲーム木は人工知能で重要であり最良の手はゲーム木を探索することで得られミニマックス法などのアルゴリズムを使用する問題は以下の要素から構成されます : 初期状態定められた動き終了状態評価関数 : +1(+10, +99), -1 (-10, -99), または 0 のように数値 ( 評価値 ) を与えます. コンピュータは相手が取りうる動き ( 手 ) の中で正しい動き ( 手 ) を含む戦略を見つけなければなりませんそして最終状態の勝者を導き出しその流れの最初の一手を選びます重要 : 評価関数はどの動きが最高の動きであるかを決定するじゅうような構成要素です 4

5 ミニマックス法考え方自分の手では局面が最良になる手を選びたい相手は ( 自分にとって ) 局面が最悪となる手を選ぶだろう相手が自分にとってまずい手を打ってきてもそのまずさ (Min) があまり悪くない手 (Max) を打とう

6 ミニマックス法もう少し詳しく今自分が打てる複数の候補手を考えた時それぞれの手に関して相手の対抗手 ( これもまた複数 ) を探索するこの時対抗手の評価値を全て計算するその中で最小の評価値 ( 相手にとっては最高の評価値 )hを求める自分の候補手の中で最も高い評価値である手を最適なものとする自分の手では評価値が max, 相手の手では評価値が min となる手を選択

7 5 つのステップから構成されます : ゲーム木の全体を生成する. 木の末端ノードに評価値を得るために効用関数を適用する. この評価値を探索木の1つ上のレベルのノードの評価値を得るために使う ( どちらの手番かによってどのノードの評価値を選ぶかは変わる ). これを末端から根まで繰り返す. コンピュータは最も評価値の高いものを選ぶ. 3 L1 (return maximum in L2) A 1 A 2 A L2 (return minimum in L3) A 11 A 12 A 13 A 22 A 23 A 21 A 31 A 32 A L3(return 評価値 ) 7

8 ゲーム木の全体を生成する完全木例 : 三目並べゲーム木 9 9*8 9*8*7 9*8*7*6 9*8*7*6*5 8

9 MinMax - Searching tree - Ex: Tic-Tac-Toe (symmetrical positions removed) - 対称性

10 - Min-Max 探索における評価値の動きの例

11 演習 1 Fill in the return value at each blank node 11

12 どのように実装するか 1. 自分が打てる複数の候補手を考えた時それぞれの手に関して相手の対抗手を探索する 1. これを深読みレベルまで繰り返す 2. 木の末端まで来た時評価値を計算する 2. 子ノードから返された評価値比較する 1. AI( 自分 ) のターンなら最大を選択する 2. プレイヤー ( 相手 ) のターンなら最小を選択する 3. 評価値を親ノードへと返す 1. 自分自身が子ノードの場合選ばれた評価値を親ノードへ返す 2. 根の場合最適な場所を返す

13 三目並べの例評価値 h = h0 h1 h0: 自分の石だけが置かれている縦横斜めの列数 h1: 相手の石だけが置かれている縦横斜めの列数 -99 比較 -99 比較 0 Select 現在の状態自分 ( 黒石 ) の手 Max 白勝利評価最悪 -99 m i n h=-1 (1-2) m i n h=-1 (0-1) m i n h=0 (0-0) 比較白勝利評価最悪比較比較 -99 h=1 (1-0) 相手の手 Min

14 X: Win +99 O: Win -99 O: Win -99 X: Win +99 X: Win +99

15 1 1.2 コード部分 public int minmax(boolean flag, int level) { String my; // 現在の手 int value; // 評価値 int child; // 子ノードからくる評価値 // うつ場所 int bestposition = -99; // 仮 if (level == 0) { return evaluation(flag); if (flag) { // AI ターンでの初期化 value = -999; my = "O"; else { // プレイヤーターンでの初期化 value = 999; my = "X"; // 評価値を計算する for (int i = 0; i < size * size; i++) { if (buttons[i].getlabel().equals("")) { buttons[i].setlabel(my); if (check(flag)) { buttons[i].setlabel(""); if (!flag) return -1000; else return i; // 次の手に移動ここで子ノードの評価値が帰ってくる child = minmax(!flag, level - 1); 1.1 flag : AI の手のとき true プレイヤーの手のとき false level : 先読みのレベル 2 3 if (flag) { // AIならノードの中で最大の評価値を選ぶ if (child >= value) { value = child; bestposition = i; else { // プレイヤーならノードの中で最小の評価値を選ぶ if (child <= value) { value = child; bestposition = i; buttons[i].setlabel(""); if (level == SEARCH_LEVEL) { // 根 if (bestposition == -99) { // CPの負けが確実 JOptionPane.showMessageDialog(null, " まいりました "); System.exit(0); return bestposition; else { // 子ノード return value; // 評価値を返す

16 イメージ 1 minmax(true, SEARCH_LEVEL); level 3 自分の手 level 2 相手の手 level 1 自分の手 minmax(true, 3) 打てる部分を全て試す for (int i = 0; i < size * size; i++) { if (buttons[i].getlabel().equals("")) { buttons[i].setlabel(my); 次の手を考える minmax(false, level-1); minmax(false, 2) 打てる部分を全て試す for (int i = 0; i < size * size; i++) { if (buttons[i].getlabel().equals("")) { buttons[i].setlabel(my); 次の手を考える minmax(true, level-1);

17 イメージ 2 level 3 自分の手 minmax(ture, 1) 打てる部分を全て試す for (int i = 0; i < size * size; i++) { if (buttons[i].getlabel().equals("")) { buttons[i].setlabel(my); level 2 相手の手次の手を考える minmax(false, level-1); level 1 自分の手 level 0 評価値 minmax(false, 0) レベルが 0 なので親ノード if (level == 0) { return evaluation(flag); // 評価値を計算する evaluation(false) 評価値を計算して返す

18 イメージ 3 level 3 自分の手 Max level 2 相手の手 Min level 1 自分の手 Max minmax(false, 2) else { if (child <= value) { value = child; bestposition = i; Levelは2なので親ノードに返す return value; minmax(ture, 1) if (flag) { if (child >= value) { value = child; bestposition = i; Levelは1なので親ノードに返す return value;

19 イメージ 4 Select このノードを選択する level 3 自分の手 Max level 2 相手の手 Min level 1 自分の手 Max minmax(ture, 3) if (flag) { if (child >= value) { value = child; bestposition = i; Levelは3なので親ノードに返す if (level == SEARCH_LEVEL) { return bestposition;

20 まとめると : コンピュータは最後に一番高い評価値を選ぶ. しかし相手プレイヤーもまた自分にとって良い手を選びますしたがって相手プレイヤーはコンピュータの評価値の最小を選びます ( コンピュータにとって評価値が低いということは自分にとって有利であるから ) 20

21 α-β pruning (Alpha-Beta 法 ) 3 L1 (maximum in L2) A 1 A 2 A 3 α=3 2 L2 (minimum in L3) α=-999 β=3 β=999 初期値 A 11 A 12 A 13 A 22 A α= 12 8 A 21 A 31 A 32 A 33 β =2 A 121 A 122 A α=12 β=3 α > β α=3 β=2 α >= β L3 (maximum in L4) 探索のスピードを早めるためにこの分岐をカットする A 121 の評価値が 12 と決定したとき A 12 の評価値は 12 以上だと確定する (A 121,A 122,A 123 の最大値が A 12 の評価値になる ) よって A 12 の評価値が A 1 に選ばれることはなくなった ( A 1 の評価値は A 11,A 12,A 13 の最小値が選ばれる ) ので A 122,A 123 の評価値を計算する必要がないのでカットする 21

22 α カット最大の評価値を取ろうとするときの下限 (α) 以下になる場合は残りの部分は探索しない O >=5(α 値 ) A の評価値が 5 と確定後 E の評価値が 4 だとわかるこの時 B の評価値は 4 以下だとわかるよって B 選ばれないので F は見ない自分 A (5) B <=4(β 値 ) α カット相手 C (5) D (7) E (4) F (8) G (3) H (5) I (4) J (7) K (4) L (3) M (3) J (4) G (4) M (3) J (8) G (5)

23 β カット最小の評価値を取ろうとするときの上限 (β) 以上になる場合は残りの部分は探索しない A <=5(β 値 ) O Cの評価値が5と確定した時 Aの評価値は5 以下であることが確定する次にJを見て評価値が7となり Dの評価値は7 以上であることが確定よってDが選択されることはないのでK,Lはカットされる B C (5) D >=7(α 値 ) β カット E (4) F (8) G (3) H (5) I (4) J (7) K (4) L (3) M (3) J (4) G (4) M (3) J (8) G (5)

24 計算回数ミニマックス法 12 回 αβ 法 7 回 R B E F D H C A G J I L K J M G J M G R B E F D H C A G J I L K J M G J M G

25 演習 2 Draw the branches which can be cut 25

26 擬似コード public int alphabeta(boolean flag, int level, int alpha, int beta) { String my; // 現在の手 int value; // 評価値 int child; // 子ノードからくる評価値 // うつ場所 int bestposition = -99; // 仮 flag : AIの手のときtrue プレイヤーの手のときfalse level : 先読みのレベル alpha : α 値 beta : β 値演習 3: complete the codes 1 if (flag) { if (childvalue > value) { 1.1を書く if (level == 0) { return evaluation(flag); if (flag) { // AI ターンでの初期化 value = -999; my = "O"; else { // プレイヤーターンでの初期化 value = 999; my = "X"; for (int i = 0; i < size * size; i++) { if (buttons[i].getlabel().equals("")) { buttons[i].setlabel(my); if (check(flag)) { buttons[i].setlabel(""); if (!flag) return -1000; else return i; child = alphabeta(!flag, level - 1, alpha, beta); 2 else { if (childvalue < value) { 1.2 を書く 2.1 を書く 2.2 を書く

27 まとめゲームは自分にとっては最も有利な手を自分が打ち (max) 次に相手が自分にとって最も不利な手を打ち (min) それらが交互に繰り返されることによって成り立ちます <α-β 法 ( 刈 )> Minimax を改良したもの枝刈りを行うことで Minimax より評価するノードを抑えている <Minimax algorithm と α-β algorithm の違い > Minimax 法ではすべてを探索し最良の手を選択するのに対して α-β 法は minimax 法で採用されないと判断された手についてはそこから先を探索しないことで無駄な探索に費やす時間をカットしているまた α-β 法による結果は minimax 法での結果と同じになる枝刈りを行うことにより探索が minimax 法より早く終わるので α-β 法のほうが効率的である 27

オセロゲームの評価方法について http://uguisu.skr.jp/othello/5-1.

28 オセロゲームの評価方法についてこの図では隅に重みを上げ隅の周りのマスの重みを下げていることが分かりますこの評価値の付け方だと隅を取ると有利になることしか満たしていません例えば左の局面を上記の評価値を用いて計算すると白 :+33 黒 :+13 となりますしたがってこの局面では白が評価値 20 ほど有利だと言えますしかしながらこれは誤りですこの場面では黒が有利と判定されなければなりません石の位置による評価を重視しての方法各マスの評価点は中央の方が点数が高くなるようにまた基本的に負の値に設定する方法ですこうすると自分の石が多いほど合計点が小さくなることは分かります負にすることで何のメリットがあるのでしょうか? 実はこの方法だと相手に囲ませる石を多くとらないといったリバーシの必勝通りの戦法になります例えば左のような重み付けをしたとすると先ほどの局面は白 :-23 黒 :-18 となり黒が優勢となりますヒント : 序盤は隅が非常に重要だが終盤はそれほど重要でないなど石の位置の重みも変化してくるのでこの評価値を序盤中盤終盤などに分けて数パターン作成しておきます 28

29 (Optional) 課題をするにあたってやってほしいこと : (1) TicTacToe_MinMax Java TicTacToe_alphabeta.java プログラムをダウンロードする (2) 実行する (3) ソースコードを読み理解する (4) ゲーム AI" をキーワードにして検索し出てきた記事を読む課題 : 自分の言葉で以下のアルゴリズムを説明しなさい (1) MinMax (2) α-β 29

30 参考サイト : Java In python Othello Game (Min-Max): α-β 30

AI 三目並べ

AI 三目並べ ame Algorithms AI programming 三目並べ 2011 11 17 ゲーム木お互いがどのような手を打ったかによって次にどのような局面になるかを場合分けしていくゲーム展開を木で表すことができる相手の手ゲームを思考することはこのゲーム木を先読みしていく必要があるミニマックス法考え方では局面が最良になる手を選びたい相手は ( 自分にとって ) 局面が最悪となる手を選ぶだろう