1 Trillion Accordion Solitaire Solves

Accordion is an interesting solitaire game which is quite difficult to win as a human even though almost every deal is winnable. I built a solver that plays 6 million games per second which found to my knowledge the first randomly dealt unsolvable accordion solitaire deal. This ground breaking research shows that a little under 1 in a billion deals are unwinnable. 

What is Accordion?

Accordion is a solitaire game where the whole deck deck at the very beginning of the game. The goal is to collapse matching ranks and suits into one pile, this is quite challenging because its very easy to get stuck without matching cards at the end of the game. Full rules can be found here. 

I've been playing accordion casually on camping trips for several years, I like it more than most solitaire games because its very strategic and very difficult to win. Some blogs claim human win rates of 98-99%, but after a few dozen games I still only win a little over half the time I play. 

Human vs compute accordion 

In the early 2000s, Mark Masten's solver won 30 million out of 30 million random deals, and the Solvitaire paper from Blake and Gent estimates 99.99948% of deals are winnable. 

I vibe coded a program that solved randomly dealt deals faster than anyone has before, peaking at around 6 million deals/s. After playing 1 trillion deals over a few days, the program found 721 unwinnable deals which were shown to be unsolvable with Lean proofs. This is win rate of 99.9999999279%, about one unwinnable deal in every 1.39 billion has no solution. 

Play it

An interactive version of the game is below, you can also play the game on its own page. Type 112249515 or 202346720 into the seed box for examples of unsolvable deals. 

Seed

Right click leaps

Moves

How the program works

Brute forcing a normal deal is unrealistic, there are something like 10^17 reachable positions. Even at the GPU's ~3 billion positions per second that's roughly a year per deal, and you'd need hundreds of petabytes to remember which positions you've already seen. 

We are fortunate however, that the deals which cannot be won are also the deals that have fewer available moves, and can be searched exhaustively. The 721 unsolvable deals we found have between 2 and 22 million reachable positions, which takes under a minute to search on the CPU. 

To solve the other 999999999279 I used an improved version of the strategy Masten figured out back in 1999. The program the first ~40 moves semi-randomly, brute forces whatever is left, and repeates until something wins. 

The GPU finds almost all of the wins but it doesn't get to grade its own homework, the CPU replays every winning line to double check.

The first unsolvable deal

Seed 112249515 is the first unsolvable deal I found. From a first look, the deal doesn't look stuck. You start with 14 legal moves, 11 of which keep you on track. But playing out all 110,959,471 legal moves, the best you can end with is 2 piles: an 8♦ and a 9♣. There is no easy intuition for why this is unsolvable, the way the piles work out there is no way to get a shared rank or suit for these last two cards to line up. 

Others like seed 124280819596 are much more obvious, this deal only has one legal move!

Program details

The first commit was at 10:30pm on November 3rd. The next morning the solver could win whole deals at ~3,000 deals per second. 4 days after that it's at 6.09 million, ~2,000x faster on the same laptop, Claude was actively working on speeding up the solution for ~59 hours shown below. I think more speed is possible, perhaps with an extremely bare bones neural net running on the GPU, but as shown on the graph my current strategy was reaching diminishing returns

Solving speed against hours Claude was speeding up the program with constant prompting and suggestions

All of this ran on my laptop: an Intel i7-1260P (16 threads), 48 GB of RAM and an entry level Nvidia T550 with 4 GB of memory. As I'm currently living in a hotel room in Memphis, I balanced the laptop on a stack of plastic cups and a trash can to get the AC to blow air into it. This worked to a point, my 65W charger became the limiter after this. 

Better cooling increased solving speed by ~10%

Much like with other projects, I found Claude was incredibly good at implementation but not great at overall strategy. The majority of the ideas around speeding up the implementation came directly from Claude, it realized the memory limitations of the GPU and figured out how to optimize it. Claude rarely thought of strategy improvements though, stuff like implementing dead end tests and making the prefix of random moves less random were both ideas I had to prompt. Similarly, Claude kept trying to make the CPU faster even when the GPU was the bottleneck and already solving 95% of deals. 

Speed increases that worked

• The CPU solver, which went from 2,952 to 14,805 deals/s (5x) in one go:
  • Restarting searches more often, basically giving up on brute force and playing a new random deal earlier 
  • Skipping move orders that lead to the same place
  • The 11 pile endgame lookup table: once a game is down to 11 piles the program sees if the leftover pile matches a permutation of the winnable deals at 11 piles instead of brute forcing the end. This was not feasible on the GPU with memory limitations, and not easy to expand as 11 piles was already >1GB
• Adding the GPU: only ~1.4x at first, but it ended up doing almost everything
• A better dead end test that uses the fact that the leftmost pile never moves: 1.48x
• This check is looking for if there is ever a connectivity failure, if the deck is split into two halves that don't have any overlapping rank/suit cards you might as well give up now because there won't be a solution
• Connectivity also cannot be through the card in the 0th pile, that card can never leap or slide onto another card
• Rewriting how the GPU works through attempts >2x speed increase
• Splitting semi random deals in the prefix out from the brute forcing deals
• The win here is the jobs can be parallelized much easier, the prefix will always be the same number on instructions and can much more easily be split into warps 
• Also minimizing memory usage on the GPU and keeping as many deals as possible in shared memory helped a lot
• Making the random moves less random, 
• The brute forcing starts with 16 piles leftover, it took ~400 of these attempts to solve with a random prefix, and a strategic prefix took this down to ~5
• Making leaps 8x as likely as slides, this tuned ratio performed the best
• Mining won games for what good moves look like, the best strategy found here was preferentially removing ranks whenever possible 
• Cheap lookahead at move 27 to make a better deal for the real brute force
• Scoring moves with bit patterns whose weights were tuned by actually playing. This is the closest to neural net black magic, the program is just statistically choosing tuned patterns and playing them without any intuition or understanding 
• Preparing batches ahead of time on the CPU so the GPU never waits: ~2x
• Better move patterns, a cheaper win check and queueing 3 GPU launches at once: ~1.35x
• A long tail of small tweaks worth 2-10% each
• Retuning search depth, prefix size, prefix vs brute force split on the GPU after other improvements

What did not work

• Caching positions in the 12-16 pile range: ~40% slower
• Putting the endgame tables on the GPU: 23-31% slower at every size, even though each lookup was almost free
• A version of the GPU code that doesn't shift cards around: that part got 30% cheaper on its own and the whole thing got 13-20% slower. We never fully figured out why
• Another dead end test called the left leaf test: removed 5-9% of positions and cost more time than it saved
• Searching the most promising positions first: 0.4% to 36% worse
• Skipping positions with only 1-2 legal moves: doesn't pay, they're cheap to search and sometimes win
• Shrinking the GPU code with loops and function calls: 3-14% slower

How much of this was Claude?

All of it. All 72 commits are coauthored by Claude (67 with Opus 5.5, 5 with Sonnet 5.5). That's ~19,000 lines of Rust, ~3,000 lines of GPU kernel, ~5,500 lines of Python, ~900 lines of TypeScript and ~800 lines of Lean, plus the research, benchmarks and documentation. I didn't write any of the code.

My part was setting the goal, pushing ideas like the game mining, telling it to question its own assumptions, and letting it run on its own for long stretches with multiple agents. It measured its own ideas and threw most of them away. At one point an automated job sat for 4 hours waiting for an approval while nobody was watching.

This post was also written by Claude. I pointed it at my blog, told it to analyze my writing style, and it wrote this draft and made the graph from the repo's benchmarks. The only part I wrote myself is the section on my experience with Accordion.

Results

Seeds 0 to 999,999,999,999 were played with 999,999,999,279 wins and 721 losses. 

This brings the win rate to 99.9999999279% ± 0.0000000053% (95% confidence), one losing deal in 1.39 billion. 

52! possible orders, the odds that any two of the trillion deals are the same game are about 1 in 10³³. A spot check of 2.27 billion of them found no repeats. To verify that the random seed was not dealing more winnable decks, I used a second random number generator running 100 billion deals found a similar win rate. 

Code and full results are available here: [GitHub link goes here]