# We write AI for Vindinium on single-board computers. Part 2: Decision Logic

A series of articles on writing AI for multiplayer online game of the bagel genre.

In this part of the article, we will look at approaches to creating logic for AI, talk a little about the goal-setting of each law-abiding bot, and determine the choice of programming language and write some code.

## The game world Vindinium

In order to create an AI, you need to understand the device of the game world.

Free translation of game documentation

#### Description

Vindinium is a multiplayer turn-based bagel. Each of the four players has one hero who can move around the map. The goal is for the players to collect the maximum amount of gold for a given number of moves (each player makes 300 moves per game, so the whole game consists of 1200 moves). Players must take control of gold mines to produce gold; however, the mines are protected by goblins. When a player defeats a goblin, he becomes the owner of the mine and receives one gold per turn. In addition, the goblin now protects the mine from other players.

Heroes can fight each other. A survivor in battle gains control of all the gold mines of his opponent. The slain hero is immediately reborn with all his gold, but all mines pass into the hands of the killer.

When attacking a tavern, heroes can buy beer for 2 gold units, thus restoring their health points.

The goal is to create a computer program (bot) that plays the game Vindinium as reasonably as possible. It is recommended that you use one of the starter kits for a large number of programming languages as a starting point.

#### Map

Maps are created randomly. Each game object on the card is encoded using two characters. Sample map:

``+----------------------------------------+ |######\$- \$-############\$- \$-######| |###### ## ## ######| |####[] #### #### []####| |## #### ## ## #### ##| |#### \$- \$- ####| |########## @1 @4 ##########| |############ #### #### ############| |\$-##\$- ############ \$-##\$-| | \$- \$-################\$- \$- | | ######################## | | ######################## | | \$- \$-################\$- \$- | |\$-##\$- ############ \$-##\$-| |############ #### #### ############| |########## @2 @3 ##########| |#### \$- \$- ####| |## #### ## ## #### ##| |####[] #### #### []####| |###### ## ## ######| |######\$- \$-############\$- \$-######| +----------------------------------------+` `

#### Legend

`##` - Insurmountable Forest
`@1` - First Hero
`[]` - Taverns
`\$-` - Gold Mine (no one's)
`\$1` - Gold Mine (owned by the first hero)

The generated maps are symmetrical and always contain 4 taverns and 4 heroes.

#### Hero

Heroes can move one cell for each turn and have the following indicators:

• Health Points (HP): Each “fresh” player starts with a maximum value = 100. If HP drops to zero, the hero dies (see the section “Death of a Hero”).
• Gold: starting from scratch, this is an indicator of the hero’s success. At the end of the game, heroes will be rated based on their amount of gold.
• The number of gold mines.

#### Direction of travel

The bot must give one order per turn. Possible orders: `Stay` , `North` , `South` , ( `East` ) or ( `West` ). As soon as the order is executed, the hero remains in his place or moves one square in a given direction.

##### Moving Hero

If the hero:

• Trying to go beyond the boundaries of the map or go through the trees, nothing happens.
• It goes into a gold mine, it remains in place and:
• If the mine already belongs to the hero, nothing happens.
• If the mine is drawn or belongs to another hero, there is a battle with the goblin warden guarding the mine. The hero loses 20 hit points. If he survives, mine is his.
• Attacking another hero, he stays in place and nothing happens. Hero fights are decided at the end of the turn.
• He enters the tavern, he stays in place and orders himself to eat. The hero pays 2 gold and recovers 50 health. Please note that the amount of health can not exceed 100 units.
• He does not send an order for the time allotted to him to make a decision (1 second), he remains in place until the end of the game, it becomes impossible to send new orders. Please note that he can still win if at the end of the game he has more gold than other players.

#### End of turn

After the hero has moved (or decided to stay in place), the following things will happen:

##### Battles

Heroes are a little nervous and never miss an opportunity to strike each other with big swords. At the end of the hero’s turn, if there is an enemy at a distance of one square in any direction, the hero attacks him. For example, in this situation, at the end of the move of the first hero ( `@1` ):

` `######## ##@1@2## ## @3## ########` `

Player 1 attacks the second player, but does not touch the third player, because the third player stands at a distance of two cells from him.
The attacker does not lose health points, the defender loses 20 points.
If the defender dies (see: Death of the hero), the attacker gains control of all the gold mines of the loser.

##### Gold mining

After his turn and battles with other heroes (if any), the player receives one unit of gold for each mine he controls.

##### Thirst

Then the hero loses one health unit, for any action makes him thirsty.
Note that heroes cannot die of thirst. In the worst case, the value of their health drops to unity.

#### Hero's death

When the hero's health drops to zero, he dies. The hero immediately appears on the map at his point of rebirth, with a full stock of health (100 units). The hero loses control of all his gold mines, but retains all his accumulated gold. Be careful when the hero returns to the resurrection point, any opponent who is in this cell automatically dies. Thus, you should avoid staying on the cell of the rebirth of one of the heroes ...

The hero cannot die of thirst. Thirst can leave a hero with one health unit, but not kill him.

#### End of the game

The game ends when the maximum number of moves is reached (usually 300). The winner is the hero with the most gold. If two players have the same amount of gold, there is no winner.

#### Rating

The system for assessing the relative strength of players uses Elo Rating The idea is this: it is better to be first than second, better to be second than third, and so on. I hope the principle is clear.

#### Using multiple bots at the same time

You can simultaneously run multiple instances of your bots and, in general, use any measures that you think are suitable for achieving dominant leadership. Fight!

It is worth noting a couple of aspects that were not described in the rules, but identified empirically:

• If we have less than 21 health units, but you attack a mine that does not belong to you, then you die. Yes, yes, there is no protection from a fool; everything is serious here, as in most real battles. If you attack a nobody's mine, all your mines become no man’s, and if you mine one of the enemies, then your mines pass into the hands of the player who owns this mine.
• The game describes the following procedure: - - `1` . And what happens if during the execution of the order we die (in the game you can do this only by dying in a battle with the goblin)? We are reborn (and instantly kill the player who is standing now at our spawnpoint), but lose the opportunity to hit the closest enemies, and also do not lose 1 health point due to thirst.
• After killing an opponent standing on our spawnpoint during our revival, we capture his mines, hehe.
• The map has a square view, the length of the map takes on even values ​​on the segment [8, 28].

## "Learn from your enemies and you will understand their strengths."

Vindinium is a public game, its useful side is that we can look in the profile of any player and see the last hundred battles with his participation. "Great! It's time to use neural networks, because we have 50 top players, take 10 of them to be the strongest, each of the last 100 fights contains ~ 300 moments when the player had to make a decision, about 200-300 thousand units in total material for training! And you can also rotate every situation clockwise, mirror, etc, to get even more material for training and fix the result, it will give us as much as 4.8-7.2 million units of material "- the voice of reason rang out. Yes, indeed, such an idea has the right to exist. In addition, neural networks have many advantages.

• All material for learning is easily parsed from open source.
• A wide scope for reflection on computer vision is revealed:
• You can leave everything as it is, there will be 28 * 28 input neurons (if the card is smaller, we fill it with trees);
• You can center each time according to the position of the hero (maybe it will bring some amazing result);
• It is possible to present the map as a graph, thus the work of the neural network to find patterns is greatly facilitated; This option will allow the neuron to quickly find patterns of complex behavior and quickly understand why, if we have little health, we go to a far tavern, if there is another tavern just a couple of cells from us, even if it is close to the enemy;
• An already trained neural network, if you pre-set the task of resource consumption, can be compactly placed in 512 MB of RAM allocated for us (in fact, it turns out about 480 MB), so much so that the capacity of a single-board computer is sufficient for calculations.

However, adolescent maximalism in me wants to go a more complicated way - not to impose a search for patterns on the neural network, but to do this work independently, head on, relying on the intuitive higher plasticity of this solution.

So. Decision trees, alpha-beta pruning, minimax ... too resource-intensive tasks! On the Vindinium subreddit, several developers, revealing the veil of secrets of their bots, have already used this solution, and certainly not in such Spartan conditions. Unfortunately, in this area it is unlikely to be able to do anything better than the rest.

Having read articles about evolutionary, genetic algorithms, decisive trees, I dug out secret knowledge - potential fields. Read more about them here and here . This idea seemed very working, because the potential field is a planar graph, a function depending on the input data is placed in each link (in particular, the distance from the object, but no one bothers to make more conditions). All this fits perfectly into the realities of Vindinium - you do not need to look for a path to the object if it is already embedded in the algorithm.

## "Quite specific tastes"

Let's watch the battles of top characters. Before we start, we will choose a favorite, we will follow him, cheer for him, reproach for the wrong decisions in the style of "but I would do that at this place ...". After a dozen battles, it is already possible to make a first sketch of what a law-abiding AI is (conditions are checked in order):

1. You should not walk near the enemy's spawnpoint, if the enemy has a chance to die (that is, if we can expect an inglorious death while standing at the enemy's spawnpoint);
2. It is foolish to fight with your enemy near his spawnpoint, for he still aki phoenix will be reborn with full health and again will try to capture our honestly looted mines;
3. If the enemy is close to us, and we stand near the tavern - time to get drunk. Judging by the many bloody battles near the means of subsistence and relaxation, this rule is very important;
4. If we can not defeat the enemy / enemies, but we have time to reach the tavern - we run;
5. If we can not defeat the enemy (s) And do not have time to reach the tavern, then:
• If we can commit suicide on a farm, we kill ourselves. Take a bite!
• If we can die on the miner's file of the person with the lowest amount of gold, we will get rid of it;
• If a sad end awaits us, then we need to take away as much health as possible from this reptile, let it be long to remember our mistake!
6. If there is an enemy whom we can kill within our two moves and he has minilki - we attack;
7. If there is an enemy, removed from all mine-feeds more than we, and he has 33% of mine-controls under control. And we can defeat him - we go to win, otherwise we go to drink beer;
8. Capture the farm, if nothing else remains.

• What are its advantages in comparison with neural networks, which will cope with this task a hundred times better, or with trees that all your next n moves in advance know and have already developed countermeasures, all that remains is a good evaluation function to apply?
• (1) Multifunctional. It's easier to change the parameters, add new features. You follow your character like this, you are happy, and then bang - and you see that at a certain moment you could have done something completely different, more prudent, - we write a new rule or change the old one. (2) We also know exactly what decision the program was guided by when choosing a particular course. (3) Potential fields have shown themselves well in bagels as the basis for artificial intelligence bots.

• Prove that your approach is effective, that your intentions are worth something.
• In the leaderboard, `Zaraza 0.1` hangs in the 27th place - AI on potential fields, which is guided by only three instincts - mindlessly seize everything that gets in its path, do not dry out in bars and carefully behave with enemies. If you follow his movements, you will see how well he is fighting, although it is simply unbelievable for AI, which is based on three simple rules, and even complex dreams will not appear to him even in dreams. Moreover, I am currently working on `Zonko 0.11` , which is a greatly improved version of the Zaraz drinkers; you can embed a much more complex behavior into it due to improved interaction with the fields - just like in the new-fashioned GPS. But, as it turned out, it is gluttonous to the resources, so now the process of its optimization is going on ... But I digress this, now we are talking about strict restrictions, strict rules of strict (...).

• Your beliefs are ridiculous, your faith is too weak! I can create an AI in the name of the method, and it will tear you!
• It will be very nice to listen to other people's thoughts on this topic. Moreover, for you I have already added up all the battles of the top 10 players, only 1000 battles and about 1,000,000 moves - link (.zip - 33MB, RAW - 1.68GB). I suggest the conditions of the game:
• Register bots under their nicknames in geektimes.
• The five players who scored the most points before September 30, than me or anyone else among those who have expressed to play, I will send a postcard from Moscow).

So, now the programming language ... Personally, I’m rushing around between Python3 (fast development, easy to read, have been familiar with it for a long time, there is pypy3 (fast optimized interpreter), jupyter ("notebooks" in which you can safely write pieces of code and optimize them to infinity); but pypy / pypy3 does not work under ARM 64bit, and indeed ARM is no longer supported, and the language itself is inferior to compiled because of its nature) and Golang (also fast development, easily understood, large backend bias, multithreading and multiprocessing, runs faster than python; but when etsya to get used to the absence of an interactive environment to static typing).

The main function that communicates with the server can be represented as follows:

Code
` `#     train_url, arena_url, userkey,   config.py from config import train_url, arena_url, userkey import requests, random, json, time def start(is_train = True, debug = True, show_decision = True): #   if is_train: r = requests.post(train_url, data={"key":userkey}) else: r = requests.post(arena_url, data={"key":userkey}) timer = time.time() data = json.loads(r.text) if debug or show_decision: print('viewUrl:', data['viewUrl']) print(' :', data['game']['board']['size']) # while True: if debug: print('Turn', data['game']['turn']) #     direction = random.choice(['North', 'South', 'East', 'West', 'Stay']) if show_decision or debug: print(' ',str(data['game']['turn'])+':', direction) #    ,   ,  . if debug: print(':',time.time()-timer) r = requests.post(data['playUrl'], data={'key': userkey, 'dir': direction}) timer = time.time() if r.status_code != 200: print('Request code :', r.status_code) print('Reason:', r.reason) break data = json.loads(r.text) if data['game']['finished']: print('Game finished.') break` `

But it is recommended to use ready-made designs, links to which can be found on the official website of Vindinium.

Extra 1: I really want to read about the development of artificial intelligence based on Vindinium from other people, because this is how one can understand the many facets of solving this problem. In order to get a summary of the battle in json format (this can be useful for debugging the battles), you need to convert the link to the fight http://vindinium.org/fd96vc2z into a link like http://vindinium.org/events/fd96vc2z . But I do not advise you to torment the game server, trying to get hundreds of battles of top players, use the link above.

Extra 2: If someone wants to try out their work in Vindinium, drive them into the limitations of NanoPi Neo2 or Orange Pi Zero, I can provide the opportunity to work with these single-board computers.