Alpha-Beta-Schnitt bei gleichzeitigen Bewegungen?

7

Ich habe ein Spiel, für das ich ein Ai baue, bei dem 2 Spieler gleichzeitig Züge machen. In diesem Spiel gibt es genau einen Zug, bei dem, wenn beide es gleichzeitig schaffen, das Ergebnis anders ist als wenn sie es separat gemacht hätten (alle anderen Züge sind ziemlich unabhängig).

Wie auch immer, ich versuche einen guten Algorithmus zu finden, um darauf zu werfen. Minimax mit Alpha-Beta-Schnitt scheint ein guter Kandidat zu sein, wenn die Spieler abwechselnd Züge machen würden, aber nicht für gleichzeitige. Ich habe ein Papier (pdf) zu diesem Thema gefunden, aber es geht mir etwas über den Kopf - ich habe Probleme beim Lesen des Pseduocodes.

Kann jemand entweder helfen, diesen Ansatz zu klären, einen anderen Weg vorschlagen, um ein Alpha-Beta-Bereinigen für ein solches Spiel durchzuführen, oder einen besseren Algorithmus vorschlagen?

Fishtoaster
quelle

Antworten:

9

Die Sache ist, dass bei gleichzeitigen Zügen die optimale Strategie schwerer zu erraten ist, da Sie etwas berechnen müssen, das nicht immer offensichtlich gewinnt.

Schauen Sie sich das Nash-Gleichgewicht und das Gefangenendilemma an, wenn Sie sie noch nicht kennen. Dies ist die Art von Argumentation, die Sie jedes Mal benötigen, wenn Sie zwei gleichzeitige Züge in Betracht ziehen, anstatt einfach einen Zug zu wählen, der in Spielen mit nicht simultanen Zügen in eine gewinnbringende Konfiguration übergeht. Das Konzept der Dominanz ersetzt das Konzept des Gewinnens .

Der Algorithmus in Ihrer Referenz macht das, wenn Sie sich auf die Abbildungen 4 und 5 beziehen, aber versuchen Sie zuerst herauszufinden, was diese Abbildungen tun sollen, bevor Sie verstehen, wie sie es tun.

jmad
quelle