国际象棋编程,Scala,JVM:动态调度的代价是多少？

Question

我的目标是写一个基本的国际象棋玩AI.它并不需要令人难以置信,但我希望它能够对某些熟悉游戏的人有一定程度的能力.

我有一个名为Piece的特征,它有抽象方法canMakeMove(m:Move,b:Board)和allMovesFrom(p:Position,b:Board).出于显而易见的原因,这些方法对于程序逻辑很重要,并且由具体类King,Queen,Pawn,Rook,Bishop和Knight实现.因此在其他地方,例如在确定特定板是否具有King的代码中,这些方法在类型为抽象类型Piece的值上调用,(piece canMakeMove(...,... ))所以调用的实际方法是在运行时通过动态调度确定的.

我想知道这对于国际象棋AI程序来说是否太昂贵了,而这个程序将不得不多次执行此代码.在网上浏览并阅读有关国际象棋编程的更多内容之后,我发现国际象棋棋盘的最常见表现形式不像我的Vector [Vector [Option [Piece]],而是一个可能使用的int矩阵('bit board')关于板上值的switch语句,以实现我目前依靠动态调度来实现的效果.这会阻止我的AI达到可行的性能水平吗？

Answer 1

我会在这个答案中建议你在编程中遇到一个常见的陷阱.我从同事那里学到了一个非常重要的智慧,它已经一次又一次证明了它的价值:

只有在问题发生时解决问题,而不是更快.

请记住,很长一段时间里都有国际象棋程序和国际象棋电脑.C64上甚至还有国际象棋程序,还有那些嵌入国际象棋棋盘的小型旅行棋牌计算机,因此您可以轻松携带它们.

这些系统的资源远远少于现在的计算机几个数量级.如果你有一个类似于在那些旧系统上运行的算法,并且该算法是在Scala中实现的,使用动态调度,宽大的向量而不是位数组等,它们仍然比它们在旧硬件上更快从过去的日子.

尽管如此,为国际象棋问题编写一个适度的搜索启发式算法对于单个开发人员来说是一项艰巨的任务.当面对一项巨大的任务时,一个人直观地倾向于寻找能够解决问题的第一个问题,希望这自然会导致你可以解决的下一个小问题,等等,最终领先彻底解决这个巨大的问题.分而治之.

但是,我个人的经验告诉我,这不是解决更大编程问题的好方法.通常,如果您遵循此路径,您最终会得到一个真正优化的棋盘表示,只消耗很少的内存,并尽可能地优化运行时间.

然后你就被困住了.你已经把所有精力投入到这个中,你真的为你的棋盘级别而感到骄傲,不知何故,你真的不满意你觉得没有更接近实际拥有一个有效的国际象棋AI.

这就是我在开始时提到的规则派上用场的地方.简而言之:不要优化.然而.如果有必要,您仍可以稍后进行优化.

相反,请执行以下操作:

• 制作代表棋盘的类或特征.
• 在开头留空 - 没有方法或成员.
• 对表示件,板位置,移动等的类型执行相同的操作.
• 然后,当您开始实施国际象棋AI时,请使用方法填写这些类型.但是只添加你真正需要的方法,并且只在你需要它们的时候,而不是任何单一的方法.
• 如果需要,可以在开始时使用特征,稍后可以生成更优化的特征版本.

通过这种方式,尽可能快地获得国际象棋AI的第一个版本,它可以做一些有趣的事情.您可以在此上下文中定义"有趣"的含义.

如果国际象棋AI的第一个版本很糟糕,并且每场比赛都输了,因为它做出了非常糟糕的决定,这没关系.它应该只有一件事:它应该做一些你至少发现有趣的东西.

然后,确定您对国际象棋AI的最大问题.想想如何解决它,提出一个只能解决一个问题的计划,以你能想象到的最简单的方式,即使你的程序员本能告诉你做一些更复杂的事情.抵制快速深入研究复杂性的冲动,因为您编写的最复杂的代码最终将成为您最大的问题,也是您代码库中最不灵活的部分.

解决方案的简短,简单,几乎是愚蠢的步骤.原型很多,在短时间内创建简单版本,并且只在需要时进行优化.

至于优化 - 这真的不是问题.例如,让我们说在开始时你认为定义这样的董事会职位是个好主意:

case class Position(x:Int, y:Int)

后来,你认为只使用一个整数元组来表示一个董事会职位是一个更好的选择.只需将您之前的定义替换为:

type Position = (Int, Int)

你去吧 进行更改,编译代码,编译错误将显示代码中需要适应的所有位置.重构这个并不需要很长时间.

即使在线下,您也可以决定,由于电路板上只有64个可能的位置,您可以轻松地用0到64之间的数字表示位置 - 为"板外"保留数字64.同样,这是一个简单的改变:

type Position = Byte

保存,编译,修复编译错误.不应超过15分钟.

在这个例子中,我想说明你不应该害怕以后优化,等待它们实际发生时才解决问题.这总是需要一些重构,但通常不值得一提.我倾向于认为这是"按摩代码".

当然我们知道初级程序员有时会写"意大利面条代码",以后很难重构.也许这就是为什么有一种对后期优化的恐惧,几乎每个开发人员都知道,以及早期优化的冲动.

对这种"意大利面条代码"唯一真正的解药是多次经历这个痛苦的过程.过了一段时间,您将对如何编写可以轻松优化和重构的代码形成非常好的直觉.这将匹配所有常见的编程智慧,如关注点分离,简短方法,封装等.在这一点上,我会推荐"清洁代码"这本书作为一个很好的指导方针.

更多提示:

• 将您的程序视为桥梁.你站在桥的一边,什么都没有开始.在远端,有你的愿景 - 一个体面的象棋AI.两端之间存在差距.你的计划将成为桥梁.不要把你所有的精力放在优化你放在桥上的第一块砖上.只有一块完美砖块的桥梁将无法容纳.首先构建一个原型桥 - 蹩脚,但它连接两端.当你拥有它时,一步一步地增强蹩脚的桥梁会更容易.
• 将所有功能抽象为特征和类.警惕代码重复 - 当你发现错误或需要进行重构时,重复的代码可能会成为破坏者.
• 只要代码简单并解决问题,不要害怕编写看起来不聪明的代码.代码读取得很好,看起来几乎就像算法的直观描述.
• 保持你的方法简短.一到六行.
• 确保您的代码不会过于嵌套 - 具有一点Scala经验的每个人都应该能够理解您的代码正在做什么.
• 花一些时间来为你的概念找到好名字是一件好事.也许甚至有一些标准来命名国际象棋AI的某些部分.先做一些研究是件好事.
• 在进行研究时,请查看是否有一些可用的Scala/Java库,用于解决问题的重要部分.您仍然可以在以后使用自己的实现替换库,但在开始时,使用其他人的知识可以帮助您快速创建第一个原型版本"bridge".一切有助于你迅速缩小"差距"的事情都很好.
• 不要将你的代码视为永恒,完美,不可改变的东西.也许你有志于在Scala中写出最好的棋盘表示.不要那样做.永恒,完美的代码无法轻易地重构或更改.可以轻松重构的代码是非常好的代码.重构代码是程序员的50%.
• 跳进自动化测试.对于Scala,使用scalatest库可能是一个不错的选择.使用像SBT这样的工具,它将在每个构建上运行所有自动化测试.如果您对所编写的类有某些假设,请将这些假设硬编码到自动化测试中.一开始会感觉有点愚蠢和多余.但是,当您的一个自动化测试第一次向您显示本来很难找到的错误的原因时,编写这些自动化测试的所有时间都将得到支付.
• 关于自动化测试的高级主题是代码覆盖.您可以使用生成覆盖率报告的工具,自动化测试涵盖了多少代码.根据我自己的经验,我会推荐jacoco4sbt.
• 最后,强制性引用:"优化是所有邪恶的根源." - 这个有很多智慧.

祝你好运,充满乐趣!