Connect4

GitHub - RichardS0268/Connect4: Project 3 of THU course Introduction to AI

Using MCTS and UCT algorithms play Connect 4 (The rules are a little bit different. More details). Evaluation is based on competition results with existing .so in ./TestCases. bash compile.sh bash compete.sh 5 // how many rounds with each .so you want to play python stat.py Output example

https://github.com/RichardS0268/Connect4

1. 问题描述

2. 模型与算法

2.1 整体框架

2.2 实现细节

1. Selection：每轮开始前依据己方和对方的上一个决策（共两步）对树进行换根，建立UCT 树，根的子节点即每一列可落子的状态。

2. Expansion：从根出发，若当前点可以扩展新的子节点，则扩展并选中新扩展的点。若当前点无法扩展新的子节点，则选中以当前点为根的子树中得分最高的叶节点。得分规则（UCB）为
其中 为当前节点， 为考察的子节点。 为 被回溯的次数， 为 回溯总得分。

3. Simulation：将新的子状态进行模拟，双方轮流随机落子，并在该过程中添加启发性策略（见2.3.1）进行优化。

4. Backpropagation：将模拟产生的结果——胜（1分），平（0分），负（-1分）作为收益回传至根，选择根收益最大的一个子节点作为最佳落子点。

1. class Agent

class Agent {
  private:
			...
      int treePolicy(int x, Status* board);
      int defaultPolicy(int x, Status* board);
			void backTrack(int x, int value);
  public:
			...
      Agent(int N, int M, int noX, int noY);
      std::pair<int, int> Search();
      void RootChangeTo(std::pair<int, int> decision);
			...
  };

1. struct Node

struct Node {
	  int child[MAX_WIDTH]; // 子节点
	  int cnt, value; // N(v), Q(v)
	  int parent; // 父节点
		void refresh(int parent_) // 重用前重置 (见2.3.2)
}

1. struct NodePool

struct NodePool {
    int q[MAX_TREE_NODE + 10];
    int h, w;
    NodePool() : h(0), w(0) {}
    void enqueue(int x) {...}
    int dequeue() {...}
    bool empty() {...}
}

1. class Status

class Status {
  private:
			...
			int n, m, noX, noY;
      enum State {win, draw, running, lose};
      unsigned horizon[12], vertical[12], diag1[30], diag2[30]; // 状态压缩(见2.3.3)
      int top[12]; // 12列（竖向）的顶端位置
      UrgentList urgentList[2]; 
      bool urgent[2][13][13]; // Urgent Threat信息
	public：
			...
}

2.3 性能优化

• threat:
如果一个点被A的对手B占领后，B会连起4个子，则这个位置是A的 threat。

• urgent threat:
可以在这一手棋下到的 threat。

1. 如果对手有urgent threat, 则下在那里即可获得胜利。

2. 如果自己有urgent threat, 则必须下在那里，否则下一步对手可以下在那里并获胜。

3. 按UCT算法进行落子，但不能落在对手threat的下面一格。

1. 若玩家落子前，他的对手有urgent threat，则玩家可以将子下在那个位置直接取得胜利。

2. 若对手没有urgent threat
1. 若某玩家存在两个urgent threat，则无论他将棋子落在何处，对手均可以将棋下在urgent threat处取得胜利。因此，如果下完一手棋后，对手出现两个urgent threat, 且己方没有urgent threat, 则己方必胜。如果己方落子前已有两个urgent threat且对手没有urgent threat，则己方必败。
2. 若玩家有一个urgent threat，并且这个位置上面也是他的threat，则玩家必败。反之，若对手出现这种情况，则玩家必胜。
3. 玩家A落子后，玩家B所有可行的落子点上方都是自己的threat，则玩家A必胜.

• 删除节点时，设原树根为 root1，新树根 root2 为 root1的子节点。则在RootchangeTo 时需删除 root1 及 root2 的兄弟节点
• 将 root1 的子节点信息清空并放入NodePool中
• 将 root2 的兄弟节点放入NodePool中

• 新建节点时，直接从NodePool中取一个节点，并将其子节点放入内存池中（见Agent::newNode），再将其重置（refresh）后即可使用.

1. 将落子点的四种状态：空位，不可落子点，已有A子，已有B子分别用00011011表示。

2. 为实现方便，将棋盘的四周全部列为不可落子点位置，这样每一行和仅需用位的二进制数表示，并可用int实现。列和斜向的操作类似，两种斜向可分别视为把 相同的以及把 相同的归为一行。
示意图如下（以4*5棋盘为例）

• 则最低行可用 表示，最右边一列可用橙色对角线可用 表示。

• 落子后，可通过位操作取出落子点及其周围的连续四个位置的编码，若为，，，中的一个，则出现了一个A的threat (即B还差一个位置就可连成四个)；而若出现了，，，中的一个则出现了一个B的threat.

• 由于落子点可能位于取出的位置（串）中的任一位置，故对于行和斜向操作共需取四次数。

• 而对于竖向，由于必定是按照从低到高的顺序落下的，因此如果落子后产生threat,则threat一定是落子点之上的一个点，因此仅需进行一次取数判定。

3. 实验结果

4. 总结