我正在为一个简单的棋盘游戏编写 AI 引擎。我现在的简单实现是遍历所有可选的棋盘状态,根据游戏规则和我的简单算法对每个棋盘状态进行加权,然后根据该分数选择最佳着法。
由于评分算法是完全无状态的,我想通过创建一些(所有?)棋盘配置的哈希表并从那里获取分数而不是即时计算来节省计算时间。
我的问题是:
1. 我的方法合乎逻辑吗? (如果没有,你能给我一些改进的建议吗?:))
2. 什么是最适合我需要的线程安全 STL 容器?我正在考虑使用 char 数组(板配置)作为键,将分数作为值。
3. 你能给我一些让我的人工智能成为 killer 的技巧吗? :)
编辑:更多信息:
棋盘是 10x10,有两名玩家,每人有 10 个棋子。规则很像跳棋。
最佳答案
是的,将评估板存储到称为转置表的哈希表中很常见。 STL 容器可以是 std::vector
。通常,您必须创建哈希函数(例如 zobrist hashing)。散列函数计算特定板的散列值。 hash_value modulo HASH_TABLE_SIZE
的结果将是 std::vector
的索引。
换位表条目可以保存的信息不仅仅是board-score和best-move,您还可以存储深度董事会被评估,如果评估分数(如果您正在进行 alpha-beta 搜索)是
- 准确
- 上限
- 或下界
我可以推荐 chessprogramming网站,在那里我学到了很多东西。查找术语 alpha-beta、转置表、zobrist 散列、迭代加深。还有很好的论文可以进一步阅读:
关于c++ - 棋盘游戏AI设计: choosing STL data container,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5431302/