0

To impress two (german) professors i try to improve the game theory.

AI in Computergames. Game Theory:  Intelligence is a well educated proven Answer to an Question. This means a thoughtfull decision is choosing an act who leads to an optimal result.

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

For Example one robot is fighting another robot. This robot has 3 choices:

-move forward
-hold position
-move backward

The resulting Programm is pretty simple 

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

We are using pseudorandomness.

The test for success is simply did he elimate the opponent. The robots have automatically shooting weapons :

struct weapon 
{ 
  range 
  damage 
}

struct life
{  
  hitpoints
}

Now for some Evolution.

We let 2 robots fight each other and remember the randomseeds. What is the sign of a succesfull Roboter ? 

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

Now the question is how do we choose the right strategy against an opponent ?   We assume we have for every possible seed-strategy the optimal anti-strategy.   Now the only thing we have to do is to observe the numbers from the opponent and calculate his seed value.Then we could choose the right strategy.

For cracking the random generator we can use the manual method : http://alumni.cs.ucr.edu/~jsun/random-number.pdf

or the brute Force : https://jazzy.id.au/2010/09/20/cracking_random_number_generators_part_1.html

Nils Gramberg
  • 11
  • 4
  • 3
    If you know how an opponent robot is going to behave, there is a small chance that you can calculate the seed. But how are you going to determine how a robot would behave just by looking at it. There is no way to run this a-priori. Also, what makes you think that an opponent would always behave the same way? – Artjom B. Mar 17 '17 at 22:04
  • you only get the data at the actual time , like a hacker would get his data. and the opponent doesn't need to behave the same it is a randomnumber after all. – Nils Gramberg Mar 17 '17 at 22:15
  • oh i am reading http://alumni.cs.ucr.edu/~jsun/random-number.pdf and there the hacker needs to guess a word. – Nils Gramberg Mar 17 '17 at 22:29
  • well interesting read : https://jazzy.id.au/2010/09/20/cracking_random_number_generators_part_1.html – Nils Gramberg Mar 17 '17 at 22:41
  • 1
    I don't see a well-formalized game (how does elimination work?) and also not something to impress someone who understands the basics of game-theory. Reverse-engineering of PRNGs is also not really what Game-Theory is about and CS has other tools to forbid this (cryptoPRNGs). Normaly one categorizes the art of game and depending on your inner-workings of your game, reversing the seed is not even needed (compare with the NIM game; in many possible realizations of your game there is a simple strategy like in NIM possible). – sascha Mar 18 '17 at 01:56
  • i formalized the game , my goal is not writing a game about robots fighting , i did this , https://www.youtube.com/watch?v=w2a8BDpke1s , i want to write an AI Libraray – Nils Gramberg Mar 18 '17 at 11:22
  • you can call my strategy the GRAM strategy – Nils Gramberg Mar 18 '17 at 12:19
  • actually it is less a strategy more like a general chooses strategies that best suits the task – Nils Gramberg Mar 18 '17 at 12:23

1 Answers1

0

It depends on the algorithm used to generate the (pseudo) random numbers. If the pseudo random number generator algorithm is known, you can guess the seed by observing a number of states (robot moves). This is similar to brute force guessing a password, used for encryption, as, some encryption algorithms are known as stream ciphers, and are basically (sometimes exactly), a one time pad that is used to obfuscate the data. Now, lets say that you know the pseudorandom number generator used is a simple lagged fibonacci generator. Then, you know that they are generating each number by calculating x(n) = x(n - 2) + x(n - 3) % 3. Therefore, by observing 3 different robot moves, you will then be able to predict all of the future moves. The seed, is the first 3 numbers supplied that give the sequence you observe. Now, most random number generators are not this simple, some have up to 1024 bit length seeds, and would be impossible for a modern computer to cycle through all of those possibilities in a brute force manner. So basically, what you would need to do, is to find out what PRNG algorithm is used, find out all possible initial seed values, and devise an algorithm to determine the seed the opponent robot is using based upon their actions. Depending on the algorithm, there are ways of guessing the seed faster than testing each and every one. If there is a faster way of guessing such a seed, this means that the PRNG in question is not suitable from cryptographic applications, as it means passwords are easier guessed. AES256 itself has a break, but it still takes theoretically 2 ^ 111 guesses (instead of the brute force 2 ^256 guesses), which means it has been broken, technically, but 2 ^ 111 is still way too many operations for modern computers to process in a meaningful time frame.

if the PRNG was lagged fibonacci (which is never used anymore, I am just giving a simple example) and you observed that the robot did option 0, then, 1, then 2... you would then know that the next thing the robot will do is... 1, since 0 + 1 % 3 = 1. You could also backtrack, and figure out what the initial values were for this PRNG, which represents the seed.

Jacob Levinson
  • 169
  • 9