人智导大作业四子棋

四子棋实验报告

  • 本次实验中我采用了UCT算法

UCT算法

  • 在本次实验中我使用了UCT算法
    • 状态(state): 某一时刻的棋局
    • 初始状态即为得到getPoint()指令时的初始状态, 以此状态建立根节点
    • 节点: 博弈树中的一个节点为一个状态, 节点与状态一一对应
    • 终止节点: 即棋局的终止状态, 为某一方胜利的状态或平局状态的节点
    • 可扩展节点: 对于当前博弈树, 某节点不是终止节点且有未被扩展的子节点, 即在博弈树中可以扩展出叶子节点的当前叶子节点
    • 信心上限估计值: 根据公式计算出的每个节点的信心上限估计值
    • 最佳儿子节点: 当前节点的儿子节点中信心上限估计值最大的儿子节点
    • delta: 单次收益, 若我方赢, 我方节点收益为1, 对方为-1, 反之我方为-1, 对方为1, 平局双方均为0
    • Tree Policy: 每次走到最佳儿子节点, 直到走到一个可扩展节点
    • Expand: 此时我们处于一个可扩展节点, 给当前节点添加一个未访问过的儿子节点并走到这个节点
    • Default Policy: 从当前节点开始随机模拟棋局直到终止
    • Back Up: 从当前节点向上更新所有祖先的信心上限估计值

优化

棋盘压缩

  • 棋盘最大为12*12, 最小为9*9, 可以使用3个64位整数存储棋局中某一方的棋盘, 1为此处有此方落子, 0为此处没有此方落子, 总共使用6个64位整数。
  • 把三个64位整数看作一个大整数, 此时可以用位运算快速判断是否为终止节点, 具体的: 若S & (S >> 1) & (S >> 2) & (S >> 3)不为零即当前棋局可能为纵向四连子(一种可能的情况为跨不同列, 需要特殊判断), 横向和斜向同理
  • 我实现了两个版本, 一个是自己用unsigned long long实现, 一个是用bitset实现, 最终采取了bitset实现, 但是由于bitset的位运算或者.any()实现太慢, 位运算判断棋局效果不理想, 弃用位运算判断

内存池

  • 由于每次getPoint() 都会重新建立博弈树, 若每次都 new/delete 开销太大, 自己实现了一个简单的内存池以复用内存而不用每次new/delete

省略节点中存储的某些信息

  • 由于每次Tree Policy都是自上向下走到一个可扩展节点, 因此可以省略节点中存储的棋局信息, 改为用一个全局的棋局信息, 每次向下走时落子. 这样既省了大量的内存, 也节省了新建节点时复制棋盘的时间.

快速log 和 快速 sqrt

  • 我尝试使用一些求平方根的快速算法, 包括使用传说中的magic number, 但效果不理想, 弃用
  • 快速log, 尝试使用了 https://github.com/herumi/fmath 的快速log, 效果不错但需要CPU支持SSE2且需要打开编译开关, 弃用

结果

  • 最终这个AI取得了不错的结果, 在对战90 92 94 96 98 100这些AI时, 胜率稳定在80%以上

代码

https://github.com/NSBlink/connect-four

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注