リバーシの石を置けるかの評価関数について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
A5

リバーシの石を置けるかの評価関数について

#1

投稿記事 by A5 » 5年前

リバーシの石を置けるかの判定をしたいと考えております。
8×8が通常なのですが、色々なサイトを見ていて場外の2ずつを
足したほうが良さそうだったので多めに領域を設定しております。

黒と白の表示とターンごとに石のセットまでは作れたのですが、
「石を置ける場所なのかのチェック」と「石を裏返す」処理をまだ実装出来ておりません。

「石を置ける場所なのかのチェック」のチェックだけでも実装してみたいのですが
上手く動作させることが出来ませんでした。

取りあえずは下向きに探索をかけてみて違う色があり、
同じ色が出てきたらtrueを返すみたいにしたのですが、
処理の書き方が悪く上手く動作しませんでした。

課題とかではないので急ぎではないのですが
お分かりになる方アドバイス頂けないでしょうか?

コード:

#define BOARD_MAX 10       /* 盤を表す配列 board のサイズ */

class BOARD{
public:
    MENU Button[BOARD_MAX][BOARD_MAX];
    int Board[BOARD_MAX][BOARD_MAX];   /* 盤の状態を表す配列 */
    void Init();
    bool BW( int bx, int by );			// 黒か白ならtrue
    bool SetCheck( int bx, int by, int color ); // 今回の作りたい内容
};

// 初期化
void BOARD::Init(){
    
    for ( int i=0; i<BOARD_MAX; i++ ){
        for ( int j=0; j<BOARD_MAX; j++ ){
            this->Board[i][j] = -1;
        }
    }
    for ( int i = 1; i <= 8; i++ ){
        for ( int j = 1; j <= 8; j++ ){
            this->Board[i][j] = 0;
        }
    }
    this->Board[4][5] = this->Board[5][4] = 1;
    this->Board[4][4] = this->Board[5][5] = 2;
    
    // ボタンの初期化
    for ( int i=0; i<BOARD_MAX; i++ ){
        for ( int j=0; j<BOARD_MAX; j++ ){
            int px = j*BOARD_WIDTH + 50;
            int py = i*BOARD_HEIGHT + 50;
            this->Button[i][j].Init( px, py, BOARD_WIDTH, BOARD_HEIGHT, 1.0f, 1.0f );
        }
    }

}

// 黒か白ならtrue
bool BOARD::BW( int bx, int by ){
    /*
    if( bx < 0 || by < 0 || bx >= BOARD_MAX || by >= BOARD_MAX ){
        NSLog( @"check error" );
        return false;
    }
    */
    if( this->Board[by][bx] == 1 || this->Board[by][bx] == 2 ) return true;
    return false;
}

// おけるかのチェック
bool BOARD::SetCheck( int bx, int by, int color ){

    bool cf = false;
    
    // 下向きにおけるか
    if( this->Board[by][bx] == 0 ){
        for( int y=by+1; y<BOARD_MAX; y++ ){
            if( this->BW( bx, y ) ){
                //if( this->Board[y][bx] != color ) return true;
                /*
                if( this->Board[y][bx] != color ) cf = true;
                if( this->Board[y][bx] == color && cf ) return true;
                */
            }
        }
    }
    
    return false;
}

        for( int i=0; i<BOARD_MAX; i++ ){
            for( int j=0; j<BOARD_MAX; j++ ){
                if( Board.Button[i][j].TouchCheck() && Board.SetCheck( j, i, Obj.Turn+1 )){
                    Board.Board[i][j] = Obj.Turn+1;
                    Obj.Turn++;
                    if( Obj.Turn >= 2 ) Obj.Turn = 0;
                    break;
                }
            }
        }

アバター
asd
記事: 303
登録日時: 9年前

Re: リバーシの石を置けるかの評価関数について

#2

投稿記事 by asd » 5年前

A5 さんが書きました:リバーシの石を置けるかの判定をしたいと考えております。
8×8が通常なのですが、色々なサイトを見ていて場外の2ずつを
足したほうが良さそうだったので多めに領域を設定しております。
学習のためにプログラムを作られているのだと思いますから、
なぜゲーム盤面は8x8なのに両端に余白があるのかは理解された方がいいと思いますよ。
A5 さんが書きました: 取りあえずは下向きに探索をかけてみて違う色があり、
同じ色が出てきたらtrueを返すみたいにしたのですが、
処理の書き方が悪く上手く動作しませんでした。
特定の方向に盤面を調べたとき、ありうる状態(その升目にあるもの)は何があるでしょうか。

自分の石をおく場所から順番に隣を調べていきますが、上記の状態それぞれの状態において、
取れないと判断するのか、まだ先を調べる必要があるのかを判定します。

A5さんも書いているように、自分と同じ色が出てきたら取れる可能性が出てきますよね?
ただし、置いた場所のすぐ隣に自分の色の石がある場合だけはとれません。
逆に、自分のすぐ隣ではない場所で自分の同じ石が見つかった場合はとれる可能性があるわけです。

そんなわけで、
・調査を打ち切る条件(それ以上先は調べない)
・自分と同じ色の石があった場合にさらに確認すること
が分かれば処理は出来上がるかと思います。

余談ですが、私ならとれるかどうかboolで返すのではなく、そこに置いたら何個石が取れるかを返す関数にします。
Advanced Supporting Developer
無理やりこじつけ(ぉ

A5

Re: リバーシの石を置けるかの評価関数について

#3

投稿記事 by A5 » 5年前

ご回答ありがとうございます!
なんとなく大きめに用意する理由は把握しております。

配列の要素数以外にアクセスする可能性を減らせますし、
for文で色々回せるからだと考えております。

頂いたアドバイスを元に色々と関数を改良してみました。
それっぽい動きをするのですが、たまに置けない場所でも置ける判定になってしまいます。
とりあえず斜めも1箇所だけつけたのですが、ほかがうまく動作してないので直したいです。。。

現在、下記のような形でございます。

コード:

// 何個取れるかのチェック
int BOARD::SetCheck( int bx, int by, int color ){

    
    if( bx < 0 || by < 0 || bx >= BOARD_MAX || by >= BOARD_MAX ){
        NSLog( @"Error Search" );
        return 0;
    }
    
    int num = 0;
    int rNum = 0;

    // 上向きにおけるか
    if( this->Board[by][bx] == 0 ){
        for( int y=by-1; y>0; y-- ){
            if( this->BW( bx, y ) ){
                if( this->Board[y][bx] != color && this->Board[y][bx] != 0 ) num++;
                if( this->Board[y][bx] == color  ) break;
            }
        }
        
        if( this->Board[by-1][bx] == color || this->Board[by-1][bx] == 0 ) num = 0;
    }
    
    rNum += num;
    
    // 下向きにおけるか
    if( this->Board[by][bx] == 0 ){
        for( int y=by+1; y<BOARD_MAX; y++ ){
            if( this->BW( bx, y ) ){
                if( this->Board[y][bx] != color && this->Board[y][bx] != 0 ) num++;
                if( this->Board[y][bx] == color  ) break;
            }
        }
        
        if( this->Board[by+1][bx] == color || this->Board[by+1][bx] == 0  ) num = 0;
    }

    rNum += num;
    
    // 右向きにおけるか
    if( this->Board[by][bx] == 0 ){
        for( int x=bx+1; x<BOARD_MAX; x++ ){
            if( this->BW( x, by ) ){
                if( this->Board[by][x] != color && this->Board[by][x] != 0 ) num++;
                if( this->Board[by][x] == color  ) break;
            }
        }
        
        if( this->Board[by][bx+1] == color || this->Board[by][bx+1] == 0 ) num = 0;
    }
    
    rNum += num;
    
    // 左向きにおけるか
    if( this->Board[by][bx] == 0 ){
        for( int x=bx-1; x>0; x-- ){
            if( this->BW( x, by ) ){
                if( this->Board[by][x] != color && this->Board[by][x] != 0 ) num++;
                if( this->Board[by][x] == color  ) break;
            }
        }
        
        if( this->Board[by][bx-1] == color || this->Board[by][bx-1] == 0 ) num = 0;
    }
    
    rNum += num;
    
    // ななめ
    
    // 右下向きにおけるか
    if( this->Board[by][bx] == 0 ){
        int y = by;
        for( int x=bx+1; x<BOARD_MAX; x++ ){
            if( this->BW( x, y ) ){
                if( this->Board[y][x] != color && this->Board[y][x] != 0 ) num++;
                if( this->Board[y][x] == color  ) break;
            }
            y++;
            if( y >= BOARD_MAX ) break;
        }
        
        if( this->Board[by+1][bx+1] == color || this->Board[by+1][bx+1] == 0 ) num = 0;
    }
    
    rNum += num;

    NSLog( @"%d", num );
    
    return rNum;
}

K_Tarou
記事: 22
登録日時: 6年前

Re: リバーシの石を置けるかの評価関数について

#4

投稿記事 by K_Tarou » 5年前

初めまして。
あまり、オセロのルールに詳しくないので変なことを書いてしまっているかもしれませんが...

下記のコードについてコメントを付けさせていただいた部分で、変数 "num" に 0を代入してらっしゃいますが
ここの条件は本当にこれで大丈夫でしょうか? 石を置けない状況で置けてしまうのはここが関係しているような気がします。
例えば以下のような状況で正常に動くでしょうか?

--------------------------------最上部
      白
      白
      白
      空  <----- ここに黒を置けるかをチェック
      
      //以下略
      .
      .
----------------------------------
※なんだか分かり難い気がしましたので少し修正しました。

間違ったことを書いてしまっていたら、すみません。

コード:

// 何個取れるかのチェック
int BoardGame::SetCheck( int bx, int by, BoardState color ){
 
    
   if( bx < 0 || by < 0 || bx >= BOARD_MAX || by >= BOARD_MAX ){
        NSLog( @"Error Search" );
        return 0;
    }
    
    int num = 0;
    int rNum = 0;
 
    // 上向きにおけるか
    if( this->Board[by][bx] == 0 ){
        for( int y=by-1; y>0; y-- ){
            if( this->BW( bx, y ) ){
                if( this->Board[y][bx] != color && this->Board[y][bx] != 0 ) num++;
                if( this->Board[y][bx] == color  ) break;
            }
        }// ここを抜けた時の状況は  "1:最後まで異なる色の石が続いた, 2:同じ色の石があった, 3:石がなかった"  だと思いますが、
        
        if( this->Board[by-1][bx] == color || this->Board[by-1][bx] == 0 ) num = 0;   // この条件は、上記の状態を網羅できていますか?
    }
    
    rNum += num;
    .
    .
    .
    //略
}

アバター
asd
記事: 303
登録日時: 9年前

Re: リバーシの石を置けるかの評価関数について

#5

投稿記事 by asd » 5年前

A5 さんが書きました:ご回答ありがとうございます!
なんとなく大きめに用意する理由は把握しております。

配列の要素数以外にアクセスする可能性を減らせますし、
for文で色々回せるからだと考えております。
理由は理解されていたのですね。
外周に判定が終わるような値を入れておくことで、記述頂いたように配列の範囲外アクセスを防ぐことができます。
逆を言うと、置いた場所から順番に隣を見に行く際にボードの範囲内かどうかの判定を省くことができます。
(外周に到達すると必ず判定が終了するはずなので。番兵法と呼ばれる手法です)
A5 さんが書きました: 頂いたアドバイスを元に色々と関数を改良してみました。
それっぽい動きをするのですが、たまに置けない場所でも置ける判定になってしまいます。
とりあえず斜めも1箇所だけつけたのですが、ほかがうまく動作してないので直したいです。。。
そこはぜひ明確な失敗条件を明らかにしておきましょう。
何となくうまくいく、何となく失敗するでは原因も定まらないので直しようがないです。

普通に動作させていくと手間がかかるのであれば、ボードの初期化関数でデバッグ用の盤面を作る処理を
用意しておくと、便利ですよ。

K_Tarouさんの指摘とも被りますが、とりあえずヒントを挙げておくと、

1.置こうとしている場所に既に石がある場合は問答無用で取れる数は0個(そもそも石を置けないので隣を調べる必要さえないです)
2.隣を順番に見ていく際、何も置いていない升やゲーム領域外(外周)に到達した場合、その方向で取れる石はありません。

例)☆に○石を置こうとして右方向に調べる場合
☆●●●□

途中までは自分と異なる色の石が続くので3個まではカウントされますが、
その次に何もいない升が出てきたので石は取れません。

3.別の方向を調べる場合、それまでにカウントしてきた石の数は初期化した方がいいです
 ※すべての方向で取れる石の合計rNumではなく、num

例)
以下のように上方向も下方向も石が取れる場合に、最終的に取れる石の数が狂います








☆に置こうとした場合、取れる石の合計数が狂います

次からはどういう盤面の状態でどこに置こうとしたときに考えている通りに動かないのかを載せておくといいと思います(*´ヮ`)
Advanced Supporting Developer
無理やりこじつけ(ぉ

たいちう
記事: 418
登録日時: 9年前

Re: リバーシの石を置けるかの評価関数について

#6

投稿記事 by たいちう » 5年前

10年前の本だけど、まだ入手可能なようだしご紹介します。

リバーシのアルゴリズム C++&Java対応―「探索アルゴリズム」「評価関数」の設計と実装

最終的にプログラムと対戦したいのならば、買って損はないかと。
当然、石を置けるかどうかの解説もあるので、掲示板で聞くよりも効率的だと思います。
人対人のプログラムを作りたいだけで、お金もかけたくないなら別です。

A5

Re: リバーシの石を置けるかの評価関数について

#7

投稿記事 by A5 » 5年前

皆さまご回答ありがとうございます!!
プログラムを独学で勉強していると限界があり、
このようなサイトでアドバイスを頂けて本当に助かります。

また書籍のご紹介ありがとうございました。
早速ですが購入させて頂きました。

関数に問題があるのは理解しておりますので、修正できるように頑張ります。

閉鎖

“C言語何でも質問掲示板” へ戻る