ame Algorithms AI programming 三目並べ 2011 11 17
ゲーム木 お互いがどのような手を打ったかによって次にどのような局面になるかを場合分けしていくゲーム展開を木で表すことができる 相手の手 ゲームを思考することは このゲーム木を先読みしていく必要がある
ミニマックス法 考え方 では局面が最良になる手を選びたい 相手は ( 自分にとって ) 局面が最悪となる手を選ぶだろう 相手が自分にとってまずい手を打ってきても そのまずさ (Min) があまり悪くない手 (Max) を打とう
ミニマックス法 もう少し詳しく 今 自分が打てる複数の候補手を考えた時 それぞれの手に関して 相手の対抗手 ( これもまた複数 ) を探索する この時 対抗手の評価値を全て計算する その中で最小の評価値 ( 相手にとっては最高の評価値 )hを求める 自分の候補手の中で 最も高い評価値である手を最適なものとする では評価値が max, 相手の手では評価値が min となる手を選択
三目並べの例 評価値 h = h0 h1 h0: 自分の石だけが置かれている縦 横 斜めの列数 h1: 相手の石だけが置かれている縦 横 斜めの列数 -99 比較 -99 比較 0 Select 現在の状態 Max 白勝利評価最悪 -99 m i n h=-1 m i n m i n 比較 白勝利評価最悪 比較 比較 -99 h=-1 h=0 h=1 相手の手 Min
どのように実装するか 1. 自分が打てる複数の候補手を考えた時 それぞれの手に関して 相手の対抗手を探索する 1. これを深読みレベルまで繰り返す 2. 木の末端まで来た時 評価値を計算する 2. 子ノードから返された評価値比較する 1. AI( 自分 ) のターンなら最大を選択する 2. プレイヤー ( 相手 ) のターンなら最小を選択する 3. 評価値を親ノードへと返す 1. 自分自身が子ノードの場合 選ばれた評価値を親ノードへ返す 2. 根の場合 最適な場所を返す
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(""); 2.1 2.2 3.2 3.1 if (level == SEARCH_LEVEL) { // 根 if (bestposition == -99) { // CPの負けが確実 OptionPane.showMessageDialog(null, " まいりました "); System.exit(0); return bestposition; else { // 子ノード return value; // 評価値を返す
イメージ 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);
イメージ 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 評価値 4 2 5 3 6 1 2 1 minmax(false, 0) レベルが 0 なので親ノード if (level == 0) { return evaluation(flag); // 評価値を計算する evaluation(false) 評価値を計算して返す
イメージ 3 level 3 Max level 2 相手の手 Min level 1 Max 4 5 6 2 4 2 5 3 6 1 2 1 4 2 5 3 6 1 2 1 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;
イメージ 4 Select このノードを選択する level 3 Max level 2 相手の手 Min level 1 Max 4 4 5 6 2 4 2 5 3 6 1 2 1 4 2 5 3 6 1 2 1 2 minmax(ture, 3) if (flag) { if (child >= value) { value = child; bestposition = i; Levelは3なので親ノードに返す if (level == SEARCH_LEVEL) { return bestposition;
αβ 法 ミニマックス法は木を全て探索 + 評価値の計算を行うので計算量が多くなる 木を全てではなく 見なくて良い枝をカットしていく方法が αβ 法 R A B C D (7) E F (8) H I (7) K L M M (8)
α カット 最大の評価値を取ろうとするときの下限 (α) 以下になる場合は 残りの部分は探索しない O >=5(α 値 ) A の評価値が 5 と確定後 E の評価値が 4 だとわかる この時 B の評価値は 4 以下だとわかる よって B 選ばれないので F は見ない 自分 A B <=4(β 値 ) α カット 相手 C D (7) E F (8) H I (7) K L M M (8)
β カット 最小の評価値を取ろうとするときの上限 (β) 以上になる場合は 残りの部分は探索しない A <=5(β 値 ) O Cの評価値が5と確定した時 Aの評価値は5 以下であることが確定する 次にを見て 評価値が7となり Dの評価値は7 以上であることが確定 よってDが選択されることはないのでK,Lはカットされる B C D >=7(α 値 ) β カット E F (8) H I (7) K L M M (8)
計算回数 ミニマックス法 12 回 αβ 法 7 回 R B E F D H C A I L K M M R B E F D H C A I L K M M
どのように実装するか (αβ カット ) 1. 自分 (CP) の手であれば 子ノードの中で最大の評価値を選ぶ 1. この時 α 値を更新する 2. この見ているノードの評価値が β 値より大きかったら for ループを抜ける 2. プレイヤーなら子ノードの中で最小の評価値を選ぶ 1. この時 β 値を更新する 2. 見ているノードの評価値が α 値よりも小さかったら for ループを抜ける
擬似コード flag : AI の手のとき true プレイヤーの手のとき false level : 先読みのレベル alpha : α 値 beta : β 値 public int alphabeta(boolean flag, int level, int alpha, int beta) { 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 = alphabeta(!flag, level - 1, alpha, beta); 1 2 if (flag) { if (childvalue > value) { 1.1を書く else { if (childvalue < value) { 1.2 を書く 2.1 を書く 2.2 を書く
課題 TicTacToe_MinMax.java に書かれているコメントを参考にして以下のことに取り組みましょう 1. 4 4 マスでも動くプログラム TicTacToe4.java を作成する 2. 資料を参考に αβ 法のメソッドを実装し TicTacToe_AlphaBeta.java を作成する 1. 4 4 マスで動くようにしてください