Dec. 11, 2020
# Android Interface I started by looking at what other people did on GitHub. I stumbled upon this [repository (ebensh/hoplite_ai)](https://github.com/ebensh/hoplite_ai), that was using [monkeyrunner](https://developer.android.com/studio/test/monkeyrunner), a tool provided by the Android Studio software for controlling any Android device connected to the computer (whether it is simulated or plugged-in via USB). That tool looked very promising, and I started implementing a basic interface where I could call methods such as `touch(x, y)` that would actually trigger actions on the Android device. More precisely, I have two scripts for that: - [monkey.py](https://github.com/ychalier/hoplite/blob/master/monkey.py): a script that is loaded by *monkeyrunner*, that acts as a local socket server; it listens to commands (such as *touch* or *take a screenshot*) and triggers them on the Android device that first connects to it; - [hoplite/monkeyrunner.py](https://github.com/ychalier/hoplite/blob/master/hoplite/monkey_runner.py): a socket client, a component of the AI module, that I can call whenever I need an action to be performed; it sends a request to the server with the appropriate syntax. Getting it to work was a little painful because of weird errors. I have finally got it to work after some intensive StackOverflow crawling. Though I still have some errors when the programs terminates abruptly and the communication with the device does not end properly. Fortunately, a classic *turn-it-off-and-on-again* intervention solves it. So now, I can programmatically touch the screen and take screenshots of it. Yay!
# Giving My Script Some Eyes Now that I can retrieve screenshots from the game, I need a way to parse into an internal data structure that will be interpreted by the AI: - the terrain data (tiles, enemies, etc.), - the player's health, - the player's current *bash* cooldown, - the location of the player's spear, - the current kill streak, - etc. I tried various techniques for that matter, such as minimizing the squared difference of parts of the screen to templates or using a small neuron network for classification. Yet, all those methods were quite greedy and I felt like I could find something better. First I extract the part of the screenshot that needs classification. For instance, in the case of a terrain tile (whose position is always the same), I look at a square box around that tile. Graphics in the game are clean pixel textures. Even the colors are constant from one screenshot to another. Therefore, I only need a few (sometimes one is enough) pixels for classifying that tile into one of the templates. I wrote a small script that identifies, for each template, one pixel that differs from all other templates. I then put this pixel value in a large `if` clause that identifies the image. See that extract of [classifiers.py](https://github.com/ychalier/hoplite/blob/master/hoplite/vision/classifiers.py): ```Python if is_close(part[45, 40], [0.937255, 0.541176, 0.192157]): return hoplite.game.terrain.SurfaceElement.FOOTMAN if is_close(part[15, 26], [0.611765, 0.890196, 0.352941]): return hoplite.game.terrain.SurfaceElement.ARCHER if is_close(part[37, 37], [0.741176, 0.141176, 0.192157]): return hoplite.game.terrain.SurfaceElement.PLAYER if is_close(part[20, 23], [1.000000, 0.764706, 0.258824]): return hoplite.game.terrain.SurfaceElement.BOMB if is_close(part[26, 26], [0.4509804, 0.27058825, 0.09411765]): return hoplite.game.terrain.SurfaceElement.SPEAR if is_close(part[26, 26], [0.9372549, 0.5411765, 0.19215687]): return hoplite.game.terrain.SurfaceElement.SPEAR ``` This way, I have a 100% accuracy on detecting what's happening on screen in about 10ms per screenshot. # Implementing The Game Mechanics Here is where things went complex. The actual game mechanics are not publicly available, and a lot of details, necessary for making accurate predictions, are hard to comprehend. I wrote what I could in [RULES.md](https://github.com/ychalier/hoplite/blob/master/RULES.md). I used various sources to complete my own experience: - the game's own subreddit [r/Hoplite/](https://www.reddit.com/r/Hoplite/), - the [developper's blog](http://www.magmafortress.com/2014/07/hoplite-23-progress.html), - the [developper's Discord](https://discord.com/channels/692958702805975050/692958703229337661/704958237224730654). For instance, look at the [rules applied for knocking back enemies after a bash](https://github.com/ychalier/hoplite/blob/master/RULES.md#323-bash). One does not simply guess that from a few examples. Here are the two major difficulties I encountered when exploring for those rules: 1. Some rules are not deterministic, which makes generalizing rules harder. 2. Controlling the experiment settings is very hard. Use emulator state saves helps but getting the perfect settings for an experiment is still very rare. Because of those, I gave up on predict enemies movement. My best guess was that enemies tried to get in range of the player while still getting closer to it, but it seems like in some situations, slight behavior changes can occur leading to the global prediction being irrelevant. # The Brain With my current implementation of the game rules, I am able to predict the exact state I will be in after the player's move, but not where the enemies will be after their move. Therefore, I am not able to perform some complex exploration like what a chess engine could do (which was my first intention). Then, the AI's brain only enumerates the player's possible moves, and selects the best one in a very short-term objective. That's unfortunate, but it kind of works. [I managed to finish the first 16 levels without being hit with this simple mechanism.](https://www.youtube.com/watch?v=8ofj6W05LZg&list=PL2ecHtEW1_x9NVOkVryLtduEI3Y_NNnuB&index=4&t=0s) To evaluate the *goodness* of a move, just as in chess, I have a function for evaluating the current state of the game. This function relies on numerical features, manually weighted, that are summed up into a final score. The greater the better it looks for the player. The brain enumerates the possible moves, predicts the state that would result from that move, evaluates this state and so ranks the possible moves. Feature | Range | Scaling | Weight --- | --- | --- | --- Whether the player is alive or dead | 0 or 1 | 1 | -100 Player's health | 0 to 8 | 0.125 | 25 Player's energy | 0 to 100+ | 0.01 | 1 Player's cooldown | 0 to 4 | 0.25 | -0.5 Distance ([A*](https://en.wikipedia.org/wiki/A*_search_algorithm)) to stairs | 0 to 9+ | 0.11 | -0.5 Distance ([A*](https://en.wikipedia.org/wiki/A*_search_algorithm)) to the portal | 0 to 9+ | 0.11 | -1 Distance ([A*](https://en.wikipedia.org/wiki/A*_search_algorithm)) to the fleece | 0 to 9+ | 0.11 | -2 Distance ([A*](https://en.wikipedia.org/wiki/A*_search_algorithm)) to the altar | 0 to 9+ |0.11 | -1 Distance ([A*](https://en.wikipedia.org/wiki/A*_search_algorithm)) to the spear (if thrown) | 0 to 9+ | 0.11 | -2 Enemies danger | 0 to 25+ | 0.04 | -6 where the enemies danger is the sum over all the enemies on the map of: Enemy type | Danger --- | --- Footman | 1 Demolitionist | 2 Archer | 3 Wizard | 4 After scaling all features so they usually end up in a [0, 1] interval, I manually set the weights. This was a way to rank all possible moves: simply walking one tile towards the stairs rewards less than killing an archer which rewards less than not taking one hit. Of course, such weights need to be fine-tuned through and actual optimization method, by playing the game a lot. But I did not manage to recreate the game in its entirety, and only having a partial prediction tool would make converging towards the golden weights incredibly slow, even slower because of the realtime speed of the game. # Results That is all there is to it. The code is available on GitHub at [ychalier/hoplite](https://github.com/ychalier/hoplite). I recorded some runs along the development process, showing how the AI got better. Here is the playlist: