Well, it is currently a proof of concept and has lots of bugs (you can see it doing an illegal move in the video below and getting the game into a weird state) but it mostly does what it is supposed to do?
It uses a very simple heuristic though. It looks at the game map and selects the first valid origin it can find. Then it searches it again and selects the first valid target it can find. So not only you can predict what it will do with 100% certainty (except for the bugs, of course), it does some pretty bad moves in general.
Next step is just fixing the bugs and then implementing some real heuristics. Maybe even allowing to set how smart it is.
And, BTW, you can have multiple Ai blinks connected as long as they control different players. Connecting 2 Blinks that control the same player might result in completelly chaotic behavior.
Now I have 3 different AIs (and a level selector!) each AI is a single difficult level.
Level 1: Completely random moves. It just searches for all possible moves and then picks one of them at random. This is still pretty stupid but at least it is better than always picking the same move method of the previous iteration. This should be pretty easy to beat for anyone.
Level 2: Conditional random moves. It still picks up random moves but only those that are not completely terrible. This mostly means that it will always either move a single space (so no jump) or will jump if it can capture at least one enemy position. Other than that, it will still do pretty bad moves as it will pick the first move it can find that satisfies the conditions even if there is a better one. Still should be pretty easy to beat but it is definitely harder than the purely random one.
Level 3: Scored moves. This is where things start to get really challenging. Now the AI looks at all possible moves, scores them and picks the best scored one to do (or randomly one of several with the highest score). The score is currently based on several variables that i will not mention now to not spoil the fun, but this should give a pretty good challenge even for experienced players.
I intend to try to add one other level where it will also look on possible counter moves and factor that out in the scoring. The idea is that it would not do a move that looks pretty good in itself but results in possible counter-move that would erase any gains.
Other than that, ideally I would implement some version of a Monte Carlo search or MinMax but that would mean using recursion and I am already using most of the available memory for other things. I might try to implement it anyway but I suspect that if it works, it will be severely limited in how many levels of recursion I can use). Doing this would allow the AI to pick the best move not only based on the current board state but also based on future possible moves.
Still, before doing the above, I will clean everything up and put it in a shipping state. Hexxagon itself will also need some changes not present in the current version.
So now I am at a state where I can play several games without issues and I started playing against the Level 3 AI. Well, either I am actually a bad Hexxagon player or I guess I do not need a higher level one. I mean, I lost 10 out of 10 games against it even knowing what it was doing (I programmed it after all). I guess I will upgrade this to be level 5 and then make levels 3 and 4 be a mix between the conditional random move and this one (maybe pick one with a certain chance at each turn).
Still, even losing it was fun to play against it.
BTW, interesting fact: Due to the nature of Blinks (specially the available memory), we can not really use any advanced data structures due to their memory overhead so all map-related heuristics end up being O(n) in time or worse. Still, even in the current Level 3 AI, plays are computed really quickly in a 12 Blink board and I expect it not to be too bad with the maximum of 84 Blinks (yep, I needed a couple of bytes of extra memory and had to decrease the maximum number of allowed Blinks by one). Even if it is, the code uses iterators over the map so I can actually look at a part of the map, return form loop, look at another part, return from loop and so on, so I can always make the animations be smooth even if the algorithms are complex.
