ゲームプログラミングのプログラミング例


対象としてはオセロを選ぶ,オセロのルールは以下のようになっている. オセロのルール
ゲームによらない探索の一般化をして,クラスを定義してみる.このような ことには,オブジェクト指向言語は向いている.
// 手とその評価値を表す抽象クラス
abstract class Move {
  // 評価値は doubleで表す
  double value;
  // 評価値の getter
  double getValue(){ return value; }
  // 評価値の setter
  void setValue(double value){ this.value=value; }
}

// 動かした盤面を元に戻せるように記憶
abstract class TrailStack{
}

// 盤面の状態を表す
abstract class State{
  // 次の可能手の MoveのVectorを返す
  abstract Vector nextMoves();
  // 手にしたがって盤面を変化させる.
  // TrailStackを返す
  abstract TrailStack doMove(Move move);
  // TrailStackに従って盤面を戻す
  abstract void undoMove(TrailStack trail);
  // 盤面の評価値
  abstract double eval();
}

// 次の手を決めるアルゴリズム
abstract class Search {
  // 次の手を返す
  abstract Move bestMove(State state);
}

このSearchのサブクラスとして,1手先まで読む探索プログラムを書いてみる.
// Depth1Search
// 可能手を全部生成して,その盤面の評価値で最良のものを選択する
//
class Depth1Search extends Search {
  // return null if there exists no moves
  Move bestMove(State state){
    // 可能な手を全部生成する
    Vector moves=state.nextMoves();
    int size=moves.size();
    // 最良の手が複数あるのでそれを管理する
    Vector bestMoves=new Vector();
    Move best=null;
    // 最良の手の値を負の無限大に設定しておく
    double bestVal=Double.NEGATIVE_INFINITY;
    for(int i=0;i< size;i++){
      Move move=(Move)moves.elementAt(i);
      // 1手進めてみる
      TrailStack trail=state.doMove(move);
      // 評価値を計算
      // 1手進んだ時(相手の番)の評価値なので符号を入れ替える.
      double moveVal= -state.eval(); 
      // 戻す
      state.undoMove(trail);
      move.setValue(moveVal);
      // 評価値がこれまでのbestを超えた時
      if(bestVal< moveVal){
	bestVal=moveVal;
	bestMoves=new Vector();
	bestMoves.addElement(move);
      }
      // 評価値がこれまでのbestと同じ時
      else if(bestVal==moveVal){
	bestMoves.addElement(move);
      }
    }
    // bestの中から乱数で選択
    int bestSize=bestMoves.size();
    int selected=(int)(Math.random()*bestSize);
    return (Move)bestMoves.elementAt(selected);
  }
}
MinMaxもほとんど一緒である.
//
// MinMax search
// 

class MinMaxSearch extends Search {
  // どの深さまで読むか?
  int maxLevel;
  // インスタンス生成時にレベルを設定
  MinMaxSearch(int maxLevel){
    this.maxLevel=maxLevel;
  }
  // レベルに従った評価値
  double eval(State state,int level){
    // 末端のレベルでは局面の評価値
    if(level==0) return state.eval();
    // そうでない時はベストの手の時の評価値
    Move best=bestMove(state,level);
    if(best==null) return state.eval();
    return best.getValue();
  }
  // 手の生成
  Move bestMove(State state){
    return bestMove(state,maxLevel);
  }
  // 可能な手がない時は0を返す
  Move bestMove(State state,int level){
    // 可能な手を全部生成する
    Vector moves=state.nextMoves();
    int size=moves.size();
    // 最良の手が複数あるのでそれを管理する
    Vector bestMoves=new Vector();
    Move best=null;
    // 最良の手の値を負の無限大に設定しておく
    double bestVal=Double.NEGATIVE_INFINITY;
    for(int i=0;i< size;i++){
      Move move=(Move)moves.elementAt(i);
      // 1手進めてみる
      TrailStack trail=state.doMove(move);
      // 評価値を計算
      // 1手進んだ時(相手の番)の評価値なので符号を入れ替える.
      double moveVal= -eval(state,level-1);
      // 戻す
      state.undoMove(trail);
      move.setValue(moveVal);
      // 評価値がこれまでのbestを超えた時
      if(bestVal< moveVal){
	bestVal=moveVal;
	bestMoves=new Vector();
	bestMoves.addElement(move);
      }
      // 評価値がこれまでのbestと同じ時
      else if(bestVal==moveVal){
	bestMoves.addElement(move);
      }
    }
    // bestの中から乱数で選択
    int bestSize=bestMoves.size();
    if(bestSize>0){
      int selected=(int)(Math.random()*bestSize);
      return (Move)bestMoves.elementAt(selected);
    }
    else return null;
  }
}
Alpha-Beta
//
// Alpha-beta Search
//
class AlphaBetaSearch extends Search {
  // どの深さまで読むか?
  int maxLevel;
  // インスタンス生成時にレベルを設定
  AlphaBetaSearch(int maxLevel){
    this.maxLevel=maxLevel;
  }
  // レベルに従った評価値
  // alpha
  double eval(State state,int level,double alpha, double beta){
    // 末端のレベルでは局面の評価値
    if(level==0) return state.eval();
    // そうでない時はベストの手の時の評価値
    Move best=bestMove(state,level,alpha,beta);
    if(best==null) return state.eval();
    return best.getValue();
  }
  // 手の生成
  Move bestMove(State state){
    return bestMove(state,maxLevel,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
  }
  // 可能な手がない時は0を返す
  // beta値よりも大きい値を返す場合は選ばれない
  Move bestMove(State state,int level,double alpha,double beta){
    // 可能な手を全部生成する
    Vector moves=state.nextMoves();
    int size=moves.size();
    // 最良の手が複数あるのでそれを管理する
    Vector bestMoves=new Vector();
    Move best=null;
    // 最良の手の値を負の無限大に設定しておく
    double bestVal=Double.NEGATIVE_INFINITY;
    for(int i=0;i< size;i++){
      Move move=(Move)moves.elementAt(i);
      // 1手進めてみる
      TrailStack trail=state.doMove(move);
      // 評価値を計算
      // 1手進んだ時(相手の番)の評価値なので符号を入れ替える.
      // bestValよりも小さい値は選ばれない
      double moveVal= -eval(state,level-1,-beta,-alpha);
      // 戻す
      state.undoMove(trail);
      move.setValue(moveVal);
      // 評価値がこれまでのbestを超えた時
      if(bestVal< moveVal){
        if(moveVal>beta){ // この木は刈られる
          return move;
        }
        bestVal=moveVal;
	if(bestVal>alpha) alpha=bestVal;
        bestMoves=new Vector();
        bestMoves.addElement(move);
      }
      // 評価値がこれまでのbestと同じ時
      else if(bestVal==moveVal){
        bestMoves.addElement(move);
      }
    }
    // bestの中から乱数で選択
    int bestSize=bestMoves.size();
    if(bestSize>0){
      int selected=(int)(Math.random()*bestSize);
      // return (Move)bestMoves.elementAt(selected);
      return (Move)bestMoves.elementAt(0);
    }
    else return null;
  }
}
次にオセロ固有の盤面,動きを定義してみる.
class OthelloMove extends Move{
  int position;
  OthelloMove(int position,double value){
    this.position=position;
    this.value=value;
  }
  OthelloMove(int position){
    this(position,0.0);
  }
  int getPosition(){ return position; }
  int getX(){ return position%10; }
  int getY(){ return position/10; }
}

class OthelloTrail extends TrailStack{
  int position;
  Vector reverses=new Vector();
  OthelloTrail(int position){
    this.position=position;
  }
  void add(int position){
    reverses.addElement(new Integer(position));
  }
  int getPosition(){ return position; }
  int size(){ return reverses.size(); }
  int get(int index){ return ((Integer)(reverses.get(index))).intValue(); }
}

class OthelloState extends State{
  static final int Black=1;
  static final int White=-1;
  static final int Empty=0;
  // 盤外かどうかのチェックをさぼるためには以下のチェックが有効
  static final int Edge=2;
  int board[]=new int[10*10];
  int turn;
  // 初期状態のオセロ盤を作る
  OthelloState(){
    int color;
    for(int x=0;x<10;x++)
      for(int y=0;y<10;y++){
	if(x==0 || x==9 || y==0 || y==9) color=Edge;
	else if((x==4 && y==4)||(x==5 && y==5)) color=White;
	else if((x==4 && y==5)||(x==5 && y==4)) color=Black;
	else color=Empty;
	board[y*10+x]=color;
      }
    turn=Black;
  }
  static final int directions[]={-11,-10,-9,-1,1,9,10,11};
  int opponent(int turn){ return -turn; }
  boolean checkDir(int position,int dir){
    //    System.out.println("checkDir("+position+","+dir+")");
    int oturn=opponent(turn),piece;
    if(board[position+dir]!=oturn) return false;
    for(position+=dir*2;(piece=board[position])==oturn;position+=dir){
      //      System.out.println("board["+position+"]="+piece);
    }
    //    System.out.println("lastpiece="+piece+",turn="+turn);
    if(piece!=turn) return false;
    return true;
  }
  void reverseDir(int position,int dir,OthelloTrail trail){
    int oturn=opponent(turn),piece;
    for(position+=dir;(piece=board[position])==oturn;position+=dir){
      board[position]=turn;
      trail.add(position);
    }
  }
  boolean legalMove(int position){
    if(board[position]!=Empty)return false;
    for(int dir=0;dir< directions.length;dir++)
      if(checkDir(position,directions[dir]))
	return true;
    return false;
  }
  boolean legalMove(int x, int y){
    if(1<=x && x<=8 && 1<=y && y<=8 && legalMove(y*10+x)) return true;
    return false;
  }
  Vector nextMoves(){
    Vector ret=new Vector();
    for(int x=1;x<9;x++)
      for(int y=1;y<9;y++){
	int position=y*10+x;
	if(legalMove(position))
	  ret.add(new OthelloMove(position));
      }
    return ret;
  }
  boolean canPass(){
    for(int x=1;x<9;x++)
      for(int y=1;y<9;y++){
	int position=y*10+x;
	if(legalMove(position)) return false;
      }
    return true;
  }
  void doPass(){
    turn=opponent(turn);
  }
  TrailStack doMove(Move gmove){
    OthelloMove move=(OthelloMove)gmove;
    int position=move.getPosition();
    OthelloTrail trail=new OthelloTrail(position);
    
    board[position]=turn;
    for(int dir=0;dir< directions.length;dir++)
      if(checkDir(position,directions[dir]))
	reverseDir(position,directions[dir],trail);
    turn=opponent(turn);
    return trail;
  }
  //
  void undoMove(TrailStack tstack){
    OthelloTrail trail=(OthelloTrail)tstack;
    board[trail.getPosition()]=Empty;
    int size=trail.size();
    for(int i=0;i< size;i++){
      int position=trail.get(i);
      board[position]=turn;
    }
    turn=opponent(turn);
  }
  // 一番単純な石の数による評価関数
  double eval(){
    int sum=0;
    for(int y=1;y<9;y++)
      for(int x=1;x<9;x++)
	sum+=board[y*10+x];
    return (double)(turn*sum);
  }
  int result(){
    int sum=0;
    for(int y=1;y<9;y++)
      for(int x=1;x<9;x++)
	sum+=board[y*10+x];
    return sum;
  }
  //
  void showState(){
    System.out.println(" abcdefgh");
    for(int y=1;y<9;y++){
      System.out.print(y);
      for(int x=1;x<9;x++){
	System.out.print("O.@".charAt(board[y*10+x]+1));
      }
      System.out.println();
    }
  }
}
評価関数も入れているところがあまりきれいでない.ユーザインタフェース部 分は,今回は GUI を使わずにCUIでやってみる.
class HumanSearch extends Search {
  BufferedReader d;
  HumanSearch(BufferedReader d){
    this.d=d;
  }
  Move bestMove(State state){
    OthelloState game=(OthelloState)state;
    try{
      while(true){
	System.out.println("次の手を入力してください(例 d6)");
	String str=d.readLine();
	if(str.length()==2){
	  int x=" abcdefgh".indexOf(str.charAt(0));
	  int y=" 12345678".indexOf(str.charAt(1));
	  if(1<=x && x<=8 && 1<=y && y<=8){
	    if(game.legalMove(x,y)){
	      return new OthelloMove(y*10+x);
	    }
	    else
	      System.out.println(str+"の地点には打てません");
	  }
	  else
	    System.out.println("入力の形式が間違っています"+x+","+y);
	}
	else
	  System.out.println("入力は半角2文字でなくてはいけません");
      }
    }
    catch(IOException e){
    }
    return null;
  }
}

class Othello {
  OthelloState game;
  // コンストラクタ
  Othello(){
    game=new OthelloState();
  }
  // 終局
  void gameEnd(){
    int result=game.result();
    if(result>0)
      System.out.println("黒が"+result+"個勝ちました");
    else if(result<0)
      System.out.println("白が"+(-result)+"個勝ちました");
    else
      System.out.println("引き分けです");
    System.exit(0);
  }
  void startGame(Search players[]) throws IOException {
    for(int player=0;;player=1-player){
      game.showState();
      if(game.canPass()){
	game.doPass();
	if(game.canPass()){
	  gameEnd();
	}
	System.out.println("次に打てる手はないのでパスします");
      }
      else{
	int x,y;
	OthelloMove bestMove=(OthelloMove)players[player].bestMove(game);
	System.out.println("着手は "+
			   " abcdefgh".charAt(bestMove.getX())+
			   " 12345678".charAt(bestMove.getY())+"です.");
	System.out.println("評価値は "+bestMove.getValue()+"です.");
	game.doMove(bestMove);
      }
    }
  }
  // main関数
  public static void main(String args[]) throws IOException{
    Othello othello=new Othello();
    BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
    Search players[]=new Search[2];
    players[0]=new HumanSearch(d);
    //    players[0]=new Depth1Search();
    //    players[0]=new MinMaxSearch(6);
    players[1]=new MinMaxSearch(6);
    othello.startGame(players);
  }
}
できあがったプログラム全体は,Othello.javaである.
弱いプログラムだが,簡単に書けて,探索アルゴリズムを変化させるのも容易 にできる.
現在,一番強いとされるオセロプログラムは LOGISTELLO で,人間のチャンピオン相手に大差で勝つ実力を備えている.作者の Michael Buroは LOGISTELLO で使われている技術情報をかなり公開しているので,オセロプログラムを作る人には大変参考になるはずである.

次に進む