带预测的博弈论

为了打动两位德国教授，我试图改进博弈论。带预测的博弈论

AI in Computergames。博弈论：智力是一个受过良好教育的问题。这意味着一个深思熟虑的决定是选择一个导致最佳结果的行为。

Question -> Resolution -> Answer -> Test (Check)

例如，一个机器人正在与另一个机器人作战。这个机器人有3种选择：

-move forward 
-hold position 
-move backward

产生的PROGRAMM很简单

randomseed = initvalue; 
while (one_is_alive) 
{ 
    choice = randomselect(options,probability); 
    do_choice(roboter); 
}

我们正在使用伪随机性。

成功的考验只是他对对手的吸引力。的机器人可以自动射击武器：

struct weapon 
{ 
    range 
    damage 
} 

struct life 
{ 
    hitpoints 
}

现在对于一些演变。

我们让2个机器人相互对抗，记住随机种子。成功的机器人的标志是什么？

struct { 
    ownrandomseed; 
    list_of_opponentrandomseed; // the array of the beaten opponents. 
    }

现在的问题是我们如何选择正确的策略对付对手？我们假设我们已经为每种可能的种子策略提供了最佳的反策略。现在我们唯一要做的就是观察对手的数字并计算他的种子价值。然后我们可以选择正确的策略。

对于裂化随机发生器我们可以使用手动方法： http://alumni.cs.ucr.edu/~jsun/random-number.pdf

或蛮力： https://jazzy.id.au/2010/09/20/cracking_random_number_generators_part_1.html

来源

2017-03-17 Nils Gramberg

如果您知道对手机器人将如何行动，那么您可以计算种子的几率很小。但是，你将如何确定一个机器人如何看待它。没有办法先运行这个事件。另外，是什么让你觉得对手总是会以同样的方式表现？ –

您只能在实际时间获取数据，就像黑客会获取他的数据一样。而且对手不需要表现得一模一样，它毕竟是一个随机数。 –

哦，我正在阅读http://alumni.cs.ucr.edu/~jsun/random-number.pdf，那里的黑客需要猜测一个字。 –

这取决于用于产生（伪）的算法的随机数。如果已知伪随机数生成器算法，则可以通过观察多个状态（机器人移动）来猜测种子。这与蛮力猜测用于加密的密码类似，因为某些加密算法被称为流密码，并且基本上（有时正好），这是一种用于混淆数据的一次性填充。现在，让我们说你知道使用的伪随机数发生器是一个简单的滞后斐波那契发生器。然后，你知道他们通过计算x（n）= x（n-2）+ x（n-3）％3来生成每个数字。因此，通过观察3种不同的机器人移动，你将能够预测所有未来的举动。种子，是提供给你观察序列的前3个数字。现在，大多数随机数发生器并非如此简单，有些具有多达1024位长度的种子，并且现代计算机不可能以强力方式循环所有这些可能性。所以基本上，你需要做的是找出PRNG算法的用途，找出所有可能的初始种子值，并设计一个算法来确定对手机器人正在使用的种子。根据算法的不同，有很多方法可以比测试每一种方法更快地猜测种子。如果有更快的方式来猜测这样的种子，这意味着PRNG不适合加密应用，因为这意味着密码更容易被猜出。AES256本身有一个突破，但它在理论上仍然需要2^111的猜测（而不是蛮力2^256猜测），这意味着它在技术上已经被打破了，但是现代计算机的2^111操作仍然太多在有意义的时间框架内处理。

如果PRNG被滞后斐波那契（这是从来没有用过，我只是举一个简单的例子），你观察到机器人做0选项，然后，1，然后2 ...然后你会知道机器人会做的下一件事是...... 1，因为0 + 1％3 = 1。你也可以回溯，并找出代表种子的PRNG的初始值。

来源

2017-03-17 22:18:04

thx我发现了一种算法，通过两个连续的“旧”随机发生器的蛮力获得种子 –

抱歉，我missclicked：我想要说对我来说数学太高了:( –

thx我发现了一个蛮力的算法，强制使用2个键和65000个步长的“普通”随机发生器，现在我得到了这个公式，但递归很容易吗？ –

带预测的博弈论

回答

相关问题