ナイト配置ゲームをつくる（1）の続きです。前回作成したものは着手可能点をランダムに選択して着手するだけだったので全然強くありませんでした。今回はアルゴリズムを改善して強くします。
必勝形かどうかの判定
現在の盤面が必勝形かどうかを判定する関数を定義します。合法手がひとつも存在しないのであれば負けが確定します。そのような形を相手に押し付けることができる合法手が存在するのであれば必勝形であると考えることができます。
Win関数を再帰呼び出ししています。同じ引数で何度も呼び出すことになるので、一度結果を取得したらこれをMapに保存して処理にかかる時間を短縮しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Game { GetKey(state){ return `${state.forbidden.lo},${state.forbidden.hi}`; } Win(state){ const key = this.GetKey(state); if(this.WinMemo.has(key)) return this.WinMemo.get(key); const moves = this.GetLegalMoves(state); if(moves.length == 0){ this.WinMemo.set(key, false); return false; } let res = false; for(let move of moves){ if(!this.Win(this.MakeMove(state, move))){ res = true; break; } } this.WinMemo.set(key, res); return res; } } |
盤面が狭いとこれで動いてくれます。しかし8×8の盤だと合法手がたくさん存在するため処理に時間がかかります。以下のコードでは待てど暮らせど着手してくれません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Game { AiMove(){ const moves = this.GetLegalMoves(this.State); let best = null; for(let move of moves){ const n = this.MakeMove(this.State, move); if(!this.Win(n)){ // この盤面でプレイヤーに手番を渡したらプレイヤーが負けが確定する // すなわちコンピュータ側にとってmoveが最善手 best = move; break; } } if(best == null){ // コンピュータ側の必敗形なので次の手はランダムに選ぶ best = moves[Math.floor(Math.random() * moves.length)]; } this.State = this.MakeMove(this.State, best); } } |
評価関数の実装
上記の方法で最善手を探すのは合法手が少なくなって短時間で処理が完了できるときに限定して、開始直後のように合法手がたくさんあるときは別に評価関数を実装することで最善手に近いものを探すことにします。
評価の方法ですが（自分の合法手数 – 相手の合法手数）で評価することにします。第二引数のdepthはあと何手先まで調べるかです（とりあえず4手先まで読む）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Game { Evaluate(state, depth){ const moves = this.GetLegalMoves(state); if(moves.length == 0) // 合法手がない＝負け確定 return -1000; if(moves.length <= 10) // 合法手が少ないので全パターン調べる return this.Win(state) ? 1000 : -1000; if(depth == 0) return moves.length; let best = -Infinity; for(let move of moves){ let score = this.Evaluate(this.MakeMove(state, move), depth - 1); score *= -1; // 相手にとっての評価値が返されるので符号を反転させれば自分の評価値となる if(best < score) best = score; } return best; } } |
AiMove関数を以下のように書き換えます。ただこれでもまだ時間がかかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Game { AiMove(){ const moves = this.GetLegalMoves(this.State); let best = null; let best_score = -Infinity; for(let move of moves){ let score = this.Evaluate(this.MakeMove(this.State, move), 4); score *= -1; if(best_score < score){ best_score = score; best = move; } } console.log('評価値: ' + best_score); this.State = this.MakeMove(this.State, best); } } |
αβ法【アルファベータ法】
上記の方法は、自分の手番における自分の利得の最大化と相手の手番における自分の利得の最小化を考えたとき、自分の利得が最も大きくなる選択肢がどれになるかを探索する方法でした。このような方法をMinMax法といいます。
MinMax法では、自分の手番か相手の手番かによって、最大化をするか最小化をするかが異なります。これを簡単にするために考案されたのがNegaMax法です。「自分の得点 = 相手の損失」なので相手の手番であれば符号を反転させて考えればどちらの手番でも最大化するようにすればよいことになります。
MinMax法もNegaMax法もすべての選択肢を最後まで探索しますが、これでは時間がかかります。そこで探索の途中で明らかに可能性のない枝を発見したときは「枝刈り」をして処理にかかる時間を短縮します。
α値を「この局面で自分がすでに確保できている最低スコア」、β値を「相手がこれ以上許さない上限スコア」とします。すると探索中の評価値はα値とベータ値の間の値となります。それ以外の場合はそこからさらに調べてもよい値はでてきません。このような枝刈りをいれるとかなり処理速度は速くなります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Game { Evaluate(state, depth, alpha, beta){ const moves = this.GetLegalMoves(state); if(moves.length == 0) return -1000; if(moves.length <= 10) return this.Win(state) ? 1000 : -1000; if(depth == 0) return moves.length; let best_score = -Infinity; for(let move of moves){ let score = this.Evaluate(this.MakeMove(state, move), depth - 1, -beta, -alpha); score *= -1; if(best_score < score) best_score = score; if(alpha < best_score) alpha = best_score; if(alpha >= beta) break; } return best_score; } } |
現在の盤面を引数にして最善手を取得する関数を定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Game { GetBestMove(cur_state){ const moves = this.GetLegalMoves(cur_state); let best_move = null; let best_score = -Infinity; for(let move of moves){ let score = this.Evaluate(this.MakeMove(cur_state, move), 4, -Infinity, Infinity); score *= -1; if(best_score < score){ best_score = score; best_move = move; } } return best_move; } } |
|
1 2 3 4 5 6 7 |
class Game { AiMove(){ const best = this.GetBestMove(this.State); if(best !== null) this.State = this.MakeMove(this.State, best); } } |
これでよほど短気でない人なら普通に動作するようになりました。ただやはり最初は着手までに数秒かかります。
そこで時間がかかる処理になりますが（一度にやろうとせずにわけたほうがよさそう）、以下のような関数を実行してプレイヤーのすべての初手に対する応手と、それに対するプレイヤーの応手に対する応手をすべて取得してしまいます。そしてこの結果をコードに埋め込んでしまえばコンピュータ側の着手はすぐに行われます。またそれ以降の着手は合法手が少なくなっているので、前処理をしなくてもほとんど待たされることなくすぐに行われます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Game { GetBestMoves(){ const moves1 = this.GetLegalMoves(this.State); for(let move1 of moves1){ const new_state1 = this.MakeMove(this.State, move1); const best_move1 = this.GetBestMove(new_state1); const key1 = this.GetKey(new_state1); console.log(`${key1}, ${best_move1}`); const state2 = this.MakeMove(new_state1, best_move1); const moves2 = this.GetLegalMoves(state2); for(let move2 of moves2){ const new_state2 = this.MakeMove(state2, move2); const best_move2 = this.GetBestMove(new_state2); const key2 = this.GetKey(new_state2); console.log(`${key2}, ${best_move2}`); } } } } |
出力されたものをコード内に埋め込みます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// コンピュータ側に手番があるときの盤面と最適手（約4500件） const best_memo = new Map(); best_memo.set('132097,0', 19); best_memo.set('571420183,20', 20); best_memo.set('572401181,20', 43); best_memo.set('576368181,20', 18); best_memo.set('581580373,20', 18); best_memo.set('575284885,20', 18); class Game { AiMove(){ // mapのなかにあるならそこから、ないならGetBestMove関数を呼び出して着手する let best = null; const key = this.GetKey(this.State); if(best_memo.has(key)) best = best_memo.get(key); else best = this.GetBestMove(this.State); if(best !== null) this.State = this.MakeMove(this.State, best); } } |
