我正在教一个孩子编程，目前正在介绍一些基本的人工智能概念。首先，我们将实现一个井字游戏，它搜索整个游戏树并因此完美地进行游戏。一旦我们完成了，我想将相同的概念应用到一个有太多位置来评估每一个位置的游戏，因此我们需要实现一个启发式来评估中间位置。
我能想到的最好的东西是Dots and Boxes。它的好处是我可以将棋盘大小设置为任意大以阻止他搜索整棵树，并且我可以制作一个非常基本的评分函数，即我的盒子数量减去对手盒子的数量。不幸的是，这意味着在游戏开始的大部分时间里，每个位置都将被等同地评估为 0 分，因为在玩家真正开始制作盒子之前需要相当多的动作。
有人对游戏有更好的想法吗？（或者对点和框有更好的评分功能）？
另一种游戏选择可能是黑白棋又名奥赛罗。
一个幼稚的启发式方法是简单地计算每个有效移动获得的瓷砖数量并选择最大的。从那里你可以考虑棋盘位置并最小化对手的脆弱性。
您可以考虑的一款游戏是Connect Four。简单的游戏，规则简单，但比井字游戏更复杂。
跳棋会让你教几种方法。简单的前瞻，对最佳情况最坏情况决策的深度搜索，短期和长期收益之间的差异，以及他们在学习了你想教给他们的东西后可以继续研究的东西。
我个人认为最后一点是最关键的——人工智能开发中有一些自然的点，可以停下来，看看你能不能打败它，然后深入研究更深层次的人工智能机制。它可以让您的学生保持兴趣而不会感到非常沮丧，并且如果他们想继续该项目，可以让他们自己做更多的事情。
Rubik's Infinity很有趣，有点像 Connect Four 但又略有不同。评估职位非常容易。
前段时间我拼凑了一个 Perl 脚本来播放它，实际上不得不减少它看起来前面的移动次数，或者它每次都击败我，通常是用非常令人惊讶的策略。
黑白棋怎么样？它有一个非常好的启发式空间，基于件数、边缘件数和角件数。
五子棋是一款不错的、简单的游戏，而且很有趣，可以为它编写 AI。
曼卡拉怎么样？每回合只有 6 种可能的移动，并且很容易计算每个移动的结果，但重要的是要考虑对手的反应，并且游戏树会很快变大。
四个连成一条线够难，但也很容易想出一个简单的工作评估函数，例如，（从我最长的线到四个的距离 - 从我的对手最长的线到四个的距离）
我真的很喜欢连接四。使用 Minimax 算法非常容易编程。一个好的评估函数可以是：
eval_score = 0
for all possible rows/lines/diagonals of length 4 on the board:
if (#player_pieces = 0) // possible to connect four here?
if (#computer_pieces = 4)
eval_score = 10000
break for loop
else
eval_score = eval_score + #computer_pieces
(less pieces to go -> higher score)
end if
else if (#player_pieces = 4)
eval_score = -10000
break for loop
end if
end for
要改进程序，您可以添加：
用已经添加的随机线开始你的点和盒子游戏怎么样。这可以让你快速投入行动。只需要确保你没有用任何盒子开始游戏。
关于点和框的更好启发式方法，我建议查看游戏的在线策略指南。Google 上关于“点和框策略”的第一个结果非常有帮助。
知道如何使用链式法则将优秀的玩家与优秀的玩家区分开来。知道什么时候链式法则会对你不利，这是区分最佳玩家和优秀玩家的关键。
看看围棋。
更新：提到了黑白棋，它是 Go 的简化变体。可能是更好的选择。