タンク・チェンジ 戦車の移動とクリア判定の続きです。今回はギブアップ時に正解手順を示す処理を実装します。
Contents
解を求める方法
ユーザーがギブアップした状態からゲームクリアまでの最短手順を取得するために幅優先探索で全探索をおこないます。そのために現在の状態を数値に変換します。
現在の状態とは青と赤の戦車がそれぞれどこにあるのかとどちらの手番なのかです。同じ色であれば戦車を区別する必要はありません。このようにすることで考える必要がある場合の数を減らすことができます。また最短手順を考えている以上、同じ状態が何度も出現することはありえず、千日手のような状態になっていつまで待っても答えがでてこないということも避けられます。
まず戦車の位置は行と列で表現されていますが、これを (row + 1) + 10 * (col + 1) として2桁の整数で表現することにします。また戦車の番号を青と赤それぞれで昇順（小さい順）でソートして以下のように計算します。
|
1 2 3 4 5 6 7 |
const value = BluePositions[0] + // 青で一番小さい番号 BluePositions[1] * 100 + // 青で次に小さい番号 BluePositions[2] * 10000 + // 青で一番大きい番号 RedPositions[0] * 1000000 + // 赤で一番大きい番号 RedPositions[1] * 100000000 + // 赤で次に小さい番号 RedPositions[2] * 10000000000 + // 赤で一番大きい番号 Turn * 1000000000000; // 手番（青：0、赤：1） |
動的計画法で bitDPがありますが、その劣化版です（bit じゃなく十進数そのまんまだし）。なんかデタラメやっているようですが、一応最短手順は取得できます。また JavaScript で安全に扱える整数は 2 の 53 乗 – 1 であり、9,007,199,254,740,991 です。上のコードだとその範囲内に収まっています。
Handクラスの定義
次の手に関する情報を格納するためのHandクラスを定義します。コンストラクタに渡されるのはどの位置にあった戦車がどの位置に移動するかです。
|
1 2 3 4 5 6 |
class Hand { constructor(from, next){ this.From = from; this.Next = next; } } |
Statusクラスの定義
戦車の位置情報などの状態を保存するためにStatusクラスを定義します。最初にコンストラクタを示します。
|
1 2 3 4 5 6 7 8 9 |
class Status { constructor(){ this.Turn = 0; // 手番；青なら 0、 赤なら 1 this.TurnCount = 0; // 手数 this.BluePositions = []; // それぞれ 3 両の戦車の位置を整数に変換したもの（昇順） this.RedPositions = []; this.PrevStatus = null; // 前の状態（現在からクリア時までの状態遷移がわかるようにする） } } |
TankPositionsToLong関数は両軍の戦車の位置とどちらに手番があるかを整数値で返すためのものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Status { TankPositionsToLong() { const value = this.BluePositions[0] + this.BluePositions[1] * 100 + this.BluePositions[2] * 10000 + this.RedPositions[0] * 1000000 + this.RedPositions[1] * 100000000 + this.RedPositions[2] * 10000000000 + this.Turn * 1000000000000; return value; } } |
開始点の状態をセットする
SetStartPositions関数は最短手順を考えるときの開始点になる状態（降参ボタンをクリックしたとき）をStatusオブジェクトに反映させるためのものです。
|
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 Status { SetStartPositions(turn){ // 現在の手番と手数をコピー this.Turn = turn; this.TurnCount = moveCount; // それぞれの戦車の位置をひとつの整数に変換して保存する this.BluePositions = []; this.RedPositions = []; for(let row = 0; row < matTanks.length; row++){ for(let col = 0; col < matTanks[0].length; col++){ const number = (row + 1) + 10 * (col + 1); // 番号からどちらの戦車かわかる if(matTanks[row][col] != -1 && matTanks[row][col] < 3) this.BluePositions.push(number); if(matTanks[row][col] >= 3) this.RedPositions.push(number); } } // それぞれを小さい順にソートする this.BluePositions.sort((a, b) => a - b); this.RedPositions.sort((a, b) => a - b); } } |
つながっている位置を取得する
GetNextPositions関数は引数で渡された位置から移動できる位置のリストを返します。
位置を表す整数は (row + 1) + 10 * (col + 1) なのでこの値に 11 と 9 をそれぞれ増減すると斜めに移動できる位置がわかります。また増減の結果、10の位が 1 ～ 5 以外であったり、1の位が 1 ～ 7 以外になった場合はマップの範囲外に出てしまったことになります。
|
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 30 31 32 33 |
class Status { GetNextPositions(position){ const list = []; const turn = this.Turn; const vs = [11, -11, 9, -9]; for(let i = 0; i < vs.length; i++){ const value = vs[i]; let temp = position; while (true) { temp += value; const one = temp % 10; const ten = Math.floor(temp / 10); let tankPositions; if(turn == 0) tankPositions = this.BluePositions; else tankPositions = this.RedPositions; if (1 <= one && one <= 7 && 1 <= ten && ten <= 5) { if (tankPositions.filter(_ => _ == temp).length == 0) list.push(temp); else break; } else break; } } return list; } } |
その位置は安全か調べる
IsSafe関数はその位置が敵から撃たれない位置かどうかを判定します。引数の位置から敵にたどりつけるのであれば敵に撃たれる位置です。そうでないなら安全な位置であると判断できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Status { IsSafe(position) { const enemiesPositions = this.Turn == 0 ? this.RedPositions : this.BluePositions; const dangers = []; for(let i = 0; i < enemiesPositions.length; i++){ const nexts = this.GetNextPositions(enemiesPositions[i]); for(let k = 0; k < nexts.length; k++) dangers.push(nexts[k]); } return dangers.filter(_ => _ == position).length == 0; } } |
安全に移動できる位置を求める
GetSafeNextPositions関数は前述のGetNextPositions関数とIsSafe関数を使って移動可能で撃たれない位置のリストを取得するためのものです。
|
1 2 3 4 5 6 |
class Status { GetSafeNextPositions(position) { const nexts = this.GetNextPositions(position); return nexts.filter(x => this.IsSafe(x)); } } |
次の手の候補リストを取得する
GetHands関数は現在の状態から次の手の候補のリストを取得します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Status { GetHands() { const hands = []; let positions; if(this.Turn == 0) positions = this.BluePositions; else positions = this.RedPositions; for(let i = 0; i< positions.length; i++){ const position = positions[i]; const nexts = this.GetSafeNextPositions(position); for(let k = 0; k < nexts.length; k++) { const next = nexts[k]; if (positions.filter(_ => _ == next).length == 0) hands.push(new Hand(position, next)); } } return hands; } } |
着手後の状態を取得する
GetResult関数は着手によってどのような状態に移行するかを取得します。
BluePositions と RedPositions から hand.From と同じものがあるときは取り除き、hand.Next を追加したオブジェクトを複製すれば着手後の状態をもつオブジェクトを生成することができます。それと同時に手番の交代と手数が増えるので Turn と TurnCount の変更も反映するようにしておきます。そして最短手順の一例を示さなければならないので前の状態を保存しておきます。
|
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 Status { GetResult(hand) { const bluePositions = []; for (let i = 0; i < 3; i++){ if(hand.From != this.BluePositions[i]) bluePositions.push(this.BluePositions[i]); else bluePositions.push(hand.Next); } bluePositions.sort((a, b) => a - b); const redPositions = []; for (let i = 0; i < 3; i++){ if(hand.From != this.RedPositions[i]) redPositions.push(this.RedPositions[i]); else redPositions.push(hand.Next); } redPositions.sort((a, b) => a - b); const status = new Status(); status.Turn = this.Turn == 0 ? 1 : 0; // 手番を交代する status.TurnCount = this.TurnCount + 1; // 手数を増やす status.BluePositions = bluePositions; // 新しい戦車の位置をセット status.RedPositions = redPositions; // 新しい戦車の位置をセット status.PrevStatus = this; // 最短手順の一例を示さなければならないので前の状態を保存しておく return status; } } |
クリア判定
IsFinish関数はクリアしたかどうかを調べるためのものです。
|
1 2 3 4 5 6 7 8 9 |
class Status { IsFinish(){ if ( this.BluePositions[0] == 17 && this.BluePositions[1] == 37 && this.BluePositions[2] == 57 && this.RedPositions[0] == 11 && this.RedPositions[1] == 31 && this.RedPositions[2] == 51 ) return true; else return false; } } |
幅優先探索で最短手順を取得する
Statusクラスを用いて幅優先探索で最短手順を取得する処理を示します。
まず最初の Status オブジェクトを生成して、SetStartPositionsメンバ関数を呼び出して現在の状態を格納します。そしてこれをキューに格納します。
あとはループ処理でキューから格納されたオブジェクトを取り出して GetHands メンバ関数を呼び出して次の手の候補を取得します。手の候補からそれぞれ GetResult メンバ関数を呼び出して次の状態を表すStatus オブジェクトを取得し、それをまたキューに格納するという処理を続けます。
ただこのときに同じ状態を複数回探索してしまわないように連想配列にオブジェクトを格納します。同一の状態が出現したときは手数が少ない場合以外は無視します。これでいつまで経っても処理が終わらない状態を回避できます。連想配列で使うキーはTankPositionsToLongメンバ関数が返した整数値です。
GetResultメンバ関数が返したオブジェクトの IsFinishメンバ関数が true を返すかキューの中身が空になったら処理は終了です。IsFinishメンバ関数が true を返すことなくキューの中身が空になった場合はすでに手詰まりになっていて最短手数は存在しない場合です。
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
function bfs(){ const turn = phase < 2 ? 0:1; const KeyValuePairs ={}; const startStatus = new Status(); startStatus.SetStartPositions(turn); const queue = []; // 配列をキューのように使う（最後尾に追加して先頭から取り出す） queue.push(startStatus); KeyValuePairs[startStatus.TankPositionsToLong()] = startStatus; let find = false; let lastStatus = null; while (queue.length > 0 && !find){ const status = queue[0]; queue.shift(); const hands = status.GetHands(); for(let i = 0; i < hands.length; i++){ const hand = hands[i]; const newStatus = status.GetResult(hand); if (newStatus.IsFinish()) { find = true; lastStatus = newStatus; break; } const key = newStatus.TankPositionsToLong(); if(!(key in KeyValuePairs)){ KeyValuePairs[key] = newStatus; queue.push(newStatus); } else { if (KeyValuePairs[key].TurnCount > newStatus.TurnCount){ KeyValuePairs[key] = newStatus; queue.push(newStatus); } } } } return lastStatus; } |
正解手順にしたがって戦車を動かす
幅優先探索の結果を取得して正解手順にしたがって戦車を動かす処理を示します。
bfs 関数の戻り値が null の場合は解は存在しません。この場合はなにもしないで false を返します。bfs 関数の戻り値が null ではない場合はこの状態は戦車を移動させた最後の状態なので、ここから逆に遡って前の状態を取得していきます。
lastStatus.PrevStatus が null であればこれが降参ボタンをクリックしたときの状態です。これまで取得したオブジェクトをリストに追加するときに最後尾ではなく先頭に追加するようにすれば反転させなくてもこれが正解手順となります。
正解手順にそって戦車を動かすには手順の前の状態との差分（なくなったもの、追加されたものはないか）を調べます。それがそのターンで動かす戦車です。どの戦車を動かすかわかったらあとはそのとおりに移動させるだけです。
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
async function Solve() { let lastStatus = bfs(); if(lastStatus == null) return false; // 最後の状態から最初の状態へ遡っていく const rets = []; rets.unshift(lastStatus); while (true) { const prevStatus = lastStatus.PrevStatus; if (prevStatus == null) break; lastStatus = prevStatus; rets.unshift(prevStatus); } // 正解手順にそって戦車を動かす for(let i = 0; i < rets.length; i++){ const status = rets[i]; // 前の状態との差分を調べる if(status.PrevStatus != null){ const prevBlue = status.PrevStatus.BluePositions; const prevRed = status.PrevStatus.RedPositions; const newBlue = status.BluePositions.filter(_ => _ != prevBlue[0] && _ != prevBlue[1] && _ != prevBlue[2]); const oldBlue = prevBlue.filter(_ => _ != status.BluePositions[0] && _ != status.BluePositions[1] && _ != status.BluePositions[2]); const newRed = status.RedPositions.filter(_ => _ != prevRed[0] && _ != prevRed[1] && _ != prevRed[2]); const oldRed = prevRed.filter(_ => _ != status.RedPositions[0] && _ != status.RedPositions[1] && _ != status.RedPositions[2]); let newPosition = 0; let oldPosition; if(newBlue.length > 0){ oldPosition = oldBlue[0]; newPosition = newBlue[0]; } else{ oldPosition = oldRed[0]; newPosition = newRed[0]; } // oldPosition にあった戦車が newPosition に移動したことがわかった const oldCol = Math.floor(oldPosition / 10) -1; const oldRow = oldPosition % 10 - 1; const newCol = Math.floor(newPosition / 10) -1; const newRow = newPosition % 10 - 1; // これは oldRow 行 oldCol 列にあった戦車が newRow 行 newCol 列に移動したことになる // あとはそのとおりに移動させるだけ await sleep(1000); await moveSmooth(new Position(oldRow, oldCol), new Position(newRow, newCol)); } } return true; } |
