

The moment I saw the problem I started coding :-)


Rather than brute forcing all possible permutations, we start from all possible final states and BFS backwards towards starting states. There are probably tons of opportunities for further optimization, but this takes ~800 ms on my desktop, and it only uses one core. We don't need to track the number of turns required to end each state, since the frontier will always consist of games which require the same number of turns to end.

Edit: Shrinking my data structures dropped runtime by 50%, and easy & cheap parallelism dropped runtime by another 75% on my four-core desktop. New runtime: 110ms (Intel i5 6600k). The key to the parallelism is that since the total amount of money never changes, we can assign a different total amount of money to each thread, and they'll never have to search the same states.

Hah I knew there was a better way to solve it! I was sort of sick of the problem by this point and didn't feel like picking it up again :) Glad to see someone else found it and implemented as well and proved that it produces a much faster calculation.

I added this at the end with a link to your solution and your post. Honestly I never expected this post to make it to the front page so thank you so much for taking some time out to do so.

Trouble sleeping, so... rev #3: tighter packing of states -> ~25% run time reduction.

Wow, this is beautiful C++ code! High level abstractions, not hiding any of the nitty gritty details, parallelism and all, yet very readable. Well done!

I felt the same - not that worse than in a modern language (of course someone should rewrite in Go with the new algorithm so we can decide if it would be good enough :)

Before I read the post I thought how I would solve it. Dynamic programming starting from end states should avoid lots of redundant work. Also making sure to sort the players by money, to reuse symmetries.

I feel retarded now. So if the players are randomly chosen according to the rules, doesn't that change the possible solutions?

Edit: Is it because each solution must take into account every possible permutation of gameplay?

A solution is "no matter what randomly happens, the game will last at least 12 turns".
