Tic-tac-toe Collection
Blog Other  

0.20.1 includes updated logic for “fairness calculations”. This has already been pushed for the server so this is in fact available in all versions when running with cloud simulation enabled.

This came about mainly because of my efforts to try and generate interesting game settings. My idea was to sort all the setting combinations by fairness, generate new ones based on them (via some minimal genetic algorithm), and then repeat until some good results fall out.

Early attempts

My first attempts did not work well. The game simulation works by playing a few turns using the normal AI, and then seeing what it thinks its chances of winning from the current position are. I defined “fairness” as: take the chance of winning of the best player and the chance of winning of the worst player, and then calculate the ratio of the two. Here are some of the types of games it generated at first:

  • Games with lots of players. Since nobody can win, it is perfectly fair.
  • Games with a win line that is too big to reach.
  • Games with a target score that is too big to reach.

Early fixes

I fixed some of it by doing some basic processing on settings before simulating. If the winline won’t fit, or there aren’t enough unique winlines to achieve the target score, I just reject it. Also, for now, I limited it to just two players.

The results were better, but basically just a more complex version of the above: games in which the AI did not manage to actually achieve a win in its simulations.

Refining the AI

One possible problem I identified was that the “chances of winning” calculation isn’t really about winning. It’s actually a kind of fuzzy number combining winning, and tying for first. In this case, tying for first is something I want to avoid. To fix this I parameterized the core AI engine, so the way it assigns a score to outcomes could be varied. There were initially two options:

  • Original AI: Winning scores 1, tying for first scores 0.5, everything else scores 0
  • “Win only” AI”: Winning scores 1, everything else scores 0

This means I can now look for games that have a high fairness, and a reasonably high chance of actually winning a game.

First derived game mode

Final updated AI

Separate to my goals of generating interesting game modes, I also took this opportunity to actually improve the AI. For games with more than two players, the (normal) AI now takes into account relative positions. So, for example with three players the following outcomes all have unique scores:

  • Finishing first, with no ties.
  • Tying for first.
  • Finishing second, with no ties.
  • Tying for second.
  • Finishing third.

This hopefully stops the situation in which multiplayer games ends up with several of the AIs “giving up” since they’ve determined they can’t possibly finish first.

Saturday, April 4, 2020 Sat, Apr 4, 2020 04 Apr '20
Technical