点格棋求解算法 [英] Dots and boxes solving algorithm

问题描述

我目前工作的程序，其中输入由计算机自动生成一个 点格棋，而我们的产量是移动，我们会作出。我将同台竞技，另一名球员（他们的算法）。

I'm currently working on a "dots and boxes" program where the input is automatically generated by a computer, and our output is what move we'll make. I'll be competing against another player (their algorithm).

我重新presenting的点和箱板为Python中的矩阵。赢得比赛更是重中之重：算法的效率并不重要

I'm representing the dots and boxes board as a matrix in Python. Winning the game is top priority: algorithm efficiency is not that important.

有没有最好的，没有复杂的算法来自动计算出什么招，我们应该给出一个板？

Is there a best, not complex algorithm for automatically figuring out what move we should make, given a board?

P.S。 - 你不需要给我的code什么，如果你想...英文算法是完全可以接受的。

P.S. - You don't need to give me anything in code if you want...English algorithms are perfectly acceptable.

推荐答案

这个游戏的 零和游戏 ，所以我建议使用 <强>最小 - 最大算法 它。该算法采用深蓝色赢得卡斯帕罗夫在国际象棋。

This game is zero sum game, so I'd suggest using the min-max algorithm for it. This algorithm was used by deep-blue to win Kasparov in chess.

创建您的启发函数，其计算游戏的每一状态，并把它作为最小 - 最大算法的评价函数。

Create your heuristic function, which evaluates each state of the game, and use it as the evaluation function of min-max algorithm.

您还可以通过使用α-βprunning 提高最小 - 最大。

You can also improve min-max by using alpha-beta prunning.

最小 - 最大的想法是详尽地搜索所有可能的行动【达到一定的深度，通常，由于国家需要走过去是指数在深入数量]，而选择了最好的举措，假设你的oponent也将让他的最好的举动。

The idea of min-max is to exhaustively search all possible moves [up to certain depth usually, since the states you need to go over is exponential in the number of depth], and chose the best move, assuming your oponent is also going to make his best possible move.

P.S。

赢得比赛更是重中之重：算法的效率是不是   重要的。

Winning the game is top priority: algorithm efficiency is not that important.

他们是密切联系在一起的，因为更高效的算法是，你将能够检查可能的解决方案达到更好的深度和更好的机会，你将有机会赢得。需要注意的是无限的时候，你可以探索整个游戏树，并拿出从每场比赛状态的制胜战略。然而 - 探索整个游戏树可能是不现实的。

They are strongly connected together, since the more efficient your algorithm is, you will be able to check the possible solutions up to better depth, and the better chances you will have to win. Note that with unlimited time, you can explore the whole game tree and come up with a winning strategy from each game state. However - exploring the whole game-tree is probably unrealistic.

这篇关于点格棋求解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！