3+ players
My final strategy was to have a list of squares I could reach before anyone else and then try an x first and a y first elbow to each of these positions (idea from Magus). These are then ranked by:
- Squares taken
- Efficiency (squares/turns)
- Voronoi of next square in the elbow
- Voronoi of last square in the elbow
These elements are used to compute a score with a linear function and the best is picked.
Voronoi: What is meant by Voronoi is the number of squares I can reach before anyone else in a given situation. For example when considering an elbow to a location and having to decide if I will go x first or y first the one that gives the most voronoi for the next square will be picked. This leads my bot to color squares closer to other people first, thereby making quite a literal wall dissuading everyone from coming to my area. The Voronoi of the last square also has some importance because you want to go towards a place where you have as many options as possible afterwards.
Linear Eval: In the begining I had if else rules with priority on efficiency then squares then Voronoi… but I found that a linear function was much better because your bot is then willing to sacrifice some short term efficiency for better future plays (Voronoi).
Updating the Target: In what I have outlined above a target is picked and then it is followed untill completion. What improved my play alot was to every turn scan for better elbows when I was doing an elbow with efficiency higher than 1 (completing a rectangle). This was done by looking for an elbow which would give better efficiency. This regularly lead to bigger non-rectangular areas and improved ranking noticeably. When doing an elbow to close a rectangle I was also scanning for corruption of the rectangle by ennemies, if it was corrupted pick another target.
The coefficients in the evaluation were different for 3 and 4 player games.
Endgame
If there wasn’t a single square I could reach before anyone else I had a primitive backup AI that would go to the nearest neutral cell with a tie break on the Voronoi, this was the behaviour in the endgame where there are a few neutral cells here and there, or on the first turn of a game where everyone starts on the same cell.
Back in Time
When a back in time from another player was detected a new target was computed to avoid crashing. I didn’t use BIT myself though I experimented with it a bit, I think this game is 99% about your moves and using Back in Time is not a priority.
2 players
I used Minimax with alpha beta pruning and an evaluation function built of squares owned and Voronoi in a linear fashion (idea from Magus). This leads to wild behaviour compared to other AIs but it performed quite well and 1v1s wern’t very important for ranking anyway.
Improvements: I think the fundemental workings of the AI, thinking with elbows, is flawed and should be replaced with scanning for rectangles for example. I think the Voronoi ideas are pretty solid but may need refinement and some way of finding the best coefficients.
Final Rank: 91 (~60 in multi without changing code)