Skip to content

kpol-lgx/decision-trees

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

2022-fall-AI-Introduction-last-HW-1

初步思考

  • step1: 尝试扩展节点并决策
  • step2: 尝试建立评估函数

每个棋局用一个 01 串表示:

  • 如果是 10 / 01 表示这里没有棋子
  • 如果是 00 表示这里是我方棋子
  • 如果是 11 表示这里是敌方棋子

每一行首尾相连构成一个长串

限定棋盘是 10 * 10 大小

那么假设使用 11 填满整个棋盘,最大值是 $2^{200} > 2^{64} > 2^{32}$

不可能使用 int 或者 long long 表示

假设博弈树有 k 层,那么最多需要检索的叶子节点有,

$$ \prod_{i = 100-k}^{100} i $$

这样的空间大小是不可接受的,必须剪枝

不过如果是深度优先遍历,实际上可以每次只保存一种棋局即可

所以如何扩展节点才是重要问题

扩展节点

使用递归的思想

About

Xidian2022Fall-AI-BHW course work

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages