AI for playing (and winning) in Dark Souls PvP
https://github.com/metal-crow/Dark-Souls-PvP-AI

People who if you like this you should also follow:
https://github.com/eur0pa. Creator of Dark Souls pvp watchdog. Thanks man!
https://github.com/OrdinaryMagician. Various projects in Dark Souls 2, and assembly master.
https://www.youtube.com/user/Birdulon. Master reverse engineerer; he found the Dark Souls 2 bullet params a week after the game came out.

## Reverse engineering Dark Souls
In order to have the AI do anything, i needed to be able to feed it data about the game state. The simplest and most direct way of doing this is would be to have it watch various variables in the game code, such as the enemy's x and y location, and then use that with the AI logic. However, since the game's code isn�t open source, i needed to reverse engineer anything i wanted to use.

The first step i took was finding the basic variables i knew i needed, and were the easiest to find. By using a second computer, i could connect to myself and have a test enemy player i could work with. Using the program Cheat Engine, which is a powerful debugging and memory scanning software, i was able to quickly find the enemy's x and y location variables, and a few other simple values. Running a pointerscan on these values and cross referencing these scans, i was able to find the executable base address that the game always used for to point to the enemy struct, and the pointer paths to the variables.

Finding basic variable like this was trivial, but more complex ones posed a challenge. The animation state of the enemy's weapon, for example, took me a long time to find. I first tried going with the assumption (that i gathered from the debug release), that a float from 0-1 determined the progress through the weapon animation. After i failed to uncover its existence in the main game, i decided to try splitting the animation into various discrete states(windup, active, recovery, etc), and finding variables that indicated the activation of these states. However, the speed of the animations made it impossible to reliably step through them and consistently pick a point i believed could be separated into a unique state (for example, i couldn�t pause the game and scan for the change of a variable the exact moment the weapon's hurtbox activated), and external speedhacks caused the game to crash or the network connection to desync. Fortunately, digging into the debug exe revealed the presence of a game-internal speedhack variable, which i could use to slow down the animations to be able to step through them. However, i have to find a way to replicate this in the non-debug game, in order to find the valid pointer paths. Again, fortunately, i had access to a struct memory dump <a href="https://drive.google.com/folderview?id=0B_Und9n_kD1vN3lxelFJSnExbEk&usp=sharing">Birdulon (!!1Wl+k0u0T+Q)</a> had posted, and with that, after trial and error, i was able to find what value in the effects struct corresponded to the speedhack. With this, i was able to apply the speedhack to my test enemy player, and step through their animations, scanning for various states i assumed the game would track for it. This was the most time consuming part, because a lot of the states i had to hope or guess would exist, and i spent a lot of time parsing the possible results.
By far the most annoying part was finding a way to detect in advance when an attack's hurtbox would be generated. After countless searches for a countdown to the hurtbox turned up nothing, I resorted to using a timer that counts up from when the attack starts, and having a lookup table for every singe attack in the game, that returns at what time that timer generates a hurtbox.

A few situations also required me to read x86 assembly in order to better understand what the game was doing with a variable, or how it was handling a specific action. I also wrote some in order to alter the game's logic to help debug how the game handled actions, and i greatly thank the Cheat Engine forum users for having created injectable code i could learn from.


## Reading external process memory from C
After some research on how OS's handle process memory allocation, the process for reading the games memory was fairly simple. Find process, get process's base address, append it to the base address of all pointers, use the Windows API to read the memory of the base address + an offset(if a pointer), find its value, and in the case of a pointer, repeat by using this value as an address + another offset. Once this is done, you have the address of the variable you want, and can read data from it.

## Interfacing from program to program
I both wanted my AI to play with the same limitations a human has (not directly altering the game memory), and altering the game memory seemed pretty hard. So, I decided the AI would emulate a user interface device, which the game would then read. Because Dark Souls is commonly played with a controller, emulating a PS3 controller was the most natural method for this. Using a library called <a href=�http://vjoystick.sourceforge.net/site/�>VJoy</a>, I could store a struct of my desired button and joystick configuration in the code, edit it, then pass this struct to a method in VJoy which send it to the driver, which emulates the controller. Dark Souls then sees this, and I can control my character in game programmaticly.

## AI Logic (basic instinct)
Having played Dark Souls PvP for quite a while, i know enough about the combat to be able to distill it into the most important components. The most basic logic for the AI to follow is to dodge if it is about to get hit, and attack in all other scenarios (i guess you don�t really need to know Dark Souls to be able to determine this). However, this logic has a lot of edge cases and extra considerations to worry about. The first thing i did was get down a base framework for the basic AI that i could easily expand onto later. For every tick of the AI's main logic loop, i read the game's memory and parse the addresses i found into more usable formats, and stored them in a struct for each character. I pass pointers to these for pretty much all the logic methods.

The first logic method is to check if the AI is about to be hit. This was simple enough. By reading in the animation id of the enemy player, i have a lookup table that determines if this is an attack animation of not. Next, if it is, i analyze the "subanimation", or the current state their animation is in. If its in a state where their animation is about to trigger the hurtbox, i return that the AI should dodge (which allows me to perfectly dodge attacks). I also included a wait state for the AI, where if the enemy is about to attack, but its not time to dodge yet, the AI shouldn�t attack and lock themselves into that animation, but should wait instead. In all other cases, we don�t have to dodge.

If this detection method determines we have to dodge, i call the dodge method. This method does some detection on which type of dodge to use, depending on range and time remaining before hurt box generation. This then triggers a dodge routine, which finds the direction i should dodge (relative to the player's camera's current facing direction, which i lock at PI to avoid weird issues).

However, this dodge method and other actions i take in the game from the AI need to be remembered by the AI, so it knows that it either still needs to dodge or that its locked into an animation, on subsequent logic ticks. For this, i created an array of states i call a "subroutine" (this is actually a pretty bad name, I should have actually called them �metaroutines� because they run beyond one tick), which is set once a decision is made, and the AI checks every tick before it does anything to see if it should fall straight into whatever current subroutine it is in. With the dodge subroutine, once the dodge method is called, the subroutine state is set to dodge, and the next tick, the AI sees this and immediately calls the dodge method again.

Back to the actual logic itself, because i need the logic to perform different actions over a long period of time, and the subroutine ensures it will be called until it decides its finished and unsets the subroutine flag, i need a way to keeping track of how long the subroutine has been going on. By having a variable store what time the subroutine starts, then comparing that time to the current time, i can implement time based, FPS independent logic. For the dodge routine, it starts by angling itself in the direction it wants to dodge. After a few ms, it presses circle to start the dodge roll. Then, after a while, when the dodge finished (i double check this by looking at the game's animation state for the player), the subroutine ends and the method unsets the flag.

If the AI detects it doesn�t have to dodge, it goes into the attack method. Again, this takes an optional argument, discussed later in the AI Logic (Neural Network) section, which defaults to a basic attack in most cases. Attacking, for the basic logic, is either move towards the enemy if the distance between the two characters is greater than the weapon range, or perform a basic attack otherwise. Now, for people who play Dark Souls, this is where turtling or shields would be used. However, this is an AI, I can execute a frame perfect action 100% of the time. So, so I don�t have to worry about shields, I just have the AI do a <a href=�https://www.youtube.com/watch?v=VERHJsP_qOM�>ghost hit</a> whenever it does a normal attack, completely negating shields.

Finally, once all this is done, I call the VJoy method to send the controller actions to the driver, and then we repeat.

## AI Logic (Neural Network)
For anyone who's played Dark Souls, you'll know that the primary combat isn�t standard attacks, but the backstab metagame. This is a beautifully complex mechanic, which allows players to instantly damage another player if they manage to get behind them and close to their back. Unlike standard attacks, an AI cant dodge this very simply, because it is executed instantaneous, there�s no windup the AI can see and roll away from. The backstab metagame with humans revolves around identifying if a person is about to go for a backstab, then dodging it or countering it ahead of time. Unfortunately, even though I can easily identify backstab attempts when I play, I cannot for the life of me translate it into discrete logic. Its just something I know from experience, I cant really explain it. However, it is vital the AI be able to detect and dodge backstabs, so I needed to figure out a way to teach it.

Here is where neural networks come in. I wont be going into what a neural network is here, but instead over how I used them and what I learned about them.
Firstly, I played a few PvP games, while having a program listen and record various parameters. It stored these parameters in a buffer, popping on and off every 2-3 seconds, and when it detected a backstab, it recorded these parameters (distance, rotation, speed, etc), to a file.
Then, in my process of learning how neural networks worked, I wrote my own. Unfortunately, I never fully completed it because it was taking up a very large amount of time, and I wanted to get back to working on the actual AI, but the code is still in the project in a nearly finished state.
So, I used the neural network library <a href=�http://leenissen.dk/fann/wp/�>FANN</a> for the AI instead, because its better than anything I could write myself and my own implementation was taking too long. By training the neural network with the parameters I had recorded earlier, I was able to train a neural network that was, with surprisingly high accuracy, able to identify it an enemy player was going for a backstab 2-3 seconds in advance.
With this trained neural network, I then had to implement it into the AI logic. Because neural networks are not especially fast, and I wanted to optimize for speed as much as possible, I had the nets run in threads alongside the basic logic. For each logic tick in the main AI, after I read in the game variables, I update a memory backed struct with these new values, and wake the thread to start the neural network. It uses these new variables as inputs for the network, and when it finishes it sets a volatile variable with its outcome (i.e if it detects a backstab or not). This runs simultaneously with the main logic, and, for example, when that logic has finished checking if there�s any immediate attacks it has to dodge, it waits for the neural network thread to finish, and checks if it determined that backstab was incoming and it needs to dodge that. This thread-based method optimizes speed by running two independent processes, and allows for future handling variable time delays in the neural network, if, for example, I decided that I would start the neural network, then check on its result a few ticks later.
So now I have a method of detecting backstabs. How to handle them, however, is still an open question. Currently, I have the AI strafe around the enemy in the opposite direction of their movement when it detects a backstab attempt, which works really well for defensive measures. But, the AI currently has no logic to make use of this situation, and punish the backstab attempt, or do anything other that not get backstabbed. Figuring out how to have the AI play the backstab metagame, instead of just avoiding it, will likely be a very difficult problem.

I also have another neural network for attacking that, while currently incomplete, I want to be able to choose the optimal attack for a given situation. Currently, it just chooses the default attack if it is in range, and has the stamina to attack.

## Known Weaknesses
There are a few semi-important areas I have not yet programmed into the AI.

It is currently completely unaware of Poise, or the ability for an enemy, or itself, to not get stunned upon taking a hit. I haven�t bothered with this yet because I'm not sure how to handle it. What tactics should the AI take with high poise players? Attacking can lead to recovery that the enemy could use to retaliate with higher damage, so the AI would want to focus on exploiting their recovery frames(not implemented, see attack neural network) or backstabbing(see backstab neural network). This is probably the most important, and the easiest, next feature to implement.

Dynamic range, or if a player uses spears vs daggers. This is more of a bug than a feature, as I currently have the values hardcoded to an average range that works pretty well. However, to fix this bug I would need to have a list of all weapon ranges, and use the one corresponding to the enemy's current weapon, and I'm not looking forward to compiling that list.

The AI is WAY to likely to trade with an enemy attack, and likely comes out the worse for it. Again, this is an attack neural network problem, one that is likely to be worked on only by v2 or even v3. The major question here is, what does a human do to determine when they should attack? And how do they detect the enemy won't attack, and they're safe to go in?

There are plenty more area's I need to work on, but they aren�t as major as the above, and can be seen in the README file under TODO.

## Results
Well, how does it actually do?