Q&A
この手の自由設定できるゲームは例外が多すぎてアルゴリズムで判断するのは厳しいのでは？
ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じ るかどうか判定するプログラムを作成したいです
以下の画像のようなすごろくを作成したとします
・「ふりだし」と「あがり」以外のマス目のイベント
・サイコロの目数
を自分で設定（入力）します。
以下の画像ののようなイベントマスを設定し、サイコロの目数を最大2に設定したとします。
その時、最初に1を出せばあがりに辿り着くことができますが、2を出してしまった場合、次にどのような数を出しても絶対にあがりには辿り着けないような設定になってしまっています。
以下のコードでは、ゴールできる設定の場合では「OK」と出力されるのですが、ゴールできない場合（「NG」）の判定ができません。
一体どのようにすればゴールできる時とできない時の判定ができるのでしょうか。ソートアルゴリズムなどを用いるのでしょうか？拙い説明ですがご教授いただけると幸いです。
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> </head> <body> <script src="main.js"></script> </body> </html>
javascript
1let x = prompt("ルーレットが出す数の最大値 はいくつですか？") * 1; 2let n = prompt("「ふりだし」と「あがり」以外のマス はいくつですか？") * 1; 3let a = new Array(); 4let s = 0; 5let g = n + 1; //ゴールのマス 6let m = 0; //現在のマス 7let flag = false; 8 9//マスの指示内容を入力 10for (let i = 0; i < n; i++) { 11 a[s] = prompt(i + 1 + "番目のマスの指示内容を入力"); 12 console.log(i + 1 + "マス目の指示は" + a[s]); 13 s++; 14} 15//シミュレーション 16while (flag==false) { 17 let ram = Math.ceil(Math.random() * x); //サイコロを振る 18 19 m = m + ram; 20 m = m + a[m]; 21 22 if (g <= m) { 23 m = g; 24 flag = true; 25 } else if (m < 0) { 26 m = 0; 27 } 28 29} 30 31//判定 32if (flag) { 33 document.write("OK");//ゴールできる場合 34} else { 35 document.write("NG");//ゴールできない場合 36} 37
アクションは連鎖しない(1 を出して 2 つ進んだところからさらに 1 つ戻されることはない)と捉えました。
この例の場合は、1 を出せば解決できるから、OK なのでしょうか、それとも 2 を出すと、その後に 1 を出しても 2 を出してもゴールできなくなるから NG なのでしょうか、どちらでしょうか。
どの程度の自由なのでしょうか。例えば、2 つ戻るのところに 10 戻る、あるいは 10 進むと書くこともできるのでしょうか、その場でスクワットする、と書くこともできるのでしょうか。ふりだしに戻るや return to start 、他のプレイヤーと位置を交替するみたいなものも良いのでしょうか。(これは解決したい課題が何かを切り分けるための質問です)
「ゴールできない」、という概念を、正確に言語化することから始めないといけません。
どういう条件を満たせば、「ゴールできない」なのか、考えてみてください。
なお、このような判定では、乱数は絶対に使いません。
説明に不足がありました。
一通りでもゴールできない条件がある場合もNGと出力します。
ルーレットを回して出た数だけ進み、止まったマスに指示が書き込んであれば、その指示に従って 移動します。ただし、指示に従って進んだ先のマスの指示には従いません。
また、「あがり」に達するより大きな数が出たときや、指示に 従うと「あがり」より先に進んでしまうときは「あがり」に移動します。指示に従って戻るときに「ふりだし」 より前に戻ってしまうときは「ふりだし」に戻ることにします。
説明不足で申し訳ございません。
グラフ理論(状態遷移)で解けそう。各マスを状態/サイコロの目を遷移 に対応付ければ、ある状態から抜け出せないマスがあったら「不正なすごろく」と判定できる。
ご指摘ありがとうございます。
グラフ理論についての理解は深まったのですが、そのアルゴリズムをどのようにプログラミンングに組み込めば良いのかが想像できません。具体的に「ある状態から抜け出せない」という判定をどのようにすればいいのでしょうか。
お時間がございましたらご教授お願いします。
マスA から マスB に移動できることを A→B と表すと、出口がないP(または P→P)が存在すれば マスPから脱出できない。
回答2件
0
ベストアンサー
あるマスから到達可能なマスに「あがり」がなければ
「ゴールできない」マスということになります。
そのようなマスに「ふりだし」から到達できてしまうようであれば、
「ゴールできない」すごろくであると判断できます。
「あるマスから到達可能なマス」については、すごろくのマスを節点、
サイコロの目によるマスの移動を辺とした有向グラフの推移閉包として求められます。
実際に必要な情報は「ふりだしから到達可能なマス」と「あがりに到達可能なマス」だけですが、
コードを簡単にするため、あえて「あるマスから到達可能なマス」をすべて求めています
JavaScript
1let x = +prompt("ルーレットが出す数の最大値 はいくつですか？"); 2let n = +prompt("「ふりだし」と「あがり」以外のマス はいくつですか？"); 3let a = []; 4let g = n + 1; //ゴールのマス 5 6//マスの指示内容を入力 7for (let i = 1; i <= n; i++) 8 a[i] = +prompt(i + "番目のマスの指示内容を入力"); 9// 各マスから1回以内で到達可能なマスで初期化 10let t = []; 11for (let i = 0; i <= g; i++) { 12 t[i] = new Set([i]); 13 for (let j = 1; j <= x; j++) 14 t[i].add(Math.max(0, Math.min(g, i + j + (a[i + j] || 0)))); 15} 16// 各マスから到達可能なすべてのマスを求める(ワーシャルのアルゴリズムによる有向グラフの推移閉包) 17for (let k = 0; k <= g; k++) 18 for (let i = 0; i <= g; i++) 19 if (i != k && t[i].has(k)) 20 for (let j = 0; j <= g; j++) 21 if (t[k].has(j)) 22 t[i].add(j) 23// ふりだしから到達可能なすべてのマスで、あがりに到達できればOK 24if ([...t[0]].every(e => t[e].has(g))) 25 document.write("OK");//ゴールできる場合 26else 27 document.write("NG");//ゴールできない場合
投稿2020/11/28 22:27
総合スコア2431
0
ふりだしからあがりに到達できない可能性があるかどうかということは、ふりだしから到達可能であがりに到達不能なマスが存在するかどうかと同じことです。
それぞれふりだしとあがりからBFSやDFSをすることで判別可能です。
指示のあるマスには注意が必要です。
指示のあるマスに到達した場合を一律に到達したとみなしていいのかどうか。
あがりから調べたときにあるマスに移動させる指示が書かれたマスをどうやって見つけるか。など
どれもコードにするのはそれほど難しいことじゃないので、考えながら書いていけばできるでしょう
投稿2020/11/28 03:02
総合スコア2047
あなたの回答
tips
プレビュー
