C++五子棋ab剪枝法 结构怎么设计。。
发布网友
发布时间：2022-04-29 12:21
共1个回答
热心网友
时间：2022-06-27 14:51
我也是初学，最近也要做一个类似的东西，略作探讨。
感觉博弈树这种东西节点用很多数据结构都能表示，没有什么特别要求。可以用这种链表型的数结构，也可以用只有指向第一个子节点和兄弟节点的结构，甚至只是使用几个队列或者数组就能表示。
博弈树不可能保存所有的节点，那样会把内存撑爆的。需要的只是第一步所有的节点和第二到第N步的一个（或一组）节点，不是构建整个树后评估，而是让 函数递归 来构建这种树形结构。
附件里是一个简化的版本，结构体有2个指向第一个子节点和兄弟节点的指针.
为了简便，产生下一轮和本轮其他步的走法可以直接产生，而且每个节点都有value值，这样可以简化评估函数。因为不同游戏产生下一步和评估函数都是不同的，这里只用一些简化写法代替。
#define MAX 100000000
#define MIN -100000000
#define LEAF 0
#define MAX_LEVEL 4
#define MAX_BRO_NUM 100
定义MAX节点，MIN节点,叶子节点，最大的层数MAX_LEVEL，最多兄弟节点数MAX_BRO_NUM，初始定义4层，每层100个节点，剪枝后大约剩几百万个节点（原本1亿个），
都不需要评估局势，还需要300毫秒左右。
每次都要在适当的时候释放内存，附件里只是一种写法。
{
int value;
int flag;
int level;
int brother_num;
struct Node* first_child;
struct Node* next_brother;
}Node;
我现在考虑用几个数组（或者队列）直接表示，有几层就需要几个数组，因为每层最多同时需要一个数组。
最后一层才是需要评估的，评估完之后就清空了，将得分传到上一层，然后根据上一层（倒数第二层）的下一个产生下一轮的走法填满刚才清空的最后一轮的数组，评估完再清空得分给上一层。........直到上一层填满就清空了将得分返回上上层......直到最上面的一层得到走法。。。
只是个人见解，仅供参考。如果不理解附件里的某些内容，欢迎追问。
