25 ms Seeschlacht

Vorwort


Vor ein paar Monaten habe ich beschlossen, Python zu lernen. Als eine der Testaufgaben musste das Spiel „Sea Battle“ geschrieben werden. Dann habe ich diese Aufgabe nicht gemacht, aber mir kam die Idee, "Sea Battle" zu schreiben, wo zwei Computer miteinander spielen. Dieser Gedanke ließ mich nicht los und ich entschied mich zu trauen. Das Ergebnis wird Ihrem Gericht vorgelegt. Für konstruktive Kritik wäre ich dankbar.

Allgemeines Konzept der aktuellen Implementierung


Tatsächlich läuft das ganze Spiel darauf hinaus, dass zwei Instanzen der Spielerklasse sich gegenseitig nach den Koordinaten der Schiffe fragen und je nach Antwort ihre Zugstrategie aufbauen.

Die Strategie zum Anordnen von Schiffen lautet wie folgt: 2-3-4 deckbasierte Schiffe werden an den Rändern der Karte platziert (2 Zellen), 1 Deck in der Mitte (6x6 Quadrat).

Bild

Die Strategie der Züge, wie im Spiel zwischen Menschen: Der erste Zug ist zufällig, wenn Sie schlagen, dann arbeiten Sie sich durch 4 Zellen herum und wenn Sie erneut schlagen, dann arbeiten Sie sich durch zwei Zellen, die sich bereits auf der Linie befinden (zwei, weil die maximale Schiffslänge 4 Zellen beträgt). 2 bereits getroffen, dann sind maximal 2 weitere Zellen vorhanden).

In dem ArtikelAuf Wikipedia ist alles ausreichend detailliert beschrieben, so dass ich nicht viel auf die Spielelogik eingehen werde, zumal jeder bereits grob versteht, worüber diskutiert wird. Ich habe nur solche Unterschiede: Wertung für jeden Zug, Nummerierung der Zellen von 0 bis 9.

Das Spiel verwendet drei Klassen: Spiel, Spieler, Schiff. Die Verwendung der Game-Klasse in der aktuellen Implementierung ist redundant, da nur eine Instanz verwendet wird. Dies ist jedoch eine Grundlage für die Zukunft (siehe die Liste der Verbesserungen am Ende des Artikels).

Das Spiel ist für die allgemeine Spiellogik verantwortlich. Der Spieler - für die Strategie der Bewegungen - speichert den aktuellen Zustand der Schiffe und ihre Koordinaten.

Link Projekt in GitHub.

Die Hauptschwierigkeiten, die bei der Entwicklung auftraten


1. Design . Schreiben mit Klassen oder Funktionen? Welche Klasse soll verwendet werden?
Das Hauptproblem beim Design war die Verfolgung verschiedener Bedingungen im Spiel. Zum Beispiel, wer läuft jetzt, in welchem ​​Zustand ist das Schiff (getroffen, getötet), hat das Spiel beendet, wer hat gewonnen usw.

2. Logik / Algorithmen . Wie ordne ich die Schiffe gemäß der Strategie an, wie wähle ich die Koordinaten für den Umzug?

Übersicht der interessantesten Teile des Codes


return_shoot_state - bestimmt die weitere Strategie in Abhängigkeit von den Ergebnissen des aktuellen Zuges.

def return_shoot_state(self, state, crd):
	"""Стратегия дальнейщих ходов в зависимости от результата текущего хода"""
	if state == u'Попал!':
		self.scores += 1
		if not self.recomendation_pool:
			crd_rec = [[crd[0] - 1, crd[1]], [crd[0] + 1, crd[1]], [crd[0], crd[1] - 1], [crd[0], crd[1] + 1]]
			crd_rec = filter(lambda x: 0 <= x[0] <= 9 and 0 <= x[1] <= 9, crd_rec)
			crd_rec = filter(lambda x: x not in self.alien, crd_rec)
			self.succ_shoots.append(crd)
			self.recomendation_pool.extend(crd_rec)
		else:
			crd_s1 = self.recomendation_pool[0]
			crd_s2 = self.succ_shoots[0]
			for ind in range(2):
				if crd_s1[ind] != crd_s2[ind]:
					if crd_s1[ind] > crd_s2[ind]:
						crd_rec = [[crd_s1[ind]+1, crd_s1[ind]+2], [crd_s2[ind]-1, crd_s2[ind]-2]]
					else:
						crd_rec = [[crd_s1[ind]-1, crd_s1[ind]-2], [crd_s2[ind]+1, crd_s2[ind]+2]]
						crd_rec = filter(lambda x: 0 <= x[0] <= 9 and 0 <= x[1] <= 9, crd_rec)
						crd_rec = filter(lambda x: x not in self.alien, crd_rec)
						self.recomendation_pool.extend(crd_rec)
	elif state == u'Убил!':
		self.scores += 1
		self.recomendation_pool = []
		self.succ_shoots = []


Wichtige Variablen: recomendation_pool - Liste der Koordinaten für zukünftige Aufnahmen, succ_shoots - letzter erfolgreicher Schuss.

Wenn wir das Schiff treffen, müssen Sie erstens Punkte für einen erfolgreichen Schuss sammeln (Punkte + 1) und zweitens verstehen, was als nächstes zu tun ist. Wir überprüfen recomendation_pool, ob dort etwas ist, wenn nicht, notieren Sie sich dort 4 Koordinaten in der Nähe (nachdem Sie sie nach den Grenzen des Feldes und der Liste der Koordinaten gefiltert haben, die wir bereits aufgenommen haben).

Bild

Wenn recomendation_pool nicht leer ist, bedeutet dies, dass wir das zweite Mal treffen und es sich nicht um 4 Koordinaten handelt, sondern um zwei von jeder Kante.

Bild

Wenn das Schiff durch den aktuellen Schuss versenkt wurde, betrachten wir unsere Aufgabe als erledigt und bereinigen den Pool von Empfehlungen und so weiter. Der nächste Schuss wird nach dem Zufallsprinzip ausgeführt.

service.gen_cord- Generiert alle möglichen Koordinaten für jeden Schiffstyp. Das Ergebnis der Funktion ist ein Wörterbuch mit der folgenden Struktur: {"S0": [[[x0, y0], [x1, y2], [xN0, yN1], [[x3, y3], [x4, y4], [xN2 , yN3]], ...], "S1": ...}, wobei S der Schiffstyp ist, [[x0, y0], [x1, y2], [xN0, yN1]] der Satz von Koordinaten für das Schiff.

def gen_cord():
	"""Генератор всех возможных комбинаций координат"""
	all_comb = [[x/10, x % 10] for x in range(100)]
	for_1_ship = filter(lambda x: x[0] in range(2, 8) and x[1] in range(2, 8), all_comb)
	for_other_ship = filter(lambda x: x not in for_1_ship, all_comb)
	cord_comb = {1: [[x] for x in for_1_ship], 2: [], 3: [], 4: []}
	for ship in filter(lambda x: x != 1, cord_comb.keys()):
		for cord in for_other_ship:
			hor_direction = [cord] + [[cord[0]+x, cord[1]] for x in range(1, ship)]
			ver_direction = [cord] + [[cord[0], cord[1]+x] for x in range(1, ship)]
			for dir_d in [hor_direction, ver_direction]:
				for cord_d in dir_d:
					if cord_d not in for_other_ship:
						break
				else:
					cord_comb[ship].append(dir_d)
	return cord_comb

Wichtige Variablen: all_comb - speichert die Koordinaten des Feldes im Format [[x0, y0], [x1, y1], ...]. for_1_ship - das gleiche 6x6-Quadrat für ein Deck, for_other_ship - ein Satz von Koordinaten für alle anderen Schiffe. cord_comb - ein Wörterbuch, in dem alle Kombinationen von Koordinaten gespeichert sind.

Schiffsanordnung


Zum Zeitpunkt der Initialisierung der Instanz der Player-Klasse werden auch Schiffe platziert. In der Klasse ist dafür die Methode create_ships verantwortlich, wobei Folgendes auftritt:

1. Für jedes Schiff wird ein Satz von Koordinaten auf pseudozufällige Weise (random.choice) aus der verfügbaren Folge von Kombinationen von Koordinaten (Kombinationen) ausgewählt.
2. Als nächstes wird ein Halo (service.set_halo) für einen Satz von Koordinaten generiert. Ein Halo ist ein Satz von Koordinaten, an denen ein Schiff nicht mehr platziert werden kann (Regel: Schiffe nicht in der Nähe platzieren).

Bild

3. Dann löschen wir die Liste der Kombinationen (data_cleaner) aus der Liste, die aus den Koordinaten des Schiffes und des Halos besteht.

Protokollierungsmodul


Am Ende der Entwicklung entdeckte ich das Protokollierungsmodul aus der Standardbibliothek. Die Ausgabefelder sind anpassbar (logging.basicConfig), und das Arbeiten mit der Ausgabe ist nicht schwieriger als beim Drucken.

Bild

Andere


sevice.rdn_usr_name - generiert zufällige Spielernamen aus einer Reihe von Buchstaben und Zahlen von 0 bis 999.

Das Spiel endet, wenn der Gegner Player.ships_defeat = 10 hat, d. h. alle 10 Schiffe versenkt. Der Zähler wird aktualisiert, wenn das Schiff "Killed!" Antwortet.

Verbesserungsliste (TO DO)


1. Machen Sie ein Turnier zwischen den Spielern, zum Beispiel, wo es 1000 Spieler geben wird. Theoretisch sollte das gesamte Turnier unter Berücksichtigung der aktuellen Vorlaufzeit etwa 30 Sekunden dauern.

2. Fügen Sie einen "Basisalgorithmus" für die Bewegung hinzu, z. B. "Cross to Cross" stanzen Sie alle Zellen diagonal und dann weiter. Implementieren Sie mehrere dieser Algorithmen, und weisen Sie sie dem Spieler zu, der sie zufällig bearbeitet. Vergleichen Sie dann die Effizienz (z. B. was ergibt mehr Ergebnisse für Zufallsbewegungen oder den "Cross to Cross" -Algorithmus?)

3. Optimieren Sie den Suchmechanismus für Kombinationen (service.gen_cord), weil Offensichtlich ist es redundant und verbraucht eine Menge Ressourcen.

4. Implementieren Sie verschiedene Strategien zur Platzierung von Schiffen und vergleichen Sie dann, welche am erfolgreichsten ist.

PS Für interessante Ideen wäre ich dankbar.

Vielen Dank.

UPDATE (16.01.2015)

Das Turnier wird durchgeführt + eine kleine Sammlung von Statistiken wurde erstellt und hier ist das Ergebnis:


Im Turnier gibt es ein Abstiegsspiel, d.h. wenn du auf der Spur verloren hast. Du bekommst keinen Schritt.

Damit das Turnier ohne Pfosten auskommt, muss die Anzahl der Spieler so bemessen sein, dass beim Teilen der Rest der Division immer durch 2 geteilt wird, und bevor die Anzahl der Spieler im Turnier nicht 1 ist (d. H. Der Gewinner). Diese Nummern umfassen 1024 (512, 256, 128, 64, 32, 16, 8, 4, 2).

Früher nahm ich an, dass das Turnier ungefähr 30 Sekunden dauern würde, d.h. Die Zeit wächst linear mit der Anzahl der Spieler, aber was war meine Überraschung, als das gesamte Turnier für 1024 Spieler nur 17 Sekunden dauerte. Warum es sich herausstellt, weiß ich nicht, 17 Sekunden, vielleicht fangen einige Optimierungsmechanismen an zu funktionieren. Meine Berechnungen lauten wie folgt: 1022 Spiele dauern das ganze Turnier * 25 ms ein Spiel = 25,55 Sekunden.

Die Turnierstatistik wird innerhalb der folgenden Werte gehalten:

1. Durchschnittliche Anzahl von Zügen (alle Spieler): 85,06,
2. Durchschnittliche Anzahl von Zügen von Gewinnern: 85,95,
3. Durchschnittliche Anzahl von Zügen von Verlierern: 84,17,
4. Durchschnittliche Anzahl von von Verlierern erzielten Punkten: 17.75

Wir können die folgenden Schlussfolgerungen ziehen:

1. Die Anzahl der Züge, die Gewinner und Verlierer in etwa gleich machen.

2. Die Anzahl der Punkte beträgt fast 18 (Sie benötigen 20, um zu gewinnen).

Fazit: Beide Spieler spielen ungefähr gleich und gleich ineffizient :) Ein Unterschied von 2 Punkten zeigt, dass der Sieg in den letzten Zügen buchstäblich aus den Fängen des Gegners ausbricht.

Fazit: seit Jetzt wird jeder Spieler nach der gleichen Strategie geführt. Es gibt keine besondere Vielfalt im Spiel. Um es interessanter zu gestalten, müssen Sie verschiedene Strategien sowohl für die Anordnung von Schiffen als auch für die Durchführung von Umzügen implementieren, was ich in naher Zukunft in meiner Freizeit tun werde.

Bleiben Sie dran für Updates.

UPDATE2 (16.01.2015) Das
Hinzufügen eines Halos zur Liste der fehlerhaften Koordinaten nach dem Untergang des Schiffes wurde implementiert (im Prinzip ist alles in Ordnung). Die Statistik über die Anzahl der Züge hat sich deutlich verbessert:
1. Die durchschnittliche Anzahl der Züge (aller Spieler): 58,91,
2. Die durchschnittliche Anzahl der Züge der Sieger: 60,98,
3. Die durchschnittliche Anzahl der Züge der Verlierer: 56,83,
4. Die durchschnittliche Anzahl der Punkte, die die Verlierer erzielt haben: 15,37

Vielen Dank, Meklonfür die idee.

UPDATE3 (17.01.2015)

Neue Strategien für die Platzierung von Schiffen (mit 60 Zellen für ein Deck) implementiert. Das Ergebnis war das Folgende: Wenn jeder der Spieler dieselbe Strategie verwendet, gibt es keinen Unterschied zwischen den Verlierern und den Gewinnern. Wenn jedoch jedem Spieler eine zufällige Zuweisungsstrategie zugewiesen wird, ist klar, dass meine Strategie mehr Krieger enthält (6x6 Felder in der Mitte). d.h. Wenn meine Strategie verworfen wird, spielen alle in etwa auf die gleiche Weise. Das ist auch nicht interessant. Jetzt werde ich verschiedene Bewegungsstrategien implementieren (vielleicht gibt es etwas Super-Optimales).

Daten
left,right, top,bottom и т.п. — это всё вариации размещения 60 координат на поле.
[2015-01-17 19:14:07,780] Статистика:
1. Среднее количесво ходов (всех игроков): 63.18,
2. Среднее количество ходов выйгравших игроков: 64.82,
3. Среднее количество ходов проигравших игроков: 61.54,
4. Среднее количество очков, которое набрали проигравшие: 16.24
[2015-01-17 19:14:07,783] Стратегия: for_1_ship_left loosers: 508
[2015-01-17 19:14:07,783] Стратегия: for_1_ship_left winners: 515

[2015-01-17 19:20:27,526] Статистика:
1. Среднее количесво ходов (всех игроков): 62.58,
2. Среднее количество ходов выйгравших игроков: 64.23,
3. Среднее количество ходов проигравших игроков: 60.93,
4. Среднее количество очков, которое набрали проигравшие: 16.23
[2015-01-17 19:20:27,529] Стратегия: for_1_ship_right loosers: 498
[2015-01-17 19:20:27,529] Стратегия: for_1_ship_right winners: 525

[2015-01-17 19:21:40,153] Статистика:
1. Среднее количесво ходов (всех игроков): 58.94,
2. Среднее количество ходов выйгравших игроков: 61.02,
3. Среднее количество ходов проигравших игроков: 56.87,
4. Среднее количество очков, которое набрали проигравшие: 15.35
[2015-01-17 19:21:40,155] Стратегия: for_1_ship_36 loosers: 518
[2015-01-17 19:21:40,157] Стратегия: for_1_ship_36 winners: 505

[2015-01-17 19:23:37,322] Статистика:
1. Среднее количесво ходов (всех игроков): 62.85,
2. Die durchschnittliche Anzahl von Zügen der gewinnenden Spieler: 64,55,
3. Die durchschnittliche Anzahl von Zügen der verlierenden Spieler: 61,16,
4. Die durchschnittliche Anzahl von Punkten, die die Verlierer erzielt haben: 16,15
[2015-01-17 19: 23: 37,323] Strategie: for_1_ship_bottom loosers: 526
[ 2015-01-17 19: 23: 37,325] Strategie: for_1_ship_bottom Gewinner: 497

[2015-01-17 19: 33: 07,933] Statistik:
1. Durchschnittliche Anzahl von Zügen (alle Spieler): 61,59,
2. Durchschnittliche Anzahl von Zügen von Gewinnern : 63.37,
3. Durchschnittliche Anzahl der Züge verlorener Spieler: 59.81,
4. Durchschnittliche Anzahl der von Verlierern erzielten Punkte
: 15.95 [2015-01-17 19: 33: 07,934] Strategie: for_1_ship_center_vertical loosers: 512
[2015-01-17 19: 33: 07,934] Strategie: for_1_ship_center_vertical Gewinner: 511

[2015-01-17 19: 36: 03,585] Statistik:
1. Durchschnittliche Anzahl der Züge (alle Spieler): 61,03,
2. Durchschnittliche Anzahl der gewonnenen Züge Spieler: 62,89,
3. Die durchschnittliche Anzahl der Züge von Verlierern: 59,18,
4. Die durchschnittliche Anzahl der Punkte, die Verlierer erzielten: 15,78
[17.01.2015 19: 36: 03,589] Strategie: für_1_Schiff_36 Verlierer: 148
[17.01.2015 19 : 36: 03,589] Strategie: for_1_ship_36 Gewinner: 109
[2015-01-17 19: 36: 03,591] Strategie: for_1_ship_bottom Verlierer: 34
[2015-01-17 19: 36: 03,591] Strategie: for_1_ship_bottom Gewinner: 50
[2015- 01-17 19: 36: 03,591] Strategie: for_1_ship_center_horisontal loosers: 129
[2015-01-17 19: 36: 03,591] Strategie: for_1_ship_center_horisontal Gewinner: 120
[2015-01-17 19: 36: 03,592] Strategie: for_1_ship_center_vertical Verlierer: 96
[2015-01-17 19: 36: 03,592] Strategie: for_1_ship_center_vertical Gewinner: 94
[2015-01-17 19: 36: 03,592] Strategie: for_1_ship_left Verlierer: 28
[2015-01-17 19: 36: 03,592] Strategie: for_1_ship_left Gewinner: 44
[2015-01-17 19:36: 03.592] Strategie: for_1_ship_right Verlierer: 40
[2015-01-17 19: 36: 03.594] Strategie: for_1_ship_right Gewinner: 48
[2015-01-17 19: 36: 03.594] Strategie: for_1_ship_top Verlierer: 35
[2015-01-17 19: 36: 03,594] Strategie: für_1_Schiffsieger: 48


UPDATE4 (01.20.2015)

Verschiedene Optionen für das Ausführen von Zügen hinzugefügt: zufällig - zufällig aus freien Zellen, kreuzweise, linear - linear in 4 Reihen durch eine (wie in gelobten Artikeln). Ein wichtiger Punkt: Die Strategie für die Anordnung von Schiffen wird für das gesamte Turnier festgelegt, die Strategie für Züge wird jedoch für jedes Spiel festgelegt.

Ich habe Statistiken gesammelt (lassen Sie mich daran erinnern, es geht um Turnit, wo 1024 Spieler im Abstieg gegeneinander spielen). Wichtigste
Bild

Ergebnisse:
Strategien für die Platzierung von Einzeldeckschiffen random_12 (12 zufällige Zellen werden ausgewählt und die Schiffe darin platziert) und for_1_ship_36 (6x6-Feld in der Mitte) sind eindeutig am wenigsten wirksam.

Eine gleichmäßige Verteilung zeigt an, dass Gleichheit unter Gleichheit ungefähr dasselbe Ergebnis liefert und der Sieg einer von ihnen nur eine zufällige Folge ist.

Die Anzahl der Züge mit der Implementierung zusätzlicher Zugstrategien hat sich nicht verringert, aber die Turnierzeit hat sich von 25 auf 50 Sekunden erhöht:
1. Die durchschnittliche Anzahl von Zügen (alle Spieler): 61,43,
2. Die durchschnittliche Anzahl von Zügen von Gewinnern: 63,23,
3. Die durchschnittliche Anzahl von Zügen von Verlierern : 59.63,
4. Die durchschnittliche Anzahl der Punkte, die Verlierer erzielten: 15.93

Ich wäre dankbar, wenn jemand meinen Code auf GitHub anschauen und seine Empfehlungen zur Verbesserung abgeben würde.

Es verbleibt eine geplante Optimierungsaufgabe, aber wie Sie wissen, kann die Optimierung auf unbestimmte Zeit durchgeführt werden, sodass der Artikel in naher Zukunft nicht ohne besonderen Bedarf aktualisiert wird.

Vielen Dank für Ihre Aufmerksamkeit und möge die Kraft von Python mit Ihnen kommen!

Jetzt auch beliebt: