Parade, redux

About a week ago, I wrote here about a card game called Parade.

I've had searching programs running for a bit, now, and have some results, results which seem to me to be a bit much to just append as edits to my previous post.

I wrote a second search program. Instead of playing out a shuffled deck in full and recording the longest parade found, it takes advantage of a property of the game: any parade that can be achieved at all can be achieved with its cards placed right at the beginning of the deck, in order. (Inserting cards into the order can never cause a card that would be picked up without the inserts to be left with the inserts.) So the new program picks six random cards for the initial parade, then does exhaustive search on the rest of the deck: first it throws out all the cards which pick anything up, then, for each remaining card, it appends it to the parade and recurses. When none of the remaining cards can be added without picking anything up, the recursion stops. The longest resulting parade is reported.

In the time it took my previous program to start finding length-18 parades, this new program had already found a length-21 parade, so it clearly was a better way to go when it comes to finding long parades. At this writing it has searched 10697 six-card initial parades and found 4916 whose maximum length is 11, 2804 12, 1228 13, 956 14, 486 15, 148 16, 99 17, 44 18, 6 19, 8 20, and 2 maxing out at length 21.

I then tried something else: I rigged the program to use the same initial six-card parade as the length-22 parade I gave in my last post, the one I found manually, and the program cooked it, finding a length-23 parade!

8A 8B 8C 9A 9B 9C tC tF 9F tB tA 4F 5F 6F 7F 4E 5E 6E 7E 0D 1D 2D 3D

The time taken to search a six-card prefix seems to be fairly directly related to the resulting maximum length. The length-23 cook took nearly 22 hours; the program is currently crunching on something that's taken some 15 hours so far, so I have hopes that it will be a parade of length 22 or better, found from a random prefix rather than a human-chosen one.

Main