Optimale Lösung zum Durchqueren von zufälligen Gittern auf einer Karte von 2 Spielern

Question

Betrachten Sie eine unendliche 2D-Karte. Wir haben zwei Spieler an den Punkten P1 und P2 an der Tafel. Sie müssen eine Reihe von Boxen auf der Platine G1, G2, G3 .... Gn durchlaufen.

Zu Beginn ist nur G1 bekannt. Die Koordinaten von G2 bis Gn sind nicht bekannt, nachdem das vorhergehende Kästchen durchlaufen wurde. Die Spieler können einzeln in einer der 8 möglichen Richtungen auf dem Brett in Einheitszeit bewegen. Wir müssen die minimale Zeit finden, um alle erforderlichen Boxen mit den beiden Spielern zu durchlaufen.

Die offensichtliche Lösung ist ein gieriger Ansatz, bei dem der Spieler, der näher an der Kiste ist, die überquert werden muss, sich ihm nähert. Dann berechnen wir den näheren Spieler für das nächste G wieder. Ich habe das Gefühl, dass es eine bessere Lösung für dieses Problem gibt, mit der ich mich im Moment nicht herumschlagen kann. Gibt es eine bessere Lösung?

Answer 1

Da das Problem nicht deterministisch ist, muss die Lösung heuristisch sein.

Der "Preis" bei jeder Runde ist die Anzahl der Züge in der Runde. Dies kann sein pRN1 oder PRN2 für die Anzahl von Zügen für player1 oder player2 jeweils wiederum N.

Der „Score“ bei jeder Umdrehung kann als die Wahrscheinlichkeit angenommen werden, dass eine bestimmte Anordnung (die Position des beide Spieler) nach den Zügen wird eine gute Vereinbarung für den Rest der Kurven sein.

Sie möchten eine Bewertungsfunktion verwenden, die sowohl den Preis als auch die Punktzahl berücksichtigt, um die Entscheidung zu treffen.

Das Problem ist, die einzige nützliche Scoring-Funktion ist eine, die eine Funktion der Entfernung zwischen den Spielern ist (je größer die Entfernung, desto größer ist die Chance, näher an den nächsten Kurven zu sein) und dies ist genau synchron mit der Mindestpreis. Jede Wahl, die die Spieler so weit wie möglich auseinander hält, ist notwendigerweise diejenige, die am billigsten ist.

Was das alles bedeutet, wenn der beste Algorithmus einfach ist, den nächsten Spieler zu bewegen, was der erste Instinkt ist, den Sie hatten.

Hätte das Board nicht wäre unendlich, könnten Sie eine bessere Scoring-Funktion erstellen, eine, die die Wahrscheinlichkeiten der nächsten Boxen berücksichtigt, die niedrigere Punktzahlen zu Vereinbarungen geben würde, die einen Spieler an den Rändern des Boards verlassen.

Answer 2

Ich denke, da das Board unendlich ist, sollten wir versuchen, so viel Fläche mit beiden Spielern wie möglich innerhalb von n Moves abzudecken (für jedes n). Auf diese Weise maximieren wir die Fülle an Feldern, die wir in n Bewegungen erreichen können.

Wer zum nächsten Feld nächsten ist:

So würde meine Strategie sein?

Sei dies P1.

Lassen Sie P1 zur Box gehen (kürzester Weg) und gehen Sie mit dem anderen Spieler P2 in die direkt entgegengesetzte Richtung. Auf diese Weise maximieren wir den Abstand zwischen den beiden Spielern, was die Überlappung des Bereichs minimiert, den sie in n Schritten erreichen können. Auf diese Weise maximieren wir die Reichweite des Bereichs, den die beiden Spieler in n Schritten für die nächste Box erreichen können.

Answer 3

Die beste Heuristik, die Sie finden können, wenn Sie den Spieler auswählen, der der nächsten Box am nächsten ist.

Erklärung: Immer wenn ein neues Ziel angezeigt wird, gibt es nur zwei Optionen: Spieler 1 oder Spieler 2 zum Ziel auf Kosten der Entfernung in Feldern bewegen. Wir bevorzugen auch eine Situation, in der die Spieler weit voneinander entfernt sind. Der extremste Fall wäre, dass beide Spieler auf demselben Feld sind, was genauso gut ist wie nur einen Spieler zu haben. Da das Spielfeld unendlich ist, ist es immer besser, weit auseinander zu sein.

Wenn das stimmt, dann sollten Sie sich fragen: Sollte ich wirklich entscheiden, dass der Spieler weiter vom Ziel entfernt ist und enden in einer Situation, in der die Spieler näher zusammen sind, als wenn ich es genommen hätte der andere Spieler?

Sicher nicht. In einem unendlichen Feld hilft die Auswahl des nächsten Spielers bei beiden, minimiert die aktuellen Kosten und verbessert die Situation für das nächste Ziel (weit voneinander entfernte Spieler).