Birds of a Feather

From AI Matters Wiki
Jump to: navigation, search

Birds of a Feather Rules

FreeCell stands out among solitaire card games because it is essentially a random self-generating puzzle that has perfect information and can be solved with high probability. Players over the years have, as a community, researched many aspects of the game.[1]

Birds of a Feather is an original perfect-information solitaire game played with a standard 52-card deck. After shuffling, the player deals the cards face-up left-to-right in c columns, and top-to-bottom in r rows to create an r-by-c grid of cards. An example 4-by-4 game's initial layout:

5S JC QH 8H
KC 6H 3H 9H
3S JS TH TS
KS 7D AH 5C

Think of each grid cell as initially containing a 1-card stack. A stack may be moved on top of another stack in the same row, or in the same column if at least one of two conditions is met: (1) The top card of each stack has the same suit. (2) The top card of each stack has the same rank or an adjacent rank (with Aces low and Kings high and Ace and King non-adjacent). Thus the 9H (9 of Hearts) stack can move onto the TS (Ten of Spades) being adjacent/same in rank:

5S JC QH 8H 
KC 6H 3H    
3S JS TH 9H 
KS 7D AH 5C

And the 8H stack can move onto the 9H stack being both of (1) same suit and (2) same/adjacent rank:

5S JC QH    
KC 6H 3H    
3S JS TH 8H 
KS 7D AH 5C

And the TH stack can move onto the AH stack being of the same suit:

5S JC QH    
KC 6H 3H    
3S JS    8H 
KS 7D TH 5C

If we notate each move as the top cards of the moving and destination stacks separated by a hyphen, then this entire tableau can be formed into a single stack from this sequence of moves:

9H-TS 8H-9H TH-AH 3H-TH QH-3H 6H-7D JC-JS 3S-KS 5S-3S 5C-5S KC-5C QH-KC QH-6H QH-JC QH-8H

Let us call this simple solution concept a "single-stack solution". However, we can define a more general solution concept of forming largest stacks by defining the score of a grid to be the sum of the squares of the stack sizes. The general solution of any grid is a sequence of moves that maximizes this grid score.

Birds of a Feather Questions

Having defined the puzzle, we can now ask many interesting questions about the game. For r rows and c columns,

  • What is the probability that a deal will have a single-stack solution?
  • What is the maximal score distribution of deals?
  • What are heuristics that can be used to guide search more efficiently to solutions?
  • What are characteristics of grids without single-stack solutions?

There are also many questions one can ask with regard to the automated design of Birds of a Feather puzzles:

  • What are the most important attributes of challenging deals with single-stack solutions?
  • How can such attributes best combine to form an objective function that can be used to generate Birds of a Feather puzzles through combinatorial optimization algorithms (e.g. simulated annealing)?

Given this fresh ground for exploration, we would invite educators and students to explore these and other questions concerning Birds of a Feather, and we can summarize our results in a future column.

The best learning is through experience, and we hope that this grit results in some pearls of work in the months to come. To share your results, please email Todd Neller (tneller@gettysburg.edu) and we invite you to register with and add to our wiki on the subject Birds of a Feather.

Birds of a Feather Research

We are currently inviting faculty-mentored undergraduate student researchers to research Birds of a Feather questions and publish/present their results at EAAI-2019: The Ninth Symposium on Educational Advanced in Artificial Intelligence. Details can be found here.

Following EAAI-2019, we will summarize what has been learned so far about Birds of a Feather on this page.