Learning from the Hexenwood AI (and many more questions)

1

First off, I’m wondering if the developer, Bruno Albuquerque, is available for questions about the behavior patterns of the Hexenwood AI programming, because I have so many questions that I wouldn’t be skilled enough to answer from trying to pull apart the program language behind the scenes itself. If you visit this forum, Bruno, I would love to have a conversation with you!

On to my main topic… I believe Hexenwood itself is one of the best games on the system so far, but the addition of the AI functionality just puts it so many tiers above the rest of what we have right now! I love playing the game myself versus AI, versus my wife, and WITH my wife against the AI, but I have to admit that my favorite thing to do is to make various AI vs AI boards and scenarios and watch games play out.

While watching the AI, I’ve done my best to try to understand optimal strategies based on the behavior of the level 3 AI, and have tried to figure out what the AI considers the best thing to do in each varied scenario. The following observations are currently all based on the level 3 AI because I assume that Bruno programmed it with the most optimal (and thus most predictable) behavior, but once I get a better grasp of level 3, I’m curious to explore level 2 and level 1 to see how they vary. I assume that all 3 levels of AI probably include a few lines of code that allow for randomness, especially if there are multiple movement options that all have similarly beneficial outcomes, but I may be wrong there. At its core, I have to assume that most of the AI programming runs on some sort of points-based priority system where it maps out the beneficial outcomes of each potential next move on the board, assigns that outcome some sort of numerical value based on how beneficial the move is, and then chooses the action with the highest beneficial value… at least that is what makes sense to my fleshy human brain. I also assume that, at least with level 3, there might be some level of beneficial value attributed to what the AI assumes the nearby opponents next moves will be, but since this is more complicated and sophisticated, and since blinks don’t have infinite space for programming, I am less confident about this. I’m even less sure if each AI might start the game with some kind of variant “personality”–things like being defensive versus aggressive, for example, which could be totally randomly assigned at the start of game, or could even be assigned based on color. So far I haven’t seen compelling evidence to suggest such a “personality” feature, but I can’t say it is outside the realm of possibility. Anyways…

There are still many behaviors, especially during mid-game, that I can’t quite find a pattern for, but the early game seems to reveal a few more simple logic patterns. For example, when I create a game board where each AI starts with a single space equally far apart at the absolute edges of the board, the AI seems to consistently use “spread” moves to fill in all nearby available spaces that are available outside the current “hopping” distance away from the nearest enemy player. Once those spaces are filled up and two players are within “hopping” distance of each other, it seems like the first player that has the ability to “hop” and convert at least 2 enemy spaces will take that opportunity. After this point, all hell breaks loose and I’m less able to observe particularly consistent behavior patterns… so far. One thing that I do seem to observe is that the AI might place a slightly higher value on being able to possess board pieces that are on the outside edge of the board. This makes sense to me because those pieces aren’t at risk of being “hopped” over.

When playing with 3 or 4 AI players, I don’t think that each AI is sophisticated enough to calculate its moves against 1 particular enemy while considering whether counter-moves against itself are potentially unlikely because of threats on that enemy from other AI on a different front. For example, if Red was on the left, Blue was in the middle, and Purple was on the right, I feel like Red would not make a more “risky” move on its battlefront with Blue despite (to a human) Red having a very obvious move that needs to be made against Purple. I hope that makes sense if you think about it… but my point is that battles on separate fronts might be a place where the AI, no matter how “smart”, might act suboptimally compared to a skilled human player.

Finally, I get the feeling that the AI might not be programmed to recognize and exploit opportunities related to “walling off” parts of the board with a line of spaces at least 2-spaces deep so they can’t be “hopped” over. On a similar note, it doesn’t seem like the AI is able to anticipate (or at least doesn’t put priority in preventing) getting trapped in a corner and losing the ability to move on future turns. I may be wrong, but I feel like I’ve witnessed several examples where the AI takes a move that provides a numerically greater advantage on that specific turn, but by doing so allows itself to be locked in a corner and lose the rest of the game rather than taking a move which is less advantageous in the moment, but allows future movement opportunities. Once again, I’m no programmer, and I have NO idea what kind of programming complexity would have to be added to change this behavior, so I totally understand if this was unreasonable to program into the AI behavior given the space limitations… I just point it out as an interesting observation.

So in conclusion, what have I potentially learned? It seems that spreading, rather than hopping, is optimal for as long as possible at the start of the game, but hopping becomes by far the dominant strategy once players get within 2 empty spaces of each other’s territory, and throughout the rest of the game. I do believe that pieces along the outside of the game board are slightly more valuable than central pieces because they’re easier to fortify against being stolen later in the game. Other than that… I’m still learning!

I would love to hear the strategies and observations from others in this community, and hopefully you found this read at least somewhat entertaining!

2

Considering I replied to you on your last thread, I guess this is a safe bet. :slight_smile:

Ask away.

Here is a general summary of how everything works:

Level 1: Almost fully random except that it will never do I jump if it would not capture any enemy pieces. It literally counts all possible moves, then picks a random move out of those and if it satisfies the constraint mentioned, it will execute that move. Otherwise it picks another one. In other words, it is pretty stupid.

Level 2: Assigns a score to every possible move and picks the one with the highest score. In case of a tie, it will simply use the first one with the winning score. This is generally good, but will do pretty dumb moves because it would, say, get 2 enemy pieces just to lose 3 in a counter attack.

Level 3: Same as above but also evaluates all possible counter-attack moves for every possible move and adjusts the score accordingly (a counter attack score is computed as it it was the counter-attack player that is playing but its score is then subtracted from the attack score.

What you are seeing is a classic case of emergent behavior. Given a simple set of rules, you see seemingly complex outcomes. But yes, the Level 2 and 3 AIs prefer clusters and positions near the edge of the board, Level 2 AI is more eager to get opponents’ pieces which makes it more susceptible to counter-attacks.

Note that, in the end, storage and memory constrained a lot what I could do but the main issue was actually CPU. All algorithms have simple arrays as data-structure without any possibility of preprocessing optimizations so everything runs in linear time when looked at isolated but then you have to run it several times so actual time complexity ends up being exponential.

I actually have a better representation of the game map that would allow for all the map searching algorithms to be pretty fast (O(1) in most cases) but it does use a bit more memory. Enough that getting Hexenwood changed to use it and fit inside existing Blinks is a huge challenge. I guess I will wait form when the bigger Blinks start being shipped. :slight_smile:

1 Like
3

I also really like to just let some AIs battle each other. In m observation it always seemed like
Level 1: Pretty stupid
Level 2: very aggressive
Level 3: More carefull and therefore usually winning.

But I also had games when a Level 2 AI won because Level 3 was a little too carefull. And Level 1 seriously puts up moves like jumping to a spot they could have reached “going” so not losing the starting point. It makes sense now.

4

Level 3 AI will win most of the time against Level 2 AI. But there are indeed circumstances where Level 2 will win mostly because the decisions the Level 3 one do are based on attack and counter-attack but no moves after those. It might be that the next move would actually make the Level 3 move worse than it looked at first.

1 Like
5

My mistake, didn’t register that BGA was you! Egg on my face :stuck_out_tongue:

Thank you for the very human breakdown of how the 3 different AI levels work. It is very encouraging that I seem to have been fairly spot-on with my estimations since I’ve always considered myself pretty bad at trying to “think” like a program.

You actually answered a majority of my main questions, but I have a few more if you’re willing to indulge me.

  1. What features did you want to include but were prevented from doing because of the restrictions of memory space, programming speed, etc?
  2. What would you say was the most difficult part of programming the AI?
  3. Was creating the ability for the game to “map the starting board” relatively simple and something that could easily be applied for other programs, or did it take up a lot of memory? Wondering this one in particular for the game idea I’ve been working on in the background for a long time where I think I can program the behavior without specifically mapping the board, but might change the way I approach the design if mapping is relatively simple and not a memory-hog.
  4. Do you feel like your in-depth understanding of how the level 3 AI makes its moves has given you an edge against it in any way, or is it pretty much a perfect player in your eyes? At a high-level glance, it seems like it might be really hard to actually win against level 3 just because of the relative simplicity of the rule set.
  5. Is the core gameplay of Hexenwood based on a specific game that already exists? I was able to find a game with seemingly the same rules by complete accident while watching a review of an old DOS game that I played way back in the game (the honeycomb puzzle from 11th hour) but I wasn’t sure if this was a coincidence or not. I have to imagine this set of rules is probably some well established board game that has been around for a long time, but for the life of me I haven’t been able to google my way to that answer!

Thanks so much for your time and your awesome game!

6

There are only a few things I was not able to squeeze in:

  • Self-destruct mechanics. A player would be able to self-destruct one of its pieces on their turn instead of doing anything else. Self-destructing results in the piece and all pieces immediately around it (friend or foe) exploding. This might be specially useful in later stages of the game but its effectiveness is limited and only makes sense in very specific scenarios.
  • Stop game on piece removal. Currently if you remove a piece of the board, the position it should be reattached to starts blinking but, other than that, the game can still be played (and would result in inconsistent state). Corner case but one that would be nice to have.
  • Smarter AI. The AI is memory and CPU intensive and making it smarter with the current approach would not work. In fact, the level 3 AI is pretty slow in big boards near the end of the game.

I actually had to write my own Blinklib to make the game possible. 2 main reasons for that:

  • Original Blinklib has no guaranteed delivery of datagrams. Hexenwood uses datagrams a lot and it can simply not work without guaranteed delivery.
  • Hexenwood is big for a Blinks game. I needed as much space as I could get. My custom Blinklib uses considerably less storage space than the original one (enough to move Hexenwood from unlikely to possible) without losing any features.

Other than that, I also had to write my own approach to broadcast messages (that relied on guaranteed delivery of datagrams).

It uses considerable memory (RAM), yes, but it is proportional to how big you need the map to be. The code theoretically supports boards of up to 256 Blinks. You can tweak this.

Kinda. I am usually spot on on figuring out the move the AI will make but I am not that good at making use of that to trap it into doing something. I win some, I lose some. :slight_smile:

The game is a from-scratch reimplementation of The old Hexxagon DOS game (There is an online version of it: https://hexxagon.com/) for Blinks. Hexxagon is, in turn, based on an even older game called Attax (Ataxx - Wikipedia), Standing in the shoulder of giants and all that. :slight_smile:

1 Like
7

And I realized my previous answer to this was about Hexenwood in general and not about the AI in specific.

The AI required me to come up with a way to create a board map (propagating all positions is non-trivial for Blinks due to how they work).

Once I had that in place I needed a way to be able to “remote control” Blinks in the board (funny enough, thinking about the answer to this led me to think that I can simplify things a bit in this logic and maybe save some space by having a single command, “click”, instead of the 2 I use).

I also needed to come up of a way to upload the map to newly connected AI Blinks so they can added/removed from the game at will.

1 Like
8

Wow, I really appreciate all of the feedback you’ve already given me in this thread. It is a bit intimidating realizing how much more I’ll have to learn to get my own game prototype into even somewhat functioning form one day, but I’m also re-energized to pick up that project again since it has been sitting on the backburner for a solid 10 months thanks to my crazy workload as a pharmacist. The effort of vaccinating so many people for covid has been no joke, I tell ya what. Thanks for all the info, and I hope that I can reach out to you again in the future!
Random thought… I don’t think I’ve seen you in any of the youtube Blinks livestreams where they talk to the developers in a more long-format video. Have you been in one and I just missed it? If not, have they approached you at all for the opportunity? I would really love to watch a video where you can share your thoughts on the game, your process, and advice for future Blinks game makers, especially since yours is the only game with AI so far!

9

Hexenwood is a complex game but a game does not need to be complex to be fun and that is all that matters in the end.

And yes, if you have any questions, ask away.

It was with all developers behind the Sakura Pack tough.

1 Like