Building Camelot the Build #4
So there’s been a bit of a break with the dev blog entries lately. My reasoning is I’ve been reworking the AI from the ground up- and as I’ve talked about a lot of what I wanted to include in previous posts, I didn’t really want to repeat myself. Especially because it’s very difficult to show you the AI changes in visual form.
So in the last post I ended up with a semi-competent AI that was perhaps passable at best. Not really good enough. Also it was slow. Too slow. It paused the game while it thought, even on the PC version- and the sheer amount of calculations it had to do meant it would be a very tricky convert to mobile devices.
So I re-built everything from the ground up, with the aim of not only making it better, but making it much, much more efficient. I’m happy to say I’m 90% of the way there now- I’ve got a much more functional AI which is fast and most importantly, doesn’t pause the game and can run on mobile platforms! At the time of writing there are still some bugs to sort out regarding garden tiles and the end game, but I’m confident I can tackle these.
So for the really hardcore development fans out there- in the rest of the blog entry I’m going to post my detailed explanation of exactly what’s going on with the AI:
So when the AI begins it’s turn it starts to run through each possible combination of tiles it can lay in every position. This is often a huge number- especially at the start when it can be in the region of 20,000+ different combinations depending on what tiles it has. That’s why in the first iteration the game paused for a while processing them all.
So to get around this I’ve made it more efficient by giving it some basic rules to cut down the number of calculations it should proccess. If there is between 95-40% of the game left the AI will only anylise plays which are next to existing placed tiles. This cuts down on the combinations a huge amount. When there is 40% of the game left (60% of the tiles have been placed), the number of different combinations across the whole board is managable.
When the AI has gathered all the combinations of plays it can make, it has to rank them. It basically just puts all the combinations into a list, assigns them a score, the combination with the highest score is the one played.
This is currently how it determins the score:
((total tile score * tile multiplier) + (adjacent score * adjacent multiplier) + (double score bonus * double score bonus multiplier)) * scoring multiplier )
– ((total tile potential * potential multiplier) * (1 – game completion percentage/100))
– (next player scoring opportunity * next player multiplier)
– (2nd next player scoring opportunity * 2nd next player multiplier)
– (3rd next player scoring opportunity * 3rd next player multiplier)
+ (play blocking value * play blocking multiplier)
= ranking score
Here are the variables explained:
Total tile score; the total red score from just the tiles in this combination.
Tile multiplier; a variable we can use to tell the AI how to value the score on the tiles. In testing I have this at 100.
Adjacent score; the total points from adjacent tiles this combination gets.
Adjacent multiplier; a variable we can use to tell the AI how to value points gained from adjacent tiles. It’s useful to have this high compared to the others so it chooses ‘good value’ plays. In testing I have this at 300.
Double score bonus; the score multiplier that is applied if the combination features 3 end to end tiles. This is actually just 0 or 1 * the existing combination score (seeing as you either get it or not).
Double score bonus multiplier; a variable used to tell the AI how to value the double score. I’ve got this set at 100 in testing.
Scoring multiplier; a variable used to tell the AI how much to value scoring points. This is like a master variable for all of the above.
Total tile potential; because certain tiles are more ‘valuable’ than simply their score in red, I’ve implemented a variable (unseen to the player ofcourse) to determin the scoring potential of a tile. Without this the AI would just play garden tiles like they were wall pieces for example.
I’m still experimenting with the rankings, but they are supposed to represent the maximum scoring potential of the tile in relation to how common they are, and their positioning on the board. Here they are currently:
2 pnt corner- 10
3 pnt corner- 15
Blank wall- 0
Blank ground- 5
Garden- 100
1pnt wall tiles- 0
Scriptorium- 30
Round table- 50
Goblet – 50
Chapel – 40
Small Halls – 20
Great hall corner- 10
Great hall wall- 10
Uther Pen Dragon- 30
Dragon Banner- 40
Throne- 40
Excalibur- 50
Fireplace – 90
Wall inside corner – 5
Gates – 10
Furthermore though, I found this value needs to be less important as the game goes on. This is because at the start of the game every tile has it’s biggest chance to achieve it’s maximum scoring potential. As the game goes on it becomes less relevent, because as the tiles are filled in the chances that a tile can achieve it’s max scoring potential is reduced.
So to reflect this, I’ve made it so this value becomes less important in the equation as the game progresses like so:
Potential multiplier; a variable used to tell the AI how to value the potential. I’ve got this set at 60 in testing. I could just set the above tile rankings lower, but this allows me to easily adjust them all while keeping their ratio to each other the same (which is the important part).
Next/2nd Next/3rd Next player scoring opporunity; The AI will look at the hands of the following players and anylise how many points they can score from the current combination, if placed.
Next/2nd Next/3rd Next player multiplier; I’ve got a seperate multiplier for each following player here. I’ve given a higher weight to the immediately following player, with quickly declining weights given to the others- as obviously at this stage we don’t know what will be played inbetween those turns. In testing I’ve got next player at 100, 2nd at 50, 3rd at 20.
Play blocking value; This is how the AI attempts to block high scoring plays. It looks at the hand of the other players, and generates a ‘heatmap’ of the remaining board. This heatmap represents possible high scoring plays for the other players. The value on the heatmap for the spaces in the combination is added to the ranking. It’s still quite a basic representation of the opponent’s high scoring tiles- it doesn’t take into account most of the variables above as this would require anylising through up to 3 turns worth of additional combinations.
Play blocking multiplier; A value to tell the AI how much to value play blocking. I have this at 160 in testing.
So that’s a detailed breakdown of how the new AI works. It might be hard to get your head around but I figured I might as well share this with you guys if you wanted to try!