博弈论算法：如何进行 [英] game theory algorithms: how to proceed

问题描述

举个例子：排列游戏（interviewstreet.com）。我想知道我怎么处理这种问题。

Take an example: Permutation Game(interviewstreet.com). I would like to know how do I proceed in such questions.

PS：请不要发布完整的算法（因为这将破坏的乐趣），短短三分

P.S.: Please don't post the full algorithm(as that would spoil the fun), just a few pointers.

推荐答案

我会设置一个小游戏，小N和随机排列，然后画一个完整的α-β树 ...

I would setup a small game with a small N and a random permutation and then draw a complete Alpha-Beta Tree...

http://en.wikipedia.org/wiki/Alpha-beta_pruning

所有可能的动作，然后工作自下而上作出最佳选择，每个玩家在每一个点。

of all possible moves, and then work bottom-up making the optimal choice for each player at each point.

然后从那里概括，一旦你看到的格局。

Then generalize from there once you see the pattern.

在博弈论的术语，你需要使用后向归纳法查找完美子博弈均衡

In game theory terminology you need to use Backward Induction to find the Subgame Perfect Equilibrium.

这篇关于博弈论算法：如何进行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！