AI 三目並べ

Size: px

Start display at page:

Download "AI 三目並べ"

いおりこのえ
5 years ago
Views:

1 ame Algorithms AI programming 三目並べ

2 ゲーム木お互いがどのような手を打ったかによって次にどのような局面になるかを場合分けしていくゲーム展開を木で表すことができる相手の手ゲームを思考することはこのゲーム木を先読みしていく必要がある

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

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

5 三目並べの例評価値 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

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

7 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の負けが確実 OptionPane.showMessageDialog(null, " まいりました "); System.exit(0); return bestposition; else { // 子ノード return value; // 評価値を返す

8 イメージ 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);

9 イメージ 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) 評価値を計算して返す

10 イメージ 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;

11 イメージ 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;

12 αβ 法ミニマックス法は木を全て探索 + 評価値の計算を行うので計算量が多くなる木を全てではなく見なくて良い枝をカットしていく方法が αβ 法 R A B C D (7) E F (8) H I (7) K L M M (8)

13 α カット最大の評価値を取ろうとするときの下限 (α) 以下になる場合は残りの部分は探索しない 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)

14 β カット最小の評価値を取ろうとするときの上限 (β) 以上になる場合は残りの部分は探索しない 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)

15 計算回数ミニマックス法 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

16 どのように実装するか (αβ カット ) 1. 自分 (CP) の手であれば子ノードの中で最大の評価値を選ぶ 1. この時 α 値を更新する 2. この見ているノードの評価値が β 値より大きかったら for ループを抜ける 2. プレイヤーなら子ノードの中で最小の評価値を選ぶ 1. この時 β 値を更新する 2. 見ているノードの評価値が α 値よりも小さかったら for ループを抜ける

17 擬似コード 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 を書く

18 課題 TicTacToe_MinMax.java に書かれているコメントを参考にして以下のことに取り組みましょうマスでも動くプログラム TicTacToe4.java を作成する 2. 資料を参考に αβ 法のメソッドを実装し TicTacToe_AlphaBeta.java を作成するマスで動くようにしてください

PowerPoint Presentation

PowerPoint Presentation ゲーム木の探索についてミニマックス法のアルゴリズムアルファベータ法のアルゴリズ三目並べゲームの例 1 ゲーム TicTacToe Othello Chess Let us find game and play! 三目並べ http://perfecttictactoe.herokuapp.com/ オセロ http://atohi.com/osg/default.aspx 将棋 2 ゲーム木の探索問題