Clever Geek Handbook

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.







Part 1 .

Part 3







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.







image







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!







Link to the original







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









"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.









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.


Question answer:









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.







→ Link to Vindinium

→ Link to Vindinium sabreddit - a very useful thing, there you can track my movements on Vindinium

→ Link to my githab with some insights on Vindinium







In the next part we will customize potential fields, work with potential maps, write conditions and impose all this on modern realities.







More articles:


All Articles