質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.79%

c言語 アルゴリズム

受付中

回答 5

投稿

  • 評価
  • クリップ 2
  • VIEW 872

miso_soup

score 19

c言語で宝探しゲームのようなプログラムを作りました。
そこで自動で宝を探してくるようなプログラムを作りたくて、
アルゴリズムなどを考えたのですがどのようにしたら良いのか難しくて、
良い方法がありましたらご回答頂きたいです。

イメージ説明
10×10の図の中にランダムに宝が8個配置される。
Input : b1と入力すると周囲8近傍に宝がいくつあるか表示される。
宝がある座標をInput:に入力すると$と返す。

私が考えたのはb1,e1,h1,j1,b4,e4,h4,j4,b7,e7,h7,j7,b9,e9,h9,j9
をinputで入力したら被りが一番少なく探せるのかなと思いました。
それをどのような手順ですれば良いのでしょうか?
宝8個を全て自動で探索するアルゴリズムはどのようにしたら良いでしょうか?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • miso_soup

    2019/05/25 02:23

    説明が下手で申し訳ないです。
    Inputにa0と入力するとb0,a1,b1に宝が何個あるかどうかをInputにb0を入力するとa0,c0,a1,b1,c1に宝が何個あるかどうかをa0とb0の座標に返してくれるので、a1,b1が2回調べられることになるので、それをできるだけ少なく調べようとしたらb1,e1,h1,j1,b4,e4,h4,j4,b7,e7,h7,j7,b9,e9,h9,j9をまず調べるのがいいのかなと思いました。
    b1,e1,h1,j1,b4,e4,h4,j4,b7,e7,h7,j7,b9,e9,h9,j9をInputで入力したら全てのマスの宝があるいうことが
    わかるので、そこからどのようにして宝を見つけていけば良いのでしょうか?

    キャンセル

  • miso_soup

    2019/05/25 02:29

    > 宝がある座標をInput:に入力すると$と返す。
    これは,例えば,「c5」と入力してその箇所に宝があったら,該当のc5マスには「$」と表示される
    (=b1マスのように周囲の宝の個数は教えてくれない)
    ということでしょうか?
    そうですね、c5と入力して宝があった場合は$と表示されるので周囲8近傍の宝の数は数えてくれないので
    そうなった時の処理も考えないといけないですよね

    キャンセル

  • ikadzuchi

    2019/05/25 16:14

    > 全てを考えると100手かかってしまうので、もっと効率的な方法を考えたいということです。
    では「被りが」一番少なくではなく、「手数が」一番少なくが目的ということでよいですね?
    あとは「一番少なく」の方ですが、まあ話を聞く感じでは最悪値を少なくするのかなあという気はします。
    まあ何にせよそう簡単に厳密解が求まるものではないと思います。

    キャンセル

回答 5

+2

(早いとは思わないので,回答としては不適切かもしれませんけど)
ものすごく簡単に思いつく方法としては
【とりあえずマス毎に「宝がありそうな確率」を持っておいて,確率が高い個所から掘っていく】
という方法が考えられますね.
同じ確率のマスが複数ある場合には,掘られていない隣接マスが多い個所を優先するとかで.

初期状態は,10×10マスに宝が8個だから,全マスの確率値は8/100

b1を掘ったら「1」が出た
→その周囲のマスの確率を1/8に更新
→他の箇所の確率は 7/91 に更新

{b2,c1,c2}のどれかを選んで掘る

みたいな.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/24 11:59

    自分で書いたくせして,【確率の更新が馬鹿(=私)には無理なレベルで難しい】ことに気付いたので,誰か低評価しておいてください.

    キャンセル

  • 2019/05/25 11:19

    低評価って言ったのに+になってる謎

    キャンセル

  • 2019/05/25 11:48

    すまん、俺が高評価を押しました。

    確率の出し方は考えるだけでも凄くめんどくさいですが、方向性としては十分にありだと思います。

    キャンセル

  • 2019/05/25 14:13

    ベイズ推定、潜水艦沈没事故。

    キャンセル

+1

  • 絶対に宝が無いとわかるところを選ばない
  • ヒントの数値がでかいやつの周囲を先に選ぶ

みたいな簡素な方法を実装してみました.
(微妙にところどころC++成分入ってますが,読める範疇かと.)


全体的に使う構造体と定数

//[Pos.h]
#pragma once

//座標(x,y)を表すだけの構造体
struct Pos
{
    int x, y;
    Pos( int x=0,int y=0 ) : x(x),y(y) {}
};
//[SysDefs.h]
#pragma once

//マップのサイズ
#define MAP_W   10
#define MAP_H   10
//宝の総数
#define N_TREASURE  8

ゲームのルール部分側の実装("Sys"とかいう命名がダサい^^)

//[SysSide.h]
//ゲームのルール側の実装
#pragma once
#include "Pos.h"

//状態初期化.
void Sys_Init();

//指定のマスを開く.
//・Sys_Show()によって表示される内容が更新される.
//・指定マスに関する情報を返す.
//
//戻り値は,
//・指定マスに宝が無い場合は,その8近傍に存在する宝の個数
//・指定マスが宝の場合には,負の値
int Sys_Open( const Pos &OpenPos );

//現状態の表示
void Sys_Show();
//[SysSide.cpp]
#include "stdafx.h" //VC
#include "SysSide.h"
#include "SysDefs.h"
#include <cmath>

//表示内容バッファ
static char ShowBuff[MAP_H][MAP_W + 1];

//※とりあえず宝の位置は固定のハードコーディング※
static const Pos TreasurePos[N_TREASURE] =
{
    Pos( 0,1 ), Pos( 1,8 ), Pos( 2,2 ), Pos( 5,0 ),
    Pos( 5,4 ), Pos( 6,4 ), Pos( 6,3 ), Pos( 8,7 )
};

//
void Sys_Init()
{
    //全マスの表示内容を'+'に初期化
    for( int y=0; y<MAP_H; ++y )
    {
        for( int x=0; x<MAP_W; ++x ){   ShowBuff[y][x] = '+';   }
        ShowBuff[y][MAP_W] = '\0';
    }
    //※本来はここで,TreasurePos[]の内容を乱数とか使って決めれば良いかと※
}

//
int Sys_Open( const Pos &OpenPos )
{
    int nTreasureArround = 0;
    for( int i=0; i<N_TREASURE; ++i )
    {
        int dx = abs( OpenPos.x - TreasurePos[i].x );
        int dy = abs( OpenPos.y - TreasurePos[i].y );
        if( dx==0 && dy==0 )
        {
            ShowBuff[OpenPos.y][OpenPos.x] = '$';
            return -1;
        }
        if( dx<=1 && dy<=1 ){   ++nTreasureArround; }
    }
    ShowBuff[OpenPos.y][OpenPos.x] = '0' + nTreasureArround;
    return nTreasureArround;
}

//
void Sys_Show()
{
    for( int y=0; y<MAP_H; ++y ){   printf( "%s\n", ShowBuff[y] );  }
}

アルゴリズム側のヘッダ

//[AlgoSide.h]
//宝を探すアルゴリズム側の実装
#pragma once
#include "Pos.h"

//状態初期化
void Algo_Init();

//開くマスを決める.
Pos Algo_DecideOpenPos();

//アルゴリズムに,マスPに関する情報を与える.
//( Algo_DecideOpenPos()が返した場所Pに関する,Sys_Open(P)の結果をアルゴリズムに教える用 )
//
//InfoVal は
//・マスPに宝が無い場合は,その8近傍に存在する宝の個数
//・マスPが宝の場合には,負の値
void Algo_Update( const Pos &P, int InfoVal );

mainはこんな感じで.

#include "SysSide.h"
#include "SysDefs.h"
#include "AlgoSide.h"

int _tmain(int argc, _TCHAR* argv[])
{
    //初期化
    Sys_Init();
    Algo_Init();

    //宝探す処理
    int nIter = 0;
    int nTreasureRest = N_TREASURE; //未発見の宝の個数
    while( nTreasureRest>0  &&  nIter<MAP_W*MAP_H )
    {
        ++nIter;
        Pos OpenPos = Algo_DecideOpenPos();
        int OpenResult = Sys_Open( OpenPos );
        if( OpenResult < 0 ){   --nTreasureRest;    }
        Algo_Update( OpenPos, OpenResult );

        printf( "Turn %d : (%d,%d) -> %c\n", nIter, OpenPos.x, OpenPos.y, (OpenResult<0 ? '$' : '0'+OpenResult) );
        Sys_Show();
        printf( "-------------------------------\n\n" );
    }

    printf( "Total Turn = %d\n", nIter );
    printf( "Rest Treasure Count = %d\n", nTreasureRest );
    getchar();  //Press Enter_Key to Quit
    return 0;
}

(…と,ここまでくらいの物を質問する側で指定してもらえると,回答書く人もそれを読む人もやり易くてよいのではないなかぁ,とか思う)

で,アルゴリズムの実装.

//[AlgoSide.cpp]
#include "stdafx.h" //VC
#include "AlgoSide.h"
#include "SysDefs.h"

//作業関数.
//Pの8近傍のマスの座標をDstの先頭側に入れる.
//戻り値は入れた個数(=近傍マスの個数)
int GetNeighbors( const Pos &P, Pos (&Dst)[8] )
{
    const int DX[8] = { -1, 0, 1,  -1,1,  -1,0,1 };
    const int DY[8] = { -1,-1,-1,   0,0,   1,1,1 };

    int nNeighbor = 0;
    for( int i=0; i<8; ++i )
    {
        int x = P.x + DX[i];
        int y = P.y + DY[i];

        if( x<0 || y<0 || x>=MAP_W || y>=MAP_H )continue;

        Dst[ nNeighbor ] = Pos(x,y);
        ++nNeighbor;
    }
    return nNeighbor;
}

//マスの情報用構造体
struct Info
{
    bool IsOpened;  //開いたマスはtrueにする
    bool TreasureNotExist;  //宝が無いとわかった場所はtrueにする→次回から見なくていい
    int InfoVal;    //マスを開いて得られた結果.
    int NotOpenedPosArround;    //8近傍で開いていないマスの個数
    int nFoundTreasureArround;  //8近傍に見つけた宝の個数

    Info() :
        IsOpened(false), TreasureNotExist(false),
        InfoVal( -1 ), NotOpenedPosArround(8), nFoundTreasureArround(0)
    {}
};

//情報バッファ
static Info Data[MAP_H][MAP_W];

//(x,y)のスコアを計算する作業関数
double CalcScore( int x, int y )
{
    if( Data[y][x].IsOpened || Data[y][x].TreasureNotExist )return -1;

    double Score = 0;
    Pos NeighborPos[8];
    int n = GetNeighbors( Pos(x,y), NeighborPos );
    for( int i=0; i<n; ++i )
    {
        const auto &ND = Data[ NeighborPos[i].y ][ NeighborPos[i].x ];
        if( ND.IsOpened )
        {
            if( ND.InfoVal < 0 )continue;   //宝のマスからは情報を得られない
            if( ND.InfoVal <= ND.nFoundTreasureArround )
            {//このマスに宝はない
                Data[y][x].TreasureNotExist = true; //次回以降見なくていいフラグを立てておく
                return -1;
            }

            Score += (double)ND.InfoVal / ND.NotOpenedPosArround;
        }
    }
    return Score;
}

//初期化
void Algo_Init()
{
    for( int x=1; x<=MAP_W-2; ++x )
    {   Data[0][x].NotOpenedPosArround = Data[MAP_H-1][x].NotOpenedPosArround = 5;  }

    for( int y=1; y<=MAP_H-2; ++y )
    {   Data[y][0].NotOpenedPosArround = Data[y][MAP_W-1].NotOpenedPosArround = 5;  }

    Data[0][0].NotOpenedPosArround = 3;
    Data[MAP_H-1][0].NotOpenedPosArround = 3;
    Data[0][MAP_W-1].NotOpenedPosArround = 3;
    Data[MAP_H-1][MAP_W-1].NotOpenedPosArround = 3;
}

//開く箇所を決める
Pos Algo_DecideOpenPos( )
{   //全てのマスに関して,適当なルールで得点を算出し,一番得点が高い個所を開く場所とする
    Pos Ret;
    double MaxScore = -1;
    for( int y=0; y<MAP_H; ++y )
    {
        for( int x=0; x<MAP_W; ++x )
        {
            double Score = CalcScore( x,y );
            if( MaxScore < Score )
            {
                Ret = Pos( x,y );
                MaxScore = Score;
            }
        }
    }
    return Ret;
}

//情報更新
void Algo_Update( const Pos &P, int InfoVal )
{
    if( Data[P.y][P.x].IsOpened )return;    //一応チェック
    //マスPの情報更新
    Data[P.y][P.x].IsOpened = true;
    Data[P.y][P.x].InfoVal = InfoVal;
    {//Pの周囲のマスの情報を更新
        Pos NeighborPos[8];
        int n = GetNeighbors( P, NeighborPos );
        for( int i=0; i<n; ++i )
        {
            --Data[ NeighborPos[i].y ][ NeighborPos[i].x ].NotOpenedPosArround;

            if( InfoVal<0 ) //マスPに宝が見つかったとき
            {   ++Data[ NeighborPos[i].y ][ NeighborPos[i].x ].nFoundTreasureArround;   }
        }
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

「マインスイーパー アルゴリズム」で検索してください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/24 08:13

    Inputをどのように入力していくと宝が早く見つかるのでしょうか?

    キャンセル

  • 2019/05/24 08:16 編集

    マインスイーパーですよね?
    このキーワードで解法アルゴリズムみつかりませんでした?
    私のところでは複数表示されたんですが。
    Google を使ってみてください。https://google.com

    キャンセル

  • 2019/05/24 22:03 編集

    マインスイーパーとは全くルールが異なりますよ。0のマスを踏んでも、周りが勝手に開いてくれると言うことはないのですから。似たようなモノで言うと、海戦ゲームやバトルシップと言われるゲームに近い物があると思います。

    キャンセル

  • 2019/05/24 22:13

    ルールの一部が伏せられているのかと思ったんですが、外れっぽいですね。

    キャンセル

0

より少ない回数を目指すならfanaさんの回答みたいな手段がいいと思いますが、確率を出していくのが非常に面倒です。ということで、もうちょっと妥協したものを考えたいと思います。

  1. 全てのマス分の整数値二次元配列(takara_m)を用意して0にする。
  2. 全てのマス分の整数値二次元配列(num_m)を用意して0にする。
  3. takara_mで0のマスから一つランダムに開く。
  4. それが宝の場合は8.へ飛ぶ。数値の場合は5.以降を行う。
  5. (数値の場合分岐)takara_mを-2にする。
  6. マスを開いた出た数値をnum_mに追加する。
  7. num_mが0になる場合は、近傍8マスについてtakara_mが0のものは全て-1にする。
  8. 最初の1.に戻る。
  9. (宝の場合分岐)takara_mを1にする。
  10. 近傍8マスについてnum_mを一つ減らす。
  11. 近傍8マスでtakara_mが-2かつnum_mが0になる場合は、そのマスの近傍8マスについてtakara_mが0のものは全て2にする。
  12. 最初の1.に戻る。 

宝が「0ある可能性がある」「1ある」「-1ある可能性はない」「-2ない」かをフラグ管理する二次元配列(takara_m)と、周りの個数を数える二次元配列(num_m)を用意します。周りの個数は、宝が周りに見つかる度に1減らしていき、そのマスを開いたときにその数値を足すというものです。既に開いたマスでnum_mが0になるということは、そのマスを開いたときの数値分の宝はすべて見つかっているはずですので、他のマスを「-1ある可能性はない」に変えていきます。

こうしてフラグを変えながら「0ある可能性がある」だけを次々に開いていけば、「-1ある可能性はない」というマスは避けられますので、ある程度は効率的にできるのではないだろうかと思われます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/27 10:19

    手順3.の開く箇所の選び方は完全ランダムなんでしょうか.
    感覚的にはヒントの数字がたくさん隣り合う箇所ほど「確定ではいが宝がありそう」な気がするからそういう箇所を優先的に開いてみたくなりそうだけども,
    別の箇所を先に開いてヒントを増やして宝の箇所を確定させていく方が早くなるのかも?

    キャンセル

  • 2019/05/27 18:43

    この方法では完全ランダムです。もっとありそうと言うところを開いて行ければ良いのですが、妥協して、確率が0のところだけ注意してみようというものです。数値が見つかったら、数値に応じて周りの確率をあげるとか、そういった工夫をしていけば、もっと少ない回数で宝を見つけることができるでしょう。

    キャンセル

-1

どのようなルールなのか分かりませんが、下記のような感じで探索していけばいいのでは?

int 探索(int x,int y){
    int sum;
    char c = Input[x][y];
    if(c == '1'){ return x*10 + y; } 
    if(x < 10 || y < 10){
        sum = 探索(x + 1,y);
        if(sum != -0xFF){ return sum; } 
        sum = 探索(x,y + 1);
        if(sum != -0xFF){ return sum; } 
    }
    return -0xFF;//ここは適当
}

すみません。
疑似的なのと、多分C++の仕様で書いてしまった?からそのまま移植しても動かないと思うけど...
こんな雰囲気だけ伝わればいいです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.79%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る