this post was submitted on 17 Jan 2024
38 points (93.2% liked)

boardgames

5853 readers
2 users here now

Everything boardgames

Please stick to English for posts and comments

founded 1 year ago
MODERATORS
dpunked@feddit.de
pathief@lemmy.world
38
Azul: I wrote a program to calculate the optimal 17-move placement: 113 total points (lemmy.world)
submitted 10 months ago* (last edited 10 months ago) by dragontamer@lemmy.world to c/boardgames@feddit.de
5 comments fedilink hide all child comments
 

  • Move 1: 1 point
  • Move 2: 1 point
  • Move 3: 4 points
  • Move 4: 4 points
  • Move 5: 1 point
  • Move 6: 1 point
  • Move 7: 4 points
  • Move 8: 1 point
  • Move 9: 4 points
  • Move 10: 6 points
  • Move 11: 7 points
  • Move: 12: 8 points
  • Move 13: 7 points
  • Move 14: 7 points
  • Move 15: 7 points
  • Move 16: 7 points
  • Move 17: 7 points
  • Endgame Bonus: 10 + 10 + 7 + 7 + 2 == 36 Endgame Bonus
  • Total Score: 113

Note that while this is "optimal" placements, it is not the best sequence in-game. For example, sequence 8, 9, 10, 11, and 12 are going backwards. I'm not sure how to rewrite my program to account for the top-down placements per round however. So there's still work to be done.

This was a relatively simple brute-force bot that exhaustively checked all possibilities for the best possible placement. So I'm pretty sure I've go the best placement here. Well, maybe it was more "Dynamic Programming". I worked backwards: I calculated all possible 17-placement endgames (there's only 1.081 million of them, aka 25-choose-17), and then back-calculated all possible moves back to move#1.

Then I calculate from move#1 forward, choosing the best endgame move now that all possible endgames have been searched. Chess-programming fans would know this as a "Tablebase" approach.

EDIT: Searching the ~60 million possible optimal games proved to be difficult, as my computer ran out of RAM at 2GB (ummm... I got a 32GB system here. WTF Windows?). I'm sure there was some compiler flag I messed up on.

But I did a few heuristics and came up with the following board:

This is a 17-placement across 5 rounds with as many placements on the "top" of the board that I could find with my program.

EDIT:

  • Optimal 11 Placement: 58 Points
  • Optimal 12 Placement: 63 Points
  • Optimal 13 Placement: 73 Points
  • Optimal 14 Placement: 82 Points
  • Optimal 15 Placement: 91 Points
  • Optimal 16 Placement: 99 Points
  • Optimal 17 Placement: 113 Points
  • Optimal 18 Placement: 123 Points
  • Optimal 19 Placement: 136 Points
  • Optimal 20 Placement: 147 Points
  • Optimal 21 Placement: 163 Points
  • Optimal 22 Placement: 174 Points
  • Optimal 23 Placement: 192 Points
  • Optimal 24 Placement: 211 Points
  • Optimal 25 Placement: 240 Points

top 5 comments
sorted by: hot top controversial new old
[–] Wojwo@lemmy.ml 6 points 10 months ago (2 children)

But that's not playable, right? I'm trying to play out in my mind what tiles have to be selected on the left to get that pattern, and it not really working in my head. Full disclosure there's some whiskey up there to.

[–] dragontamer@lemmy.world 4 points 10 months ago* (last edited 10 months ago)

Its theoretically playable. But 8, 9, 10, 11, and 12 is basically never going to happen. I'm trying to figure out how to optimize my program for "more playable" sequences.

Surprisingly: the sequence 1 2 5 6 8, 3, 4, 7, 9 is playable and score-wise optimal still. So with a few reorderings / better search, I probably can find a "reasonably looking" sequence for a real game.

Still, solving this "subproblem" is likely news for many Azul players. I believe I'm the first one to find a provably optimal sequence of plays for a given target number of placements.

[–] dragontamer@lemmy.world 4 points 10 months ago* (last edited 10 months ago)

I didn't try very hard to find the best sequence yet, but this is much more playable.

I'm currently estimating about 62-million sequences that are optimal. I'll likely have to search all 62 million of them to find the "most playable" optimal 113-score game.

This is still small enough to brute force on a single-core in a few seconds. But I'm too tired to keep programming today.

This above sequence is theoretically possible in 6-rounds of play.

[–] betabob@lemmy.dbzer0.com 3 points 10 months ago (1 children)

As mentioned, the first outcome would end the game in turn 14 and also be impossible to place in the first phase of the game. The second solution comes closer but weighs heavily on getting two tile types to get there.

I just got the game and have been loving it but there are many more variables to solve this. Some examples are: group size, and random tiles drawn.

[–] dragontamer@lemmy.world 3 points 10 months ago* (last edited 10 months ago)

I've added a new placement based on a few more heuristics.

The newest placement is theoretically possible in 5 rounds, creates the maximum 113 score, and is biased to have as many placements as "high" up as possible (row1 favored most, row2 next favored, etc. etc.)