25 ms naval battle

Foreword

A few months ago, I decided to learn Python. As one of the test tasks, it was required to write the game “Sea Battle”. Then I did not do this task, but the idea came to me to write “Naval battle”, where two computers will play with each other. This thought did not leave me, and I decided to dare. The result is presented to your court. I would be grateful for any constructive criticism.

General concept of current implementation

The whole game, in fact, boils down to the fact that two instances of the Player class ask each other for the coordinates of the ships and, depending on the answer, build their strategy of moves.

The strategy for arranging ships is as follows: 2-3-4 deck-based ships are placed on the edges of the map (2 cells), 1-decked in the center (6x6 square).



The strategy of the moves, as in the game between people: the first move at random, if you hit, then work through 4 cells around and then, if you hit again, then work through two cells already on the line (two, because the max. Ship length is 4 cells, 2 already hit, then max. there are 2 more cells).

In the articleeverything is described in sufficient detail on Wikipedia, so I won’t touch on the game logic much, especially since everyone already roughly understands what is being discussed. I have only such differences: scoring for each move, numbering cells from 0 to 9.

The game uses three classes: Game, Player, Ship. Using the Game class in the current implementation is redundant, since only one instance is used, but this is some groundwork for the future (see the list of improvements at the end of the article).

Game is responsible for the general game logic, Player - for the strategy of moves, Ship - stores the current state of the ships and their coordinates.

Link project in github.

The main difficulties that arose in the development

1. Design . Writing using classes or functions? What set of classes to use?
The main problem in the design turned out to be tracking various conditions in the game. For example, who is walking now, in what condition is the ship (hit, killed), has the game ended, who won, etc.

2. Logic / algorithms . How to arrange the ships in accordance with the strategy, how to choose the coordinates for the move?

Overview of the most interesting parts of the code

return_shoot_state - determines the further strategy depending on the results of the current move.

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 = []

Important variables: recomendation_pool - list of coordinates for future shots, succ_shoots - last successful shot.

If we hit the ship, then, firstly, you need to accrue points for a successful shot (scores + = 1), and secondly, understand what to do next. We check recomendation_pool if there is something there, if not, then write down 4 nearby coordinates there (after filtering them according to the borders of the field and the list of coordinates that we have already shot).



If recomendation_pool is not empty, it means that we hit the second time and we are not talking about 4 coordinates around, but about two from each edge.



If the ship was sunk by the current shot, we consider our task completed and we clean the pool of recommendations and so on. The next shot will be performed randomly.

service.gen_cord- Generates all possible coordinates for each type of ship. The result of the function operation will be a dictionary with the following structure: {"S0": [[[[x0, y0], [x1, y2], [xN0, yN1]], [[x3, y3], [x4, y4], [xN2 , yN3]], ...], "S1": ...}, where S is the type of ship, [[x0, y0], [x1, y2], [xN0, yN1]] is the set of coordinates for the ship.

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

Important variables: all_comb - stores the coordinates of the field in the format [[x0, y0], [x1, y1], ...]. for_1_ship - the same 6x6 square for single-deck, for_other_ship - a set of coordinates for all other ships. cord_comb is a dictionary that stores all combinations of coordinates.

Ship arrangement

At the time of initialization of the instance of the Player class, ships are also placed. In the class, the create_ships method is responsible for this, where the following occurs:

1. For each ship, from the available sequence of combinations of coordinates (combinations), a set of coordinates is selected in a pseudo-random way (random.choice).
2. Next, a halo (service.set_halo) is generated for a set of coordinates. A halo is a set of coordinates at which a ship cannot be put later (rule: do not place ships nearby).



3. Then we clear the list of combinations (data_cleaner) from the list which consists of the coordinates of the ship and the halo.

Logging Module

At the end of development, I discovered the logging module from the standard library. The output fields are customizable (logging.basicConfig), and working with the output is no more difficult than with print.

Other

sevice.rdn_usr_name - generates random player names from a set of letters and numbers from 0 to 999.

The game ends if the opponent has Player.ships_defeat = 10, i.e. sunk all 10 ships. The counter is updated if the ship answers “Killed!”.

Improvement List (TO DO)

1. Make a tournament between the players, say, where there will be 1000 players. In theory, taking into account the current execution time, the entire tournament should take about 30 seconds.

2. Add a “basic algorithm” of the move, for example, cross to cross, ie punch all cells diagonally and then further. Implement several of these algorithms and then assign the player randomly work on them. Then compare the efficiency (for example, what gives more results to random moves or the “cross to cross” algorithm?)

3. Optimize the search mechanism for combinations (service.gen_cord), because obviously, it is redundant and consumes a lot of resources.

4. Implement various ship placement strategies and then compare which one is most successful.

PS I would be grateful for any interesting ideas.

Thanks.

UPDATE (01/16/2015)

The tournament is implemented + a small collection of statistics has been made and here is the result:

In the tournament there is a relegation game, i.e. if you lost on the trail. you don’t get a step.

In order for the tournament to be without jambs, the number of players must be such that when dividing the remainder of the division is always divided by 2, and so before the number of players in the tournament is not 1 (i.e. the winner). These numbers include 1024 (512, 256, 128, 64, 32, 16, 8, 4, 2).

Earlier, I assumed that the tournament would last about 30 seconds, i.e. time grows linearly depending on the number of players, but what was my surprise when the entire tournament for 1024 players was only 17 seconds. Why it turns out I don’t know 17 seconds, maybe some optimization mechanisms are starting to work. My calculations are as follows: 1022 games lasts the whole tournament * 25 ms one game = 25.55 seconds.

The tournament statistics is kept within the following values:

1. Average number of moves (all players): 85.06,
2. Average number of moves of winning players: 85.95,
3. Average number of moves of losing players: 84.17,
4. Average number of points scored by losers: 17.75

We can draw the following conclusions:

1. The number of moves that winners and losers make about the same.

2. The number of points is almost 18 (you need 20 to win).

Bottom line: both players play about the same and equally inefficient :) A difference of 2 points shows that victory literally breaks out of the opponent’s clutches in the last moves.

Conclusion: since Now each player is guided by the same strategy. There is no particular diversity in the game. To make it more interesting, it is necessary to implement various strategies both for the arrangement of ships and the execution of moves, which is what I will do at my leisure in the near future.

Stay tuned for updates.

UPDATE2 (01/16/2015)
Implemented adding a halo to the list of broken coordinates after the sinking of the ship (in principle, everything is fair). Statistics on the number of moves has improved significantly:
1. The average number of moves (of all players): 58.91,
2. The average number of moves of winning players: 60.98,
3. The average number of moves of losing players: 56.83,
4. The average number of points that losers scored: 15.37

Thanks Meklonfor the idea.

UPDATE3 (01/17/2015)

Implemented new strategies for placing ships (where there are 60 cells for single-deck). The result was the following, if each of the players uses the same strategy, then there is no difference between the losers and the winners, but if each player has an assignment strategy assigned randomly, then it is clear that there are more warriors with my strategy (6x6 square in the center), those. if my strategy is thrown away, then everyone will play about the same. This is also not interesting. Now I will implement various strategies of moves (maybe there is something super-optimal).



UPDATE4 (01/20/2015)

Added various options for making moves: random - randomly from free cells, cross - cross to cross, linear - linearly in 4 rows through one (as in praised articles). An important point: the strategy for arranging ships is issued for the entire tournament, but the strategy of moves is issued for each game.

I collected statistics (let me remind you, it’s about turnit, where 1024 players play among themselves on the relegation).


Key findings:
Single-deck ship placement strategies random_12 (12 random cells are selected and the ships are placed in them) and for_1_ship_36 (6x6 field in the center) are clearly the least effective.

A uniform distribution indicates that equals among equals gave approximately the same result and the victory of one of them is only a random consequence.

The number of moves with the implementation of additional move strategies has not decreased, but the tournament time has increased from 25 to 50 seconds:
1. The average number of moves (all players): 61.43,
2. The average number of moves of winning players: 63.23,
3. The average number of moves of losing players : 59.63,
4. Average points that losers scored: 15.93

I would be grateful if someone looked at my code on GitHub and gave their recommendations on how to improve it.

There remains one planned optimization task, but, as you know, optimization can be done indefinitely, so the article will not be updated in the near future without special need.

Thank you for your attention and may the power of Python come with you!