Im Frühherbst wurde der Wettbewerb um das Schreiben von Bots Mini AI Cup # 3 (auch bekannt als Mad Cars) abgeschlossen, bei dem die Teilnehmer auf Autos kämpfen mussten. Die Teilnehmer diskutierten viel darüber, was funktionieren wird und was nicht, Ideen wurden ausgedrückt und getestet, vom einfachen Wenn bis zum Training neuronaler Netze, aber die Jungs belegten die Spitzenplätze mit der sogenannten "Simulation". Versuchen wir zu verstehen, was es ist, vergleichen Sie die Lösungen für den 1., 3. und 4. Platz und diskutieren Sie über das Thema anderer möglicher Lösungen.

Haftungsausschluss

Der Artikel wurde in Zusammenarbeit mit Alexei Dichkovsky (Commandos) und Vladimir Kiselev (Valdemar) verfasst .

Für diejenigen, die nur über die Entscheidungen der Gewinner lesen möchten, empfehle ich Ihnen, sofort mit dem Punkt „Simulation“ zu beginnen.

Erklärung des Problems

Diesmal war die Mechanik der Welt dem Handyspiel Drive Ahead sehr ähnlich: Die Spieler erhielten ein Auto mit einem Knopf darauf; Die Aufgabe besteht darin, den Knopf des Feindes schneller zu drücken als er. Wenn in 600 Spiel-Ticks niemand gewinnt, sinkt die Karte in einen Müllhaufen, der auch einen Knopf drücken kann. Mit anderen Worten, Sie müssen Ihren Knopf vor Feinden, der Welt um Sie herum und Müllhaufen schützen (lebenswichtig, ja). Jeder Spieler erhielt 5 Leben, das Spiel dauerte 5 bis 9 Runden, während jemand sein Leben nicht beendete. Jede Runde wurde auf einer zufälligen Karte und Autos abgehalten, die für beide Teilnehmer gleich waren. Insgesamt gab es 6 verschiedene Karten und 3 Fahrzeugtypen - insgesamt 18 verschiedene Kombinationen.

Jede Runde ist in Zecken unterteilt. Ein Tick ist ein Zug, wie im Schach. Der einzige Unterschied ist, dass beide Spieler gleichzeitig gehen. Es gibt Wettbewerbe, bei denen sich jeder abwechselt, oder Sie können eine Aktion nur einmal alle paar Züge ausführen und Einheiten als Rahmen auswählen .
Jeder Tick für den Bot ist ein Zustand des Friedens und bietet die Möglichkeit, drei Aktionen auszuführen: , , . Diese Aktionen bringen das Auto in eine der Richtungen, und wenn es gleichzeitig die Räder der Erde nicht berührt, geben sie dem ganzen Körper eine kleine Drehung (ein bisschen Arcade-Physik). Nachdem beide Gegner eine Aktion ausgewählt haben, wird eine Simulation der Spielwelt gestartet, ein neuer Zustand betrachtet und an die Spieler gesendet. Wenn jemand auf eine Schaltfläche geklickt hat, endet die Runde und die nächste beginnt. Alles ist einfach, aber es gibt Nuancen.

Vollständigere Regeln finden Sie hier . Und sehen Sie die Finalspiele hier .

Allgemeine Lösungsbeschreibung

Die meisten Bot-Schreibwettbewerbe sind sehr ähnlich: Es gibt eine endliche Anzahl von Ticks (es gibt maximal 1.500 für eine Runde), es gibt eine endliche Anzahl von möglichen Aktionen, Sie müssen eine Abfolge von Aktionen auswählen, um besser als Ihre Gegner zu sein. Wenig später kehren wir zu dem zurück, was es bedeutet, besser zu sein, aber jetzt werden wir herausfinden, wie wir mit dem Hauptproblem umgehen sollen - einer Vielzahl von Optionen: Zu Beginn haben wir einen Anfangszustand, dann kann sich jede Maschine auf drei verschiedene Arten bewegen gibt uns 9 verschiedene Kombinationen für zwei Autos, durch die 1.500 Bewegung werden es 9 ^ 1.500 verschiedene Kombinationen sein ... Das ist etwas mehr als wir möchten, wenn wir planen, Zeit zu haben, um sie während der Existenz des Universums zu sortieren.

Hier kommen wir zu dem, was Simulation ist . Dies ist kein Algorithmus, sondern lediglich eine Neuerstellung der Spielregeln mit ausreichender oder vollständiger Genauigkeit, damit die Lösungen sortiert werden können. Natürlich werden wir nicht alle Lösungen durchgehen, sondern nur einen Teil davon. Hierfür wird ein Suchalgorithmus verwendet - im Spielstatusbaum suchen wir das Beste für uns. Es gibt viele Algorithmen (von Minimax bis MCTS), jeder hat seine eigenen Nuancen. Machen Sie sich am besten mit den Entscheidungen vertraut, die Teilnehmer früherer KI-Wettbewerbe getroffen haben. Dies liefert ein grundlegendes Verständnis darüber, unter welchen Bedingungen die Algorithmen funktionieren und unter welchen nicht. Dafür gibt es in einem speziellen Repository viele Links.

Bei der Auswahl eines Algorithmus sollten Sie Folgendes berücksichtigen:

• Zeitlimit für 1 Tick (hier habe ich mich dieses Jahr viel verrechnet, konnte aber auf dem 3. Platz bleiben);
• Anzahl der Spieler. Wenn beispielsweise drei Spieler vorhanden sind, ist es schwierig, Minimax zu verwenden.
• Simulationsgenauigkeit, as Dies kann die Wiederverwendung alter Berechnungen ermöglichen.
• "Verzweigung" des Zustandsbaums (ist es möglich, alle möglichen Zustände mindestens 10 Schritte voraus zu berechnen);
• gesunder Menschenverstand - schreiben Sie kein MCTS, wenn der Wettbewerb 4 Stunden dauert.

In diesem Wettbewerb ergab 1 Tick ungefähr 10-13 ms (2 Minuten für das gesamte Spiel). Während dieser Zeit musste der Bot die Daten lesen, eine Entscheidung treffen und einen Befehl zum Verschieben senden. Dies war genug, um ungefähr 500-1000 Bewegungen zu stimulieren. Iterieren Sie über alle Zustände. Der einfachste Suchalgorithmus sieht möglicherweise aus wie ein Vergleich von drei Bewegungsoptionen: "50 Ticks gehen nach links", "50 Ticks gehen nach rechts", "50 Ticks klicken auf Stopp". Und egal wie einfach es klingt, es ist nicht weit von der Entscheidung des Gewinners entfernt.

Weil Wir zählen nur 50 Züge voraus, was in den meisten Fällen erst am Ende des Spiels zählt. Dann brauchen wir eine Bewertungsfunktion , die sagt, wie gut und schlecht der Zustand der Welt für uns ist. Meistens basiert es auf Heuristiken und dem Verständnis, was für den Sieg wichtig ist. Zum Beispiel gab es beim russischen AI Cup-Wettbewerb 2014 Rennen, aber Sie könnten gewinnen, wenn Sie zuletzt ankommen und mehr Bonuspunkte erhalten. Daher sollte die Bewertungsfunktion das Sammeln von Punkten gleichzeitig mit der schnellen Bewegung entlang der Autobahn stimulieren. Die Punktzahl kann nur für den letzten Zustand der Simulation (nach 50 Ticks) oder als Summe der Schätzungen der Zwischenzustände berechnet werden. Oft „verblasst“ die Schätzung mit der Zeit, sodass früher auftretende Zustände stärker beeinflusst werden. Weil Wir können den Feind nicht sicher vorhersagen, dann sind zukünftige Optionen weniger wahrscheinlich, wir werden uns nicht stark auf sie verlassen. Außerdem beschleunigt diese Technik den Bot, um seine Aufgaben zu erledigen, und verschiebt nicht alles für später. Es ist jedoch anzumerken, dass der Bot im Interesse späterer Vorteile weniger Risiken eingeht.

Da wir den Zustand der Welt als Reaktion auf unsere Handlungen vorhersagen werden, müssen wir das Verhalten von Feinden irgendwie modellieren. Es gibt nichts Kompliziertes und es gibt einige gängige Optionen:

• Stub oder Heuristik
  Es wird eine einfache Verhaltenslogik geschrieben, bei der der Feind einfach nichts tut oder Aktionen basierend auf einfachen Heuristiken auswählt (Sie können beispielsweise Ihre ersten Versionen der Strategie verwenden oder einfach den vorherigen Zug des Gegners wiederholen).
• Verwenden Sie den gleichen Algorithmus wie für sich
  Zuerst versuchen wir, die besten Aktionen für den Feind zu finden (gegen unsere besten Aktionen aus dem letzten Zug oder gegen einen Stummel), und dann suchen wir nach der besten Aktion für uns selbst, indem wir das Verhalten verwenden, das der Feind gefunden hat. Hier wird der Bot versuchen, kniffligen Feinden zu widerstehen. Diese Logik funktioniert zu Beginn des Wettbewerbs nicht gut, weil Viele Bots sind immer noch sehr schwach und Ihre Entscheidung wird mit ihnen zu vorsichtig sein.
• Andere
  Der gleiche Minimax iteriert über alle Züge der Spieler gleichzeitig, und er benötigt einfach keine Heuristiken.

Wenn Sie alle oben genannten Schritte ausführen, erhalten Sie höchstwahrscheinlich einen sehr guten Bot, insbesondere wenn Sie eine gute Bewertungsfunktion übernehmen können. Aber wenn man seine Kämpfe durchschaut, kann man sehen, dass er sich in bestimmten Situationen seltsam verhält. Das Korrigieren der Bewertungsfunktion für diese Situationen kann schwierig sein oder es besteht ein großes Risiko, dass eine andere Logik verletzt wird. Hier kommen Krücken und Wenns zur Rettung. Ja, in den letzten Tagen des Wettbewerbs ging es oft darum, Krücken und Wenns zu schreiben, um die Fehler unter bestimmten Bedingungen zu beheben. Persönlich mag ich diesen Teil wirklich nicht, aber ich habe mehr als einmal bemerkt, dass es Krücken im Finale sind, die die Anordnung der Plätze in den Top Ten beeinflussen können, was bedeutet, dass ein ungeschriebenes Wenn Sie einen Preis kosten kann (mein Herz tut weh, wenn ich diese Worte schreibe, ich Ich liebe auch schöne Algorithmen und Lösungen.

F: Kann man überhaupt auf Simulation verzichten?
A: Ja, Sie können Lösungen für Heuristiken verwenden (Entscheidungsbäume, eine Reihe von Wenns usw.). Es gibt einen guten Artikel mit KI-Architekturen zur Heuristik.

F: Wie viel besser ist die Verwendung von Simulationen als heuristische Ansätze?
A: Es hängt alles von der Aufgabe ab. Zum Beispiel könnten hier einige Kombinationen von Karten und Autos mit Wenns fest codiert werden und immer gewinnen (oder ziehen). Oft findet die Simulation jedoch Lösungen, die für sich selbst schwer zu denken oder Heuristiken schwer zu implementieren sind. Wenn Sie in diesem Wettbewerb ein anderes Auto umdrehen, setzen die Lösungen in den Simulationen das Rad auf das Rad des Feindes, wodurch die Flagge "in der Luft" ausgeschaltet wird. Dies bedeutet, dass der Feind die Drehung des Körpers nicht anwenden und die Räder nicht wieder drehen kann. Aber die Entscheidung dachte nicht über die Bedeutung nach, sondern fand nur Optionen, bei denen der Feind schneller auf das Dach fallen und seinen Knopf drücken würde.

F: Neuronale Netze und RL?
A: Egal wie beliebt dies ist, in Bot-Wettbewerben funktionieren solche Lösungen selten gut. Obwohl neuronale Netze keine Simulation benötigen, weil Sie können einfach eine Aktion ausführen, die auf den Eingabeparametern des aktuellen Status basiert. Sie müssen noch etwas lernen, und dafür müssen sie häufig einen Simulator schreiben, um Spiele zu Tausenden lokal zu steuern. Persönlich glaube ich, dass sie Potenzial haben. Vielleicht können sie einen Teil des Problems lösen oder es unter Bedingungen sehr begrenzter Reaktionszeit verwenden.

Hinweis
In Bezug auf die endliche Anzahl möglicher Aktionen sollte klargestellt werden, dass es manchmal erlaubt ist, einige Parameter "reibungslos" anzupassen. Zum Beispiel nicht nur vorwärts fahren, sondern mit einem gewissen Prozentsatz an Leistung. In diesem Fall kann die „Endlichkeit“ der Anzahl der Schlussfolgerungen leicht erreicht werden, indem einfach mehrere Werte verwendet werden, beispielsweise 0%, 25%, 50%, 75% und 100%. Meistens reichen nur zwei aus: "Voll ein" und "Voll aus".

Simulation

In diesem Wettbewerb haben wir die fertige Chipmunk-Physik- Engine verwendet. Die Erwartungen der Organisatoren waren, dass er alt und erprobt ist und viele Wrapper hat, damit jeder es in seine Entscheidung einbeziehen kann ...

In der harten Realität erzeugte der Motor jedes Mal andere Werte, was es schwierig machte, ihn neu zu starten, um die Optionen für Bewegungen zu berechnen. Das Problem wurde „frontal“ gelöst - ein Speicherzuweiser wurde in C geschrieben und ein Speicher mit dem Zustand der Welt wurde vollständig kopiert. Ein solcher Allokator machte der Fähigkeit ein Ende, Lösungen in anderen Sprachen als C ++ zu schreiben (tatsächlich war es möglich, aber sehr arbeitsintensiv und ein Allokator müsste noch in C geschrieben werden). Darüber hinaus wurde die Genauigkeit der Vorhersage durch die Reihenfolge des Hinzufügens von Elementen zur Spielwelt beeinflusst, was eine sehr genaue Kopie des Codes erforderte, den die Organisatoren zur Berechnung der Spiele verwendeten. Aber er war schon in Python. Das letzte Highlight im Sarg anderer Programmiersprachen war, dass die Engine alt ist und viele Optimierungen enthält, die während des Wettbewerbs nicht genau wiederhergestellt werden können, um Ihre eigene Version der Physiksimulation zu erhalten.

Infolgedessen wurde der Motor, der allen Teilnehmern gleiche Bedingungen für die Simulation von Bewegungen bieten sollte, zum schwierigsten Hindernis. Über 10 Personen konnten es überwinden. Die ersten 7 Plätze in der Rangliste wurden ausschließlich von den Jungs belegt, die die genaue Simulation durchgeführt haben, was als Beweis für ihre Bedeutung in solchen Wettbewerben dienen kann.

Mit Ausnahme einiger Teilnehmer, die in der Lage waren, in das Innere des Chipmunks einzudringen und dessen Kopierzustand zu optimieren, hatte der Rest eine Simulation mit ungefähr derselben Leistung (was die Konkurrenz etwas interessanter machte, weil Sie wissen, dass der Kampf um den Entscheidungsalgorithmus geht, nicht "Wer zählt die Züge mehr").

Algorithmus zum Suchen und Vorhersagen eines Gegners

Ab diesem Punkt beginnt eine separate Beschreibung der Lösungen. Algorithmen werden im Namen des Autors beschrieben.

Vladimir Kiselev (Valdemar) 4. Platz

Eine zufällige Suche (Monte Carlo) wurde verwendet, um den Lösungsraum zu durchsuchen. Der Algorithmus ist wie folgt:

1. Wir initialisieren das Genom - eine Folge von Aktionen (links, rechts, Stopp) für 60 Ticks - zufällige Daten.
2. Nehmen Sie das beste gefundene Genom
3. Ändern Sie zufällig eine der Aktionen
4. Mit der Bewertungsfunktion erhalten wir eine Zahl - ein Indikator dafür, wie gut das neue Genom ist
5. Wenn Sie eine bessere Lösung erhalten, aktualisieren Sie die beste Lösung.
6. Wiederholen Sie erneut ab Schritt 2

Mein Simulator hat in 1 Sekunde ~ 100.000 Simulationen der Welt erstellt. Wenn man bedenkt, dass es durchschnittlich ~ 12 ms pro Tick gibt, erhalten wir 1200 Aktionen pro Tick. Das heißt, in 1 Tick schaffen wir es ungefähr 20 Mal, den gesamten Zyklus zu durchlaufen.

Um die optimale Lösung zu finden, reichte diese Anzahl von Iterationen eindeutig nicht aus. Daher wurde die Idee mit "Stretching" -Aktionen verwirklicht: Anstelle des Genoms von 60 Zügen werden wir mit einer Kette von 12 "gestreckten" Zügen arbeiten - wir glauben, dass jede Aktion 5 Ticks hintereinander dauert.
Plus: Um die Qualität der Mutationen zu verbessern, indem die Länge des Genoms verringert wird, kann die Simulation auch alle 5 Ticks ausgeführt werden und 100 statt 20 Genome überprüfen (um Zeitverzögerungen zu vermeiden, habe ich schließlich bei 70 aufgehört).
Weniger: Dehnungsvorgänge können zu nicht optimalen Lösungen führen (z. B. Schwingen am Stoßfänger anstelle eines stabilen Racks).

Es sind die Techniken zu beachten, die die Qualität des Algorithmus erheblich verbessert haben:

• Wir führen eine zufällige Initialisierung nur beim ersten Tick durch, den Rest der Zeit verwenden wir die beste Lösung, die mit einer Verschiebung von 1 Zug gefunden wurde (die Aktion beim 2. Tick wird zum 1. verschoben usw. Eine zufällige Aktion wird zum Ende hinzugefügt). Dies verbessert die Qualität der Suche erheblich, da der Algorithmus sonst "vergisst", was er beim letzten Tick tun würde, und sinnlose Rucke in verschiedene Richtungen macht.
• Zu Beginn des Kurses nehmen wir intensivere Änderungen vor (wir ändern das Genom zwei- oder dreimal anstelle von einem), in der Hoffnung, das lokale Maximum zu überschreiten (Ähnlichkeit der Temperatur bei der Methode zur Simulation des Annealing).
  Die Intensität wurde manuell ausgewählt: Die ersten 30 Iterationen ergeben 3 Mutationen, die nächsten 10 mal 2 und dann 1.
• Sehr wichtig ist die Vorhersage feindlicher Aktionen. Zum Nachteil der Zeit für die Suche nach unserer eigenen Lösung starten wir eine zufällige Suche von der Seite des Gegners mit 20 Iterationen und dann 50 für uns selbst, wobei wir Informationen über die optimalen Bewegungen des Gegners verwenden.
  Die beste Entscheidung des Gegners wird auch im nächsten Zug mit einem Versatz wiederverwendet. Gleichzeitig wird bei der Suche nach einer Lösung für den Feind das Genom aus dem letzten Zug als meine beabsichtigte Aktion verwendet.

Während des Wettbewerbs setzte er aktiv Tools für die lokale Entwicklung ein, die es ermöglichten, schnell Fehler zu finden und sich auf die Schwachstellen der Strategie zu konzentrieren:

• lokale Arena - Start vieler Spiele gegen die vorherige Version;
• Visualizer für das Debug-Verhalten;
• Ein Skript zum Sammeln von Statistiken über Übereinstimmungen auf der Website - ermöglicht es Ihnen zu verstehen, auf welchen Karten und Maschinen die Niederlage am häufigsten auftritt.

Mortido:
Das Zählen alle 5 Ticks sieht riskant aus, besonders wenn sich der Feind von den von Ihnen vorhergesagten Optionen entfernt. Andererseits ist in dieser Spielwelt für 5 Ticks nicht viel passiert.
Außerdem habe ich bei meiner Entscheidung trotzdem bei jedem Tick zufällige Kombinationen hinzugefügt, aber ich werde definitiv nicht sagen, wie sich dies auf die Entscheidung ausgewirkt hat.

Kommandos:
Das Ändern einiger Aktionen mit einer solchen Anzahl von Simulationen sieht nicht sehr aussagekräftig aus, da nur sehr wenige Änderungen in einer Aktion auftreten. Aber wenn Sie eine Aktion auf 5 Ticks Bedeutung ausdehnen, scheint es mehr zu werden.
Die Idee selbst gefällt mir auch nicht - wir nehmen das beste Set und versuchen, es irgendwo am Anfang zu bearbeiten. Es erscheint unlogisch, dass das Ändern der ersten Zecken die nachfolgenden zumindest relativ angemessen macht.

Alexander Kiselev (Mortido) 3. Platz

Mit Artikeln von Gewinnern anderer Wettbewerbe bewaffnet, entschied ich mich für den genetischen Algorithmus. Es stellte sich jedoch heraus, dass es sich um eine zufällige Suche oder sogar eine Nachahmung des Temperns handelte, aber dazu später mehr.

Wir codieren die Lösung mit einem Array von 40 Zahlen, wobei -1, 0 und 1 den Bewegungen , und .

Zu Beginn jeder Runde berechnete ich, wie viel Zeit ich bereits für das gesamte Spiel aufgewendet hatte, zählte ein neues Zeitlimit basierend darauf, wie viele Runden noch vorhanden sein würden, und jede Runde, die ich annahm, war 1200 Ticks. T.O. Anfangs habe ich versucht, nicht mehr als 11 ms pro Runde zu verbringen, aber ich könnte am Ende ein bisschen „herumlaufen“, wenn die vorherigen Runden schneller als 1200 Ticks wären.

Valdemar:
Interessanterweise hat dieser Chip das Spiel für mich verschlechtert. Es stellte sich heraus, dass es immer besser ist, zuerst 20 bis 30 ms als 11 und am Ende 60 ms zu verbringen

Ein Drittel dieser Zeit suchte ich nach dem besten Zug des Feindes, der Rest ging in die Berechnung meiner eigenen Entscheidung. Bei der Suche nach einem Zug für den Feind wurde mein Verhalten als das Beste aus dem letzten Zug modelliert, verschoben um 1 Tick. Das heißt, als ob ich weiterhin nach dem Plan handeln würde, der im letzten Tick aufgestellt wurde, und er versucht, mir zu widerstehen.

Die Suche nach der Lösung selbst war für sich und den Gegner gleich:

1. Wir treffen die Entscheidung aus dem letzten Zug und verschieben sie um 1 Zug (was wir bereits getan haben).
2. Wir beweisen der Population zufälliger Lösungen, bis wir alles gefüllt haben
3. Wir simulieren alle Entscheidungen und stellen die Fitness mithilfe der Bewertungsfunktion ein. Wir erinnern uns am besten.
4. Während es Zeit für Berechnungen gibt
   
   1. Tipp, fügen Sie der Population immer 1 Mutation der derzeit besten Lösung hinzu. Denken Sie daran, wenn es besser ist
   2. Solange es einen Platz in der neuen Bevölkerung gibt und die Zeit für Berechnungen nicht überschritten wurde (Sie können auf den Boden einer bevölkerten Bevölkerung gehen)
      
      1. Wir nehmen zwei verschiedene Personen und gehen mit der besten Fitness - Mutter
      2. Wir nehmen zwei verschiedene Personen und gehen mit der besten Fitness - Papa (sollte nicht mit Mama zusammenfallen)
      3. Überquere sie
      4. Mutieren, wenn RND <
      5. Wir simulieren eine Lösung und erinnern uns daran, wenn es die beste ist

Infolgedessen geben wir die Reihenfolge der Aktionen zurück, die als optimal angesehen wird. Der erste Zug wird als Bot-Aktion gesendet. Leider hatte mein Plan einen gravierenden Nachteil Die Anzahl der Simulationen, die mit einem Tick durchgeführt werden können, war sehr gering (auch aufgrund der langen Bewertungsfunktion). Auf dem Wettkampfserver wurden 4 Punkte nur einmal ausgeführt, und für den Feind wurden sie überhaupt nicht ausgeführt. Dies machte den Algorithmus eher zu einer zufälligen Suche oder einem simulierten Tempern (da wir es geschafft haben, die Lösung 1 Mal vom letzten Zug an zu mutieren). Es war schon zu spät, um etwas zu ändern, und wir konnten den 3. Platz halten.

Es ist wichtig, die Algorithmen zum Kreuzen, Mutieren und Erzeugen anfänglicher Zufallslösungen zu implementieren, da Es hängt davon ab, welche Entscheidungen getestet werden, und eine vollständige zufällige Entscheidung ist nicht so gut, wie es auf den ersten Blick erscheinen mag (es wird funktionieren, aber es werden viel mehr Optionen benötigt).

In der endgültigen Version wurden zufällige Entscheidungen in Segmenten generiert, die "ruckelnde" Lösungen an einer Stelle ausschlossen:

1. Zufälliges Team ausgewählt
2. Für die gesamte Länge der Lösung (40 Züge)
   
   1. Wir schreiben den aktuellen Befehl in die Zelle
   2. Mit einer Wahrscheinlichkeit von 10% ändern wir das aktuelle Team in eine zufällige

Nach einer ähnlichen Technologie trat auch eine Mutation auf - ein zufälliges Segment der Lösung wurde durch einen zufälligen Befehl ersetzt. Die Überquerung erfolgte durch Auswahl des Punktes, bis zu dem die Entscheidung von einem Elternteil und danach vom 2. getroffen wurde.

Mir hat gefallen, dass wir die uns zur Verfügung stehende Zeit nutzen, um die beste Lösung zu finden. Es ist keine große Sache, wenn die Lösung nicht die beste ist - wir können sie beim nächsten Tick verbessern, weil Die Optimierung stellt sich als zeitlich "verschwommen" heraus. , . , - , . ,

Valdemar:
1 , , .

Commandos:
— - .
— , . , … , . " ”. -.

(Commandos) 1

( ), n m . 3^2=9 . m + n 40 .

:

 |----------- n  -----------|---------- m  --------| |   ...   |   ...   | 

: , , . ( ).

n m , . , .

:

1. , ( , ):
   
   • , , , .
   • , , . . . , , , .
   • . ; ( ).
2. n m . , .1, , . - ( ) , — , ;
3. . , — . , ( ).

Valdemar:
, 2 . . , .

mortido:
Wow! , . . , 2 , 40-60 . , 3 .
n + m == const ?

. n + m != const , . , . - .

(Valdemar) 4

, . , ( , , ..) [0..1].
. : , .
, , : , .

, :

• — 70 180 ( : ).
  , .
• 0..500
• — [2pi, pi/4] [0, 1]
• — , ( ), ( , , )
• — , , , .
  , , .
• — . .
• Y — .

, 2 , .

.

:

• “” ,
• “ ” , , .

mortido:
, .. , .

Commandos:
, . -

(mortido) 3

, chipmunk. . , , , , . .

3 .

, ( , , ):

• . , , ( , );
• , — , ; , 1 ;
• ;
• ( , );
• ( “+”, “-”);
  - ( “+”, “-”); , , , ;
  30 , , ( );
• , .

, , (, , )

Valdemar:
. , “ , , ” , ( ..) .

, , . .

Commandos:
, , “”… ? , “” .

(Commandos) 1

SquaredWheelsBuggy , .. , . Buggy , , ( /).
Kurz:

1. ;
2. ; — , , 1 0; .. ;
3. . ; 10 ( );
4. ( , );
5. (, );
6. — - , ;
7. / ; , — ; .

1-5 , . 2 “ ”.

Valdemar:
, . , .

mortido:
, 10 .

IF'

(Valdemar) 4

, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .

:

• . , .
• — , .
• . “ ” .
  , , .
  , , .

, : . , , if' .

mortido:
, . .

Commandos:
if'. , , … , , .

(mortido) 3

- .

3 . . . “”, . , , .

, “” . . , , , - . . , , .. .

, , , , , . … . - — , ( , ).

Valdemar:
, . . “” , if'. , — .

, + . , .

Commandos:
… , - — , , . , , .

(Commandos) 1

. (, , ). ( ) /.

pill carcass map , , ( ). island map, , .

island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .

(Pill map, Bus) , ( / 100% ).

pill hubble map. , ( ), . .

— , ...

, . , . ( ).

Valdemar:
, — . , .

mortido:
, “” .

Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .

mortido:
: , … , , ( ). , 3 , , … .

Commandos:
- , . , , , . … . — , .
— ++. . , . 1 -.

Also

, . , . , , .

Mail.Ru Group .

Bonus

Valdemar
mortido