Spieltheorie mit Vorhersage

Question

Um zwei (deutsche) Professoren zu beeindrucken versuche ich die Spieltheorie zu verbessern.

AI in Computerspielen. Spieltheorie: Intelligenz ist eine gut ausgebildete bewährte Antwort auf eine Frage. Dies bedeutet, dass eine durchdachte Entscheidung ist, einen Akt zu wählen, der zu einem optimalen Ergebnis führt.

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

Zum Beispiel ein Roboter kämpft einen anderen Roboter. Dieser Roboter hat drei Möglichkeiten:

-move forward 
-hold position 
-move backward 

Das resultierende Programm ist recht einfach

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

Wir Pseudozufälligkeit verwenden.

Der Test für den Erfolg ist einfach hat er den Gegner zu elimieren. Die Roboter haben Schießen automatisch Waffen:

struct weapon 
{ 
    range 
    damage 
} 

struct life 
{ 
    hitpoints 
} 

Jetzt für einige Evolution.

Wir lassen 2 Roboter gegeneinander kämpfen und erinnern uns an die Zufallssaaten. Was ist das Zeichen für einen erfolgreichen Roboter?

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

Jetzt ist die Frage, wie wählen wir die richtige Strategie gegen einen Gegner? Wir gehen davon aus, dass wir für jede mögliche Seed-Strategie die optimale Anti-Strategie haben. Jetzt müssen wir nur noch die Zahlen des Gegners beobachten und seinen Startwert berechnen. Dann können wir die richtige Strategie wählen.

Für den Zufallsgenerator Knacken wir die manuelle Methode verwenden können: http://alumni.cs.ucr.edu/~jsun/random-number.pdf

oder Brute-Force: https://jazzy.id.au/2010/09/20/cracking_random_number_generators_part_1.html

Answer 1

Es auf dem Algorithmus hängt verwendet, um die (Pseudo-) Zufallszahlen zu erzeugen. Wenn der Pseudozufallszahlengenerator-Algorithmus bekannt ist, können Sie den Seed durch Ermitteln einer Anzahl von Zuständen (Roboterbewegungen) erraten. Das ist ähnlich wie Brute-Force-Erraten eines Passworts, das für die Verschlüsselung verwendet wird, da einige Verschlüsselungsalgorithmen als Stream-Chiffren bekannt sind und grundsätzlich (manchmal genau) ein One-Pad sind, das zum Verschleiern der Daten verwendet wird. Jetzt können wir sagen, dass Sie wissen, dass der verwendete Pseudozufallszahlengenerator ein einfacher verzögerter Fibonacci-Generator ist. Dann wissen Sie, dass sie jede Zahl erzeugen, indem Sie x (n) = x (n - 2) + x (n - 3)% 3 berechnen. Wenn Sie also drei verschiedene Roboterbewegungen beobachten, können Sie alle vorhersagen der Zukunft bewegt sich. Der Seed, ist die erste 3 Zahlen, die die Reihenfolge geben, die Sie beobachten. Nun sind die meisten Zufallszahlengeneratoren nicht so einfach, manche haben bis zu 1024 Bit lange Seeds, und es wäre für einen modernen Computer unmöglich, alle diese Möglichkeiten in einer brutalen Art und Weise zu durchlaufen. Also, was Sie tun müssten, ist herauszufinden, welcher PRNG-Algorithmus verwendet wird, alle möglichen anfänglichen Startwerte herauszufinden und einen Algorithmus zu entwickeln, um basierend auf ihren Aktionen den Startwert des gegnerischen Roboters zu bestimmen. Je nach Algorithmus gibt es Möglichkeiten, den Seed schneller zu erraten, als jeden einzelnen zu testen. Wenn es einen schnelleren Weg gibt, einen solchen Startwert zu erraten, bedeutet dies, dass der fragliche PRNG aus kryptographischen Anwendungen nicht geeignet ist, da dies bedeutet, dass Passwörter einfacher zu erraten sind.AES256 selbst hat eine Pause, aber es dauert immer noch theoretisch 2^111 Vermutungen (anstelle der Brute Force 2^256 Vermutungen), was bedeutet, dass es technisch gebrochen ist, aber 2^111 ist immer noch viel zu viele Operationen für moderne Computer Prozess in einem sinnvollen Zeitrahmen.

Wenn die PRNG verzögert wurde Fibonacci (die nie mehr verwendet wird, gebe ich nur ein einfaches Beispiel) und Sie beobachtet, dass der Roboter Option 0, dann, 1, dann 2 ... Sie würde dann wissen, dass die Das nächste, was der Roboter tun wird, ist ... 1, da 0 + 1% 3 = 1 ist. Sie könnten auch zurückverfolgen und herausfinden, was die Anfangswerte für diesen PRNG waren, der den Keim darstellt.