以下のようなひとふで書きの問題を作っております。
http://www.fastgames.com/kerixep.html
難しい問題を作りたいのですが、手入力で作ってもなかなかそれらしいものができなくて・・・。
どういった問題が難しいか、口頭で説明できないため、プログラムもかけずにいます。
評価関数なるものを作ってみたいのですが、どういう条件だと難しくなりそうなどわかる方おりますでしょうか。
プログラム自体はC++で制作しているのですが、そもそも難しい問題の定義がわからなくて苦戦しております。
またこちらのゲームのジャンルがひとふで書きでなかったらすいません!
(別名があったらご教授いただきたいです)
問題の仕様は以下となっております。
ex)3×3
0→通れないマス
1→スタート地点
2以上→移動できるマス(同じ数字はきません。連番で違う数字が隣り合わせて配置してあります。)
{
{0,1,0},
{3,2,0},
{4,5,6}
}
わかりにくい質問で申し訳ないです。
パズルゲーム ひとふで書きの問題難易度について
Re: パズルゲーム ひとふで書きの問題難易度について
逆に問題が与えられてプログラムで解くと考えますと、例えば、与えられた例ですと
1の次は、(上、左、右に行けないので)2しか選択肢は無く、
2の次は、3か5
3の次は、(2は通過済なので)4しか選択肢なし。同様に次は5、その次は6しか選択肢なし(正解)
5の次は、6か4
6の次は、行ける所が無く行き詰まり(不正解)
4の次は、3しか選択肢なし、3の次に行ける所が無く行き詰まり(不正解)
ということで、
1 2 3 4 5 6
1 2 5 6
1 2 5 4 3
の3通りを走査する事になるかと思いますが、この走査パターンが多いほど難しい気がします。
ですので評価関数としては、再帰的に実際に解いて、何通りの枝があるかをカウントするという
手法が考えられるのではないかと思います。
1の次は、(上、左、右に行けないので)2しか選択肢は無く、
2の次は、3か5
3の次は、(2は通過済なので)4しか選択肢なし。同様に次は5、その次は6しか選択肢なし(正解)
5の次は、6か4
6の次は、行ける所が無く行き詰まり(不正解)
4の次は、3しか選択肢なし、3の次に行ける所が無く行き詰まり(不正解)
ということで、
1 2 3 4 5 6
1 2 5 6
1 2 5 4 3
の3通りを走査する事になるかと思いますが、この走査パターンが多いほど難しい気がします。
ですので評価関数としては、再帰的に実際に解いて、何通りの枝があるかをカウントするという
手法が考えられるのではないかと思います。
Re: パズルゲーム ひとふで書きの問題難易度について
>再帰的に実際に解いて、何通りの枝があるかをカウントする
意図するところは同じ雰囲気ですが,もっと簡易的に,分岐が発生するマスの数を数えるとか.
分岐が発生するマス=「通れるマスであって,それに隣接する通れるマスの個数が3個以上である」マス…かな.
(評価の際はスタート地点を「通れないマス」扱いするべきかな)
あとは,解の個数が少ないほど難しいと思います.
どういう手順でもいけちゃう問題は簡単.
意図するところは同じ雰囲気ですが,もっと簡易的に,分岐が発生するマスの数を数えるとか.
分岐が発生するマス=「通れるマスであって,それに隣接する通れるマスの個数が3個以上である」マス…かな.
(評価の際はスタート地点を「通れないマス」扱いするべきかな)
あとは,解の個数が少ないほど難しいと思います.
どういう手順でもいけちゃう問題は簡単.
Re: パズルゲーム ひとふで書きの問題難易度について
お二方ともご回答ありがとうございました。
非常にわかりやすく助かります。
現在、同じ方向に2回移動すると簡単になりそうだったので、
そうなりそうな場合は再度移動する方向を抽選するみたいな
頭の悪いアルゴリズムで生成しております。
これを解消するためにも評価関数を作りたいので、
今回のアドバイスには大変助かっております。
頂いたアドバイスをもとにロジックを考えてみます。
再帰処理を書くのが苦手なので、作れなかったら申し訳ないです。
以下、マップ生成時の処理になります。
(6×6のステージで26~30手以内に解ける問題を生成。)
※エラー処理がなかったり、publicにしておりすみません・・・。
非常にわかりやすく助かります。
現在、同じ方向に2回移動すると簡単になりそうだったので、
そうなりそうな場合は再度移動する方向を抽選するみたいな
頭の悪いアルゴリズムで生成しております。
これを解消するためにも評価関数を作りたいので、
今回のアドバイスには大変助かっております。
頂いたアドバイスをもとにロジックを考えてみます。
再帰処理を書くのが苦手なので、作れなかったら申し訳ないです。
以下、マップ生成時の処理になります。
(6×6のステージで26~30手以内に解ける問題を生成。)
※エラー処理がなかったり、publicにしておりすみません・・・。
#include <vector>
#define EDIT_STAGE 1 // 作成ステージ数
#define TBL_WIDTH 10 // 最大サイズ(横)
#define TBL_HEIGHT 10 // 最大サイズ(縦)
class EDIT{
public:
typedef struct{
int Min, Max;
}RANGE;
enum { MOVE_NONE, MOVE_UP, MOVE_DOWN, MOVE_LEFT, MOVE_RIGHT, MOVE_MAX };
int Width, Height, Size;
RANGE BoardCount; // 移動可能マスの範囲
int Count; // 移動可能マス値保持用
int StartX, StartY; // 初期位置保存用
int BeforMove; // 前回移動した方向
std::vector< std::vector<int> > tblVec;
// 引数なしの初期化:2回目以降用
void Init(){
this->Init( this->Width, this->Height, this->BoardCount );
int r = rand() % this->Size;
this->StartX = r % this->Width;
this->StartY = r / this->Height;
this->tblVec[this->StartY][this->StartX] = this->Count;
this->Count++;
this->BeforMove = MOVE_NONE;
}
// 引数ありの初期化
void Init( int width, int height, RANGE boardCount){
this->Width = width;
this->Height = height;
this->Size = this->Width * this->Height;
this->BoardCount = boardCount;
this->Count = 1;
this->BeforMove = MOVE_NONE;
// 配列の初期化
this->tblVec.resize(0);
this->tblVec.resize(this->Height);
for( int y=0; y<this->Height; y++ ){
this->tblVec[y].resize(this->Width);
}
// 初期化
for( int y=0; y<this->tblVec.size(); y++ ){
for( int x=0; x<this->tblVec[0].size(); x++ ){
this->tblVec[y][x] = 0;
}
}
}
// 指定された位置に数字を配置
void SetPram( int nowX, int nowY ){
std::vector<int> tblMove;
tblMove.resize(0);
if( nowX-1 >= 0 ){
if( this->tblVec[nowY][nowX-1] == 0 ) tblMove.push_back(MOVE_LEFT);
}
if( nowX+1 < this->tblVec[0].size() ){
if( this->tblVec[nowY][nowX+1] == 0 ) tblMove.push_back(MOVE_RIGHT);
}
if( nowY-1 >= 0 ){
if( this->tblVec[nowY-1][nowX] == 0 ) tblMove.push_back(MOVE_UP);
}
if( nowY+1 < this->tblVec.size() ){
if( this->tblVec[nowY+1][nowX] == 0 ) tblMove.push_back(MOVE_DOWN);
}
// チェック
if( tblMove.size() > 0 ){
int r = rand() % tblMove.size();
int xx = nowX;
int yy = nowY;
// 前の方向と違えば
if( this->BeforMove != tblMove[r] ){
this->BeforMove = tblMove[r];
if( tblMove[r] == MOVE_LEFT ) xx--;
if( tblMove[r] == MOVE_RIGHT ) xx++;
if( tblMove[r] == MOVE_UP ) yy--;
if( tblMove[r] == MOVE_DOWN ) yy++;
}else{
// 難易度調整用
// もう一回だけ再抽選
r = rand() % tblMove.size();
xx = nowX;
yy = nowY;
this->BeforMove = tblMove[r];
if( tblMove[r] == MOVE_LEFT ) xx--;
if( tblMove[r] == MOVE_RIGHT ) xx++;
if( tblMove[r] == MOVE_UP ) yy--;
if( tblMove[r] == MOVE_DOWN ) yy++;
}
if( this->Count <= this->BoardCount.Max ){
this->tblVec[yy][xx] = this->Count;
this->Count++;
this->SetPram( xx, yy );
}else{
this->Log();
}
}else{
// 最小数よりでかかったら
if( this->Count > this->BoardCount.Min ){
this->Log();
}else{
// 指定された範囲より小さかったら、再度1から作り直し
this->Init();
this->SetPram( this->StartX, this->StartY );
}
}
}
// ログ
void Log(){
int tblLog[TBL_HEIGHT][TBL_WIDTH];
for( int y=0; y<TBL_HEIGHT; y++ ){
for( int x=0; x<TBL_WIDTH; x++ ){
tblLog[y][x] = -1;
}
}
for( int y=0; y<this->tblVec.size(); y++ ){
for( int x=0; x<this->tblVec[0].size(); x++ ){
tblLog[y][x] = this->tblVec[y][x];
}
}
for( int y=0; y<TBL_HEIGHT; y++ ){
for( int x=0; x<TBL_WIDTH; x++ ){
printf( "%d", tblLog[y][x] );
if( x!=TBL_WIDTH-1 ) printf( "\t" );
}
printf( "\n" );
}
}
};
static EDIT Edit;
static void Init(){
//(RANGE){30, 35}
EDIT::RANGE range;
range.Min = 26;
range.Max = 30;
if( range.Max <= range.Min ){
int temp = range.Min;
range.Min = range.Max;
range.Max = temp;
}
Edit.Init( 6, 6, range );
// Sizeが0以上なら
// Edit.Init( Edit.Width, Edit.Height, Edit.BoardCount );
for(int i=0; i<EDIT_STAGE; i++){
if( Edit.Size > 0 ){
Edit.Init();
Edit.SetPram( Edit.StartX, Edit.StartY );
}
}
}
Re: パズルゲーム ひとふで書きの問題難易度について
下記、書き殴りですが解のパターン数と行き詰まりのパターン数をカウントするメソッドです。
難易度の指標として(解のパターン数+行き詰まりのパターン数)/解のパターン数、あたりでどうだろうと考えましたが、例えば、100×100ながら全てが通れるマスで一番左上がスタートであるような、人間から見れば明らかに簡単なパターンでも、分岐の数はとても多くなるので難易度は高いと判断されてしまいます。
また、マップが大きくなるほど重い処理になるので、走査をある程度で打ち切って目安とするだとか、usaoさんの仰るような簡便でコストの低い方法を探るだとか、別の指標を取ってミックスするだとか工夫も必要になりそうです。(まあ、この辺りをあれこれ試行錯誤するのがパズルゲーム作成の醍醐味ではないかと私は思うわけですが……)
個人的には、解が複数あるようなパズル問題はあまり出来が良いとは言えないのではという気がします。
難易度の指標として(解のパターン数+行き詰まりのパターン数)/解のパターン数、あたりでどうだろうと考えましたが、例えば、100×100ながら全てが通れるマスで一番左上がスタートであるような、人間から見れば明らかに簡単なパターンでも、分岐の数はとても多くなるので難易度は高いと判断されてしまいます。
また、マップが大きくなるほど重い処理になるので、走査をある程度で打ち切って目安とするだとか、usaoさんの仰るような簡便でコストの低い方法を探るだとか、別の指標を取ってミックスするだとか工夫も必要になりそうです。(まあ、この辺りをあれこれ試行錯誤するのがパズルゲーム作成の醍醐味ではないかと私は思うわけですが……)
個人的には、解が複数あるようなパズル問題はあまり出来が良いとは言えないのではという気がします。
void eval() {
int x, y, num_solution = 0, num_deadend = 0;
// find 1
for (int i=0; i<this->Height; i++)
for (int j=0; j<this->Width; j++)
if (this->tblVec[i][j] == 1) { x = j; y = i; i = this->Height; j = this->Width; }
eval(x, y, &num_solution, &num_deadend);
fprintf(stderr, "Solution: %d\n", num_solution);
fprintf(stderr, "Dead end: %d\n", num_deadend);
if (num_solution > 0)
fprintf(stderr, "Difficulty?: %d\n", (num_deadend + num_solution) / num_solution);
}
void eval(int x, int y, int *num_solution, int *num_deadend) {
int reserve = this->tblVec[y][x];
this->tblVec[y][x] = 0;
bool f = true; // clear?
for (int i=0; i<this->Height; i++)
for (int j=0; j<this->Width; j++)
if (this->tblVec[i][j] > 0) { f = false; i=this->Height; j=this->Width; }
if (f) {
(*num_solution)++;
} else {
f = true; // dead end?
if (y > 0 && this->tblVec[y-1][x] > 0) { // up
f = false;
this->eval(x, y-1, num_solution, num_deadend);
}
if (y < this->Height-1 && this->tblVec[y+1][x] > 0) { // down
f = false;
this->eval(x, y+1, num_solution, num_deadend);
}
if (x > 0 && this->tblVec[y][x-1] > 0) { // left
f = false;
this->eval(x-1, y, num_solution, num_deadend);
}
if (x < this->Width-1 && this->tblVec[y][x+1] > 0) { // right
f = false;
this->eval(x+1, y, num_solution, num_deadend);
}
if (f)
(*num_deadend)++;
}
this->tblVec[y][x] = reserve;
}
Re: パズルゲーム ひとふで書きの問題難易度について
mikko様
こちら貴重なサンプルコードありがとうございます。
組み込んでみたところ、問題なく数値が取れました。
行数がかなり短いですし、再帰を完璧に使いこなしているので感動しました・・・。
皆さまからアドバイスを頂いてから、色々と書いてみたのですが500行位になってまして(汗)
ソースの中身を理解するのに時間がかかりそうですので、解析させてくださいませ。
本当に助かりました!
こちら貴重なサンプルコードありがとうございます。
組み込んでみたところ、問題なく数値が取れました。
行数がかなり短いですし、再帰を完璧に使いこなしているので感動しました・・・。
皆さまからアドバイスを頂いてから、色々と書いてみたのですが500行位になってまして(汗)
ソースの中身を理解するのに時間がかかりそうですので、解析させてくださいませ。
本当に助かりました!
Re: パズルゲーム ひとふで書きの問題難易度について
この手のパズルで「難しい」って何だろう…? と考えたところ,個人的には
「先の展開が 予想/把握 できない」なのかな,とか思いました.
「あーやって,こうやれば,いけるよね」みたいな見通しが立てずらい,というか,「読み切れない」とでもいうか.
なので,
・空間の広さ : 狭いほど読み切れるので
・乱雑さ : 通るべきマスと通れないマスとが入り乱れている具合
みたいなのが評価要素になるかなぁ,とか思いました.
例えば,
TVの"砂嵐"(今はもうそんなものは無いのか?)を2値化したような問題は
かなり難しい部類に入るのではないでしょうか.
「先の展開が 予想/把握 できない」なのかな,とか思いました.
「あーやって,こうやれば,いけるよね」みたいな見通しが立てずらい,というか,「読み切れない」とでもいうか.
なので,
・空間の広さ : 狭いほど読み切れるので
・乱雑さ : 通るべきマスと通れないマスとが入り乱れている具合
みたいなのが評価要素になるかなぁ,とか思いました.
例えば,
TVの"砂嵐"(今はもうそんなものは無いのか?)を2値化したような問題は
かなり難しい部類に入るのではないでしょうか.
オフトピック
スタート地点からの全ルート探索結果をツリーとして見たときに,
正解を含まない部分木が出現する深さが浅いほど難しい…? とか思ったのですが,
そんな単純な話でもなさそうですね.
正解を含まない部分木が出現する深さが浅いほど難しい…? とか思ったのですが,
そんな単純な話でもなさそうですね.
Re: パズルゲーム ひとふで書きの問題難易度について
> スタート地点からの全ルート探索結果をツリーとして見たときに,
> 正解を含まない部分木が出現する深さが浅いほど難しい…? とか思ったのですが,
> そんな単純な話でもなさそうですね.
むしろ正解を含まない部分木の高さが影響すると思います。
迷路で例えると袋小路の長さでしょうか。
枝分かれがあっても、少し先で袋小路になることが判れば、
安心して進むことができます。
プログラムで解く場合は、また別の難易度の定義になると思います。
> 正解を含まない部分木が出現する深さが浅いほど難しい…? とか思ったのですが,
> そんな単純な話でもなさそうですね.
むしろ正解を含まない部分木の高さが影響すると思います。
迷路で例えると袋小路の長さでしょうか。
枝分かれがあっても、少し先で袋小路になることが判れば、
安心して進むことができます。
プログラムで解く場合は、また別の難易度の定義になると思います。
Re: パズルゲーム ひとふで書きの問題難易度について
お礼が遅くなってしまい申し訳ございません!
解けそうで解けないのが面白いですね(汗)
色々と問題生成してみたのですが、結構同じレベルでも波がありまして・・・。
プログラムの難しさ、人間の脳の凄さを痛感してます!
解けそうで解けないのが面白いですね(汗)
色々と問題生成してみたのですが、結構同じレベルでも波がありまして・・・。
プログラムの難しさ、人間の脳の凄さを痛感してます!