The Smash the Code AI Contest ended this weekend. You had 8 days to code the smartest AI on a Puyo-Puyo-like game. This edition was also special as we introduced a new league system (no need to say that we had a bit of an adrenaline rush before the launch :)).
PODIUM & RANKINGS
The contest was inspired by the Puyo-Puyo game in a 1 vs. 1 version. Each player was in charge of a grid and had to stack up blocks composed of 2 pieces called “puyo”, for which the colors are aleatory. It’s possible to make the “puyos” disappear by grouping them by 4 or more puyos of the same color.
1. The brute force strategy: simulate all the possible moves on several tours.
2. The aleatory strategy:
Due to the important number of combinations, several players set out algorithms based on aleatory strategies (Monte-Carlo or Monte-Carlo-Tree-Search for the majority) and could therefore explore solutions up to the 8 next blocks. The whole subtility of the game was to be able to maximize it’s own combo and making it explode before it’s opponent.
- I calculate the “score to kill”. It is the “one shot” score minus one line (and modified by my current nuisance)
- I calculate the “score to be safe”. I check out the greater gap between two columns on my opponent grid. The score to be safe is the amount of needed lines to fill that gap.
- I calculate a floor combo score. This is
- Every group of 2 balls is 2 points. Every group of 3 balls is 6 points.
- Every ball touching an empty cell add 1 point : This one is important because you want to access many ball as fast as possible
- A late one : Every ball touching another ball (except a skull ball) is 0.2 points by touching balls. With the previous one and this one, your AI will try to build towers. This is the best way to be “skull proof”.
- If your combo is above the kill score, set it to the kill score. Don’t waste your time by building too big combos.
- If the combo is too small, ignore it (like said above)
- To force my AI to not seek for a better combo every time she see it, i use a “patience” term. My patience term is 0.7
100*0.7^0, so 100 points. But if i can win 500 points at the turn 2, my eval function will returns
500* 0.7^2. This way, my AI will prefer a combo now than a bigger combo in 5 turns.”
Basic simulator here, find out how much points I’d get for a particular move
each group of connected n ball is given n² points (so 1, 4 or 9).
After the score heuristic is done, post-simulate with a vertical mono-colored block, for each color and each column (total of 30 to test) – and get the biggest score!
If the combo heuristic of my opponent is tingling my AI, my own combo heuristic score will decrease so only score&connection heuristic remains, to flavor immediate action rather than build up and waiting for the correct piece to come up.
- Exhaustively bruteforce the opponent moves with a depth of 2, to detect danger (combos that will send at least 2 lines of skulls)
- Run the simulations: pick n moves randomly, and play them to see if I can find a combo. Repeat until the 100 ms are spent. “n” is picked dynamically: I use a 8-steps depth most of the time, but reduce it to 6 in the end game (as it makes no sense to search 8 move ahead when the grid is almost filled, I prefer to reduce the depths and increase the probability to find a short killer move). I pick the best moves based on the score: best move one turn ahead, best move two turns ahead, best move three turns ahead, etc… If for the same depth I find two moves with the same score, I use two other criteria for the choice: 1/ the variance of the height of each column (so the AI will try to build towers), 2/ I try to make clusters of 3 colors).
- When the simulations end and I have the best move for each depth, it’s a matter of deciding on how many turns I want to play:
- If the opponent is going to make a combo in the next turn or the turn after that, I pick the corresponding depth
- If there is a combo with more than 1500 points in the next 5 turns, I pick it
- Otherwise, I use a “patience” term (as perfectly explained by Magus) of 0.4 (lowered to 0.2 in the end game, when my AI is just trying to survive)
+1 for each group near another of the same color (the big timewaster I couldn’t get rid of)
+1 if it’s also above said group
-15 if the group has no available open spaced adjacent to it
-2 if the group size is 1
I also looked in that direction and found that page with a few good hints on the matter:http://www.cs.columbia.edu/~evs/ml/MLfinalproj/suk/genetic.html
- The league system: 80% of you were happily surprised by the league system and 10% expressed no opinion on this question.
- The rules changes: 73% of you are happy with the rules changes, even though some of you would like to know them before, just to avoid producing a piece of code that cannot be used in the upper leagues.
- The game on itself: 83% of you had good fun playing at Smash the Code 🙂
- The ranking system: One of the main concerns was about the ranking system. We’ve reviewed all your feedback and are looking for ways to improve it for the next edition.
- Chat: We received several requests to improve the chat system, in order to be able to better interact with other players. We also think there is room for improvement on this side, so keep tuned on this topic! 😉
- Sharing content: A few days before the contest, we decided to share a video of the game on several social media, which probably wasn’t the best idea as it provided some information that could allow some of the players to start thinking about their strategy before the contest launch.
Thank you again for your participation and we hope you see you in the next one: Codebusters!