Tic Tac Toe “我也不知道是什么”算法

为了巩固类、数组等知识,下来一个Assignment,定睛一看,居然是个四子棋!没想到人在江湖,也会遇上如此困难之题,随缘写个备注以防自己忘记。

完整代码已上传至 timrockefeller/ExplotionEuler


这次我请到了我在崔斯特姆遇见的朋友,Millie桑!(欢呼、鼓掌)

Millie: 大家好嘿,我是Millie,今天呢很高兴见到大家耶!

对于这个棋局,你怎么看呢?

Millie: 什么棋局?

那个啥、井字棋啊。

Millie: 噢那个我没输过诶~

巧了我也没输过。回归正题,Millie你就坐旁边看就好了。

Millie: 这么没人权吗quq?是你让我过来的诶、

导演开始吧。


构建棋盘

棋盘就用3*3数组表示吧,数组类型可以记为枚举ChessType

1
2
3
4
5
6
enum ChessType{
CROSS,
CIRCLE,
BLANK,
NULL
}

这里分为四种:叉、圈、空、未知。这个“未知”只是用于检测是否越界来着,棋盘之外便是虚空

接着我们需要写第一个类:Board,它需要完成存储、读写、判断、输出图形这些功能。让Miilie带我们看看这个类的组成部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//嗨嗨,我是Millie~~电视台终于转到我这里了
class Board{
public Board ();//构造函数,创建一个map被ChessType.BLANK填满的新地图。
public Board (ChessType[][] _map);//构造函数,创建一个和传入_map完全相同的复制。
private ChessType[][] map;//地图保存的地方,用[x][y]获取。
public ChessType getBoard(Position pos);//检验是否越界,返回这个点的ChessType,越界则返回ChessType.NULL。
public boolean setBoard(Position pos,ChessType type);//将pos位置的棋子设置为type,检测非空、不越界。成功就返回True~
public void setBoardF(Position pos,ChessType type);//全称是setBoard Force!或者FFF,反正就是强行设置的意思啦~
public void drawBoard();//画画画~画棋盘,怎么好看怎么画,疯狂println。
private String gs(ChessType t);//为了drawBoard服务,把t变成圈圈○或叉叉×。
public ChessType judge();//JUDGE~~!!会返回到底谁连成一条线了!没有的话就返回ChessType.BLANK。
public boolean isFull();//棋盘是不是满了?被……灌满了❤?
public Board clone();//返回一个复制体,用到上面的重载构造函数~
}

Millie: 细节就不放了,其中的Position类:

1
2
3
4
5
6
7
8
9
10
class Position{
public Position(){
this.x=0;this.y=0;
}
public Position(int x, int y){
this.x = x;this.y = y;
}
public int x;//坐标x
public int y;//坐标y
}

超简单的,传入pos等变量的时候直接 new Position(x,y) 就好了,当然开发大型游戏的时候它就不能叫Position了,而是Vector2(二维向量),相关函数在MizuhaPic这个写了一半(没有,没有一半,连1%都没有)的游戏引擎里出现过。

Millie: 这个类在后面经常被用到,不停地被克隆,是这个作业、呸游戏的重要成员。以及MizuhaPic怕是要弃坑了。

棋盘有了,我们还需要玩家。玩家分为两类:电脑。他们都可以继承于同一个抽象类:Player

1
2
3
4
5
6
7
8
9
abstract class Player{
//工作流程是:
// 1. 轮到玩家了
// 2. onTurn()执行并把hand调整到想要落子的地方
// 3. 外面函数把这hand给落下去
public abstract void onTurn(Board b);//这就是那个函数,每次回合开始都需要调用这个函数
public Position hand;//临时存放准备落子位置
public ChessType type;//确定玩家是叉♂叉还是圈♀圈
}

人类玩家就可以用new Scanner().NextInt()来获取棋子位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Player_Human extends Player{
public Player_Human(ChessType _type){//构造函数呗
this.type= _type; this.hand = new Position();
}
@Override
public void onTurn(Board b){
this.readInput();//直接跳到下面去了……
}
private void readInput(){//从上面跳水下来
Scanner input = new Scanner (System.in);//垃圾话
System.out.print("input x and y (1-3): ");//垃圾话2
this.hand.x = input.nextInt() - 1;//输入棋子位置x
this.hand.y = input.nextInt() - 1;//输入棋子位置y
}
}

那么我们准备好了玩家、棋盘,就需要找个房间来玩,于是我们的老大Game类就来了。同样让Millie为我们解说。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Game {
public Game();//构造函数,运行的时候顺便new几个player,可以选择一波~ 最后`this.run()`走起!
private int round;//回合数
private Board board;//棋盘咯?
private Player[] players = new Player[2];//两位玩家的凉席
private int turn;//谁的回合?你的?p,我的。
private boolean gaming;//配合run()函数的使用,判断时候游戏结束。
private void nextTurn();//轮到下个玩家啦~
private ChessType getTurnType(int _turn);//把数字0、1变成ChessType
private void run();//新的游戏~里面有个while(this.gaming),来结束游戏。
private void gameEnd(ChessType type);//赢啦~说些什么~
private void retry();//老板,再来一局!!
}

巧妙的是这个类只用生成一个对象,也就是传说中的游戏开发设计模式里的单例模式,应该吧。
很棒,一个完整的TicTacToe游戏就完成啦,好好玩玩吧~


以下是未知代码,谨慎阅读!

Millie: 在设计机器人的时候,根本不知道怎么写,好难受、好难受,硬憋憋出一个不明效果的回溯方法。具体就是:检测所有的可走路径Class.Way,保存在ArrayList里面,虽然有胜率、败率等权值,但是找不到一个合适的算法解析它们……不管了先来看吧(>^ω^<)

Millie: 在那之前我们需要准备两个类,一个是路径Way,一个是节点Node。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Node{
public Node(){this.p= new Position(0,0);}
public Node(Position pos,int i){this.p=pos;this.inspire=i;}
public Position p;//节点位置
public int inspire;//启发值,应该是这么叫的?
}
class Way {
public Way() {
this.step = new Node();
}
public Way(Node s){
this.step = new Node(new Position(s.p.x, s.p.y), s.inspire);
}
public int stats;// ==0:draw , >0:win , <0:lose
public Node step;//原来是ArrayList<Node>,但迷茫了。
@Override
public Way clone(){
return new Way(this.step);
}
}

Millie: 好的!结束!我写不懂了……接下来就是战争迷雾模式

1
2
3
4
5
6
7
class Player_PC extends Player{//同样是继承于Player之下,你怎么就这么鬼畜呢??
public Player_PC (ChessType _type);//构造函数,功能大致和Human相同
public void onTurn(Board b);//有必胜走必胜,有必输走必输,两个都没有就刷nextStop()。
private static ChessType getOppoType(ChessType _type);//小工具,获得对手方。(圈变叉、叉变圈)
private ArrayList<Way> ways;//保存那几个路径
private void nextStop(Board b,Way way,int depth,ChessType inType);//一个回溯递归算法,确实能测量步数启发值和胜率,但是结果还是很诡异。
}

Millie: 仔细看看那个nextStop():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private void nextStop(Board b, Way way, int depth, ChessType inType){
boolean newWay = false;//是否需要创建一条新路
boolean full = true;//全下满了?
for(int x = 0; x<3;x++){//遍历
for(int y = 0; y<3;y++){//又遍历
if(b.getBoard(new Position(x,y))==ChessType.BLANK){//如果可以落子
full = false;//可以落子说明还没满啦~~
Way _way;//新指针,用于各种传递
if ( newWay ) {//第二次循环就会是true
_way = way.clone();//克隆一条路
this.ways.add(_way);//并把它添加到路的集合
} else {
newWay = true;//第一次不是新路,第二次就是了
_way = way; //第一次,很朴素,一条大路走到底
}
if(depth==0)//如果是这条路的第一步
_way.step=new Node(new Position(x, y), depth);//那你就是这回合接下来要走的那一步
b.setBoardF(new Position(x, y), inType);//走一波,落子!!
ChessType wms=b.judge();//看看谁赢了
if(!b.isFull())//如果还没满
this.nextStop(b.clone(), _way, depth+(wms==ChessType.BLANK?1:0), getOppoType(inType));//接着走(为了概率相同)
else if(wms != ChessType.BLANK)//满了好说,看看这样走谁会赢
_way.stats=wms==this.type?(10-depth):(depth-10);//谁赢谁加分
b.setBoardF(new Position(x,y),ChessType.BLANK);//恢复棋盘,接着循环~~
}//♪(^∇^*)
}//\(^o^)/~
}
}

Millie: 问题是有,但是不知道在哪里quq,难受

Millie: 再您妈的见。