Java游戏直棋(二)

类别:Java 点击:0 评论:0 推荐:

本部分为电脑的人工智能。

        为了加快AI的计算速度,必须对前面的设计进行少量的修改,并最终向VC平台转移。在用VC实现的游戏中,棋盘将采用BitBoard技术,棋子的显示将彻底和逻辑分开。目前JAVA版本仍然采用数组表示棋盘,主要是便于逻辑分析和设计。

        先对第一个AI进行总结。FirstAI:

package nicholas.game.chess;

class FirstAI extends ChessPlayer {
 
 private ChessModel model[][][];
 private StepStack stack;
 private Step step;
 private int layer;
 private int turn;
 protected GameRule gameRule;
 
 public FirstAI(int t) {
  super(false);
  stack = new StepStack();
  layer = 7;
//  layer = 3;
  turn = t;
 }
 
 public String getName() {
  return "ColinRobot";
 }
 
 public Step getNextStep(ChessModel m[][][]) {
  //algo
  model = m;
  System.out.println("max="+getLayerValue(0));
  stack.removeAll();
  return step;
 }
 
 //get largest value
 private int getLayerValue(int lay) {
  if(lay>layer) {
   //no recursion
   return -1*getModelValue();
  }
  int value = 0;
  int max = -2000;
  int decision;
  for(int z=0;z<3;z++) {
   for(int y=0;y<3;y++) {
    for(int x=0;x<3;x++) {
     if((x==1&&y==1)||model[z][y][x].isOccupied()) continue;
     //assume lay chessman here
     model[z][y][x].acceptChessman(Chessman.CHESS[(turn+lay)%2]);
     decision = gameRule.checkStep(model[z][y][x], model);
     switch(decision) {
      case 0://win
       stack.add(new Step(model[z][y][x],decision));
       value = 1000;
       break;
      case 3://tiaodan|gan
       gameRule.checkDecision(model[z][y][x],1,model);
       stack.add(new Step(model[z][y][x],1));
       value = 660;
/*       value = -1*getLayerValue(lay+1);
       //roll back
       gameRule.undoStep(stack.remove(),model);
       model[z][y][x].acceptChessman(Chessman.CHESS[(turn+lay)%2]);
       //another
       gameRule.checkDecision(model[z][y][x],2,model);
       stack.add(new Step(model[z][y][x],2));
       int b = -1*getLayerValue(lay+1);
       //choose better
       if(value<b) {
        value = b;
       } else {
        //roll back
        gameRule.undoStep(stack.remove(),model);
        model[z][y][x].acceptChessman(Chessman.CHESS[(turn+lay)%2]);
        //redo first
        gameRule.checkDecision(model[z][y][x],1,model);
        stack.add(new Step(model[z][y][x],1));
       }
*/       break;
      case 1://tiaodan
       stack.add(new Step(model[z][y][x],decision));
       value = 660;
       break;
      case 2://gan
       stack.add(new Step(model[z][y][x],decision));
       value = 320;
       break;
      default://tiaodan,gan,none
       stack.add(new Step(model[z][y][x],decision));
       value = -1*getLayerValue(lay+1);
     }
     if(value>max) {
      max = value;
      if(lay==0) {
       //first layer, save step
       System.out.println("max="+max);
       step = stack.getTop();
      }
     }
     //remove chessman
     gameRule.undoStep(stack.remove(),model);
     if(max==1000) return max;
    }
   }
  }
  return max;
 }
 
 private int getModelValue() {
  return 3;
 }
 
 public void setGameRule(GameRule rule) {
  gameRule = rule;
 }
}

FirstAI直接继承ChessPlayer,以后将转为间接继承。采用最大最小深度优先搜索,结束对某分支(仅当前层次)的搜索的两个条件为:A.该层次玩家赢。B.最深搜索层次。最深搜索层次时将返回对局面的评估值(未设计,一律返回3,表示落子得3分。)。

后面的设计,除BitBoard实现棋盘外需要考虑几个问题:
1)搜索的层次。针对第一步着法,强制去除部分无关分支(x+y>2),再将搜索层次设置为7,即可得到正确的着法。因此估计最大的搜索层次设置为7即可。
2)算法的改进。即使搜索层次仅为7,计算一步也要考虑46亿种可能性,假设每种可能性需要60次运算,以我的本本的配置需要三分钟。是否设计开局库(计算表明部分落子仅有唯一应手);另外将考虑采取其它的搜索技巧;破直将有额外的奖励(局面值>3);考虑可杠可单时,单是否一定比杠有利。
3)局面的估值。比较复杂,考虑中。

本文地址:http://com.8s8s.com/it/it10890.htm