标签: chess

最近我和一位非编码人员就国际象棋电脑的可能性进行了讨论.我不太懂理论,但想想我已经足够了解.

我认为不存在确定性的图灵机总是在国际象棋中获胜或陷入僵局.我认为,即使你搜索了玩家1/2移动的所有组合的整个空间,计算机在每一步决定的单一动作都是基于启发式的.基于启发式,它不一定能击败对手可以做的所有动作.

相反,我的朋友认为,如果计算机永远不会做出"错误"动作,那么计算机将永远胜出或结合(但是你定义了吗？).然而,作为一名采用CS的程序员,我知道即使你的好选择 - 给予明智的对手 - 也会迫使你最终做出"错误"的动作.即使你知道所有事情,你的下一步行动也是贪婪地匹配启发式.

大多数国际象棋计算机都试图将可能的最终游戏与正在进行的游戏相匹配,这本质上是一个动态的编程追溯.同样,有问题的最后阶段是可以避免的.

编辑:嗯......看起来我在这里乱了一些羽毛.非常好.

再考虑一下,似乎解决像国际象棋这样的有限游戏没有理论上的问题.我认为国际象棋比跳棋更复杂,因为胜利不一定是数字耗尽,而是通过配偶.我最初的断言可能是错误的,但我认为我已经指出了一些尚未得到令人满意的证明(正式).

我想我的思想实验是,无论何时树中的分支被采用,那么算法(或记忆路径)必须找到对手移动的任何可能分支的配偶路径(不进行交配).在讨论之后,我会购买比我们可能梦想的更多的内存,所有这些路径都可以找到.

我是竞争性编程的新手,我经常注意到,许多伟大的编码员在他们的代码中都有这四行(特别是那些涉及数组的代码):

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

这真正意味着什么,技术用于什么？

不是严格意义上的问题,更多的是谜题......

多年来,我参与了一些新员工的技术访谈.除了询问标准"你知道X技术"的问题之外,我还试图了解他们如何处理问题.通常情况下,我会在面试前一天通过电子邮件向他们发送问题,并希望他们在第二天提出解决方案.

通常结果会非常有趣 - 错误但有趣 - 如果他们能解释为什么采取特定的方法,那么这个人仍会得到我的建议.

所以我想我会向Stack Overflow的观众抛出我的一个问题.

问题:您可以想到最有效的方式来编码国际象棋游戏(或其子集)的状态是什么？也就是说,给定具有合法排列的棋盘的棋盘,编码该初始状态和游戏中的玩家所采取的所有后续合法移动.

答案不需要代码,只是您将使用的算法的描述.

编辑:正如其中一张海报所指出的,我没有考虑移动之间的时间间隔.随意作为一个可选的额外:)考虑到这一点:)

EDIT2:只是为了进一步说明......请记住,编码器/解码器是规则感知的.唯一真正需要存储的是玩家的选择 - 编码器/解码器可以假设其他任何东西.

EDIT3:在这里挑选一个胜利者很难:)很多很棒的答案!

我一直在为即将到来的编程竞赛练习,我偶然发现了一个我完全不知所措的问题.然而,我觉得这是一个我现在应该学习的概念,而不是交叉指责它永远不会出现.

基本上,它涉及棋盘上的骑士棋子.您将获得两个输入:起始位置和结束位置.目标是计算并打印骑士可以到达目标位置的最短路径.

我从来没有处理过最短路径的事情,我甚至不知道从哪里开始.我采用什么逻辑来解决这个问题？

PS如果它有任何相关性,他们希望你补充骑士的正常动作,同时允许它移动到由骑士可以做的(潜在的)八个动作所形成的方形的四个角,因为方形的中心是骑士的位置.

我试图了解如何以面向对象的方式进行设计和思考,并希望从社区获得有关此主题的一些反馈.以下是我希望以OO方式设计的国际象棋游戏的示例.这是一个非常广泛的设计,我在这个阶段的重点只是确定谁负责什么消息以及对象如何相互交互来模拟游戏.请指出是否有不良设计元素(高耦合,内聚力差等)以及如何改进它们.

国际象棋游戏有以下几类

• 板
• 播放机
• 片
• 广场
• ChessGame

董事会由正方形组成,因此董事会可以负责创建和管理Square对象.每件作品也都放在一个正方形上,因此每件作品都可以参考它所在的正方形.(这有意义吗？).然后每件作品都有责任将自己从一个方格移动到另一个方格.Player类拥有对他拥有的所有作品的引用,并且还负责创建它们(玩家应该创建Pieces吗？).播放器有一个方法takeTurn,后者又调用一个方法movePiece,它属于片段Class,它将片段的位置从当前位置改变到另一个位置.现在我对Board类必须负责的内容感到困惑.我认为需要确定游戏的当前状态并知道游戏何时结束.但当一件作品发生变化时 位置如何更新电路板？它应该保持一个单独的正方形数组,其中存在碎片并随着碎片的移动而得到更新吗？

此外,ChessGame最初创建棋盘和玩家对象,他们分别创建正方形和棋子并开始模拟.简而言之,这可能是ChessGame中的代码可能是什么样子

Player p1 =new Player();
Player p2 = new Player();

Board b = new Board();

while(b.isGameOver())
{
  p1.takeTurn(); // calls movePiece on the Piece object
  p2.takeTurn();

}

我不清楚董事会的状态将如何更新.应该是否有参考板？责任在哪里？谁持有什么参考？请帮助我提供您的输入并指出此设计中的问题.我故意不关注任何算法或游戏的进一步细节,因为我只对设计方面感兴趣.我希望这个社区可以提供有价值的见解.

我有兴趣编写一个国际象棋引擎(主要是作为一个学习练习),并且会对任何人们所知道的可能感兴趣或使用的资源感兴趣,任何真正的东西:论文,书籍,理论,教程,任何可能的东西有用.

我想知道实施国际象棋引擎有多难.是否已经有开源实现？

看起来你需要一个给定的板星座的评分函数,以及探索几个可能的未来板块星座的快速方法.探索所有可能的未来动作当然是不可能的,因此人们可以贪婪地遵循最有希望的动作,或使用模拟退火等近似技术来概率地跟踪可能的动作.

您是否认为这属于机器学习研究生项目的范围- 假设有一个学生可以使用的开源实现,那么基本的事情就像返回给定数字的下一个可能的动作一样？可能太难了？

让不同的团队在国际象棋引擎上工作然后让他们互相对抗是一个有趣的项目......

是否有任何Chess游戏API,纯粹用JavaScript编写？没有Flash!有谁知道国际象棋游戏中使用的算法(一般情况下)？

我想编写一个国际象棋引擎,学习如何做出好的动作并赢得其他玩家.我已经编写了国际象棋棋盘的代表和一个输出所有可能动作的函数.所以我只需要一个评估功能,它可以说明董事会的特定情况有多好.因此,我想使用人工神经网络,然后应该评估给定的位置.输出应该是一个数值.值越高,白人玩家的位置越好.

我的方法是建立一个由385个神经元构成的网络:棋盘上有六个独特的棋子和64个场.因此,对于每个场,我们采取6个神经元(每个1个).如果有白色片段,则输入值为1.如果有黑色片段,则值为-1.如果那个场上没有那种,那么值就是0.除此之外,玩家应该有1个神经元移动.如果是白色,则输入值为1,如果是黑色,则值为-1.

我认为神经网络的配置非常好.但缺少主要部分:如何将这种神经网络实现为编码语言(例如Delphi)？我认为每个神经元的权重在开始时应该是相同的.根据匹配的结果,然后应调整权重.但是怎么样？我想我应该让两个电脑玩家(都使用我的引擎)互相对抗.如果White获胜,Black会得到其权重不佳的反馈.

因此,如果您可以帮助我将神经网络实现为编码语言(最好的是Delphi,否则是伪代码)会很棒.提前致谢!

您将使用哪些数据结构来表示计算机国际象棋程序的棋盘？