Difference between revisions of "Birds of a Feather"

From AI Matters Wiki
Jump to: navigation, search
m (ToddNeller moved page StacksSquared to Birds of a Feather: Better name)
(Add section for future research additions)
(One intermediate revision by the same user not shown)
Line 1: Line 1:
=StacksSquared Rules=
+
=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.[http://solitairelaboratory.com/fcfaq.html]
 
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.[http://solitairelaboratory.com/fcfaq.html]
  
StacksSquared 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.
+
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:
 
An example 4-by-4 game's initial layout:
  
Line 36: Line 36:
 
  <nowiki>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</nowiki>
 
  <nowiki>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</nowiki>
  
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, hence the name "StacksSquared".  The general solution of any grid is a sequence of moves that maximizes this grid score.
+
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.
  
=StacksSquared Questions=
+
=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,  
 
Having defined the puzzle, we can now ask many interesting questions about the game. For r rows and c columns,  
Line 46: Line 46:
 
*What are characteristics of grids without single-stack 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 StacksSquared puzzles:
+
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?
 
*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 StacksSquared puzzles through combinatorial optimization algorithms (e.g. simulated annealing)?
+
*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 StacksSquared, and we can summarize our results in a future column.
+
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 [[StacksSquared]].
+
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 [[#top|Birds of a Feather]].
 +
 
 +
=Birds of a Feather Research=
 +
 
 +
In this section, we summarize what has been learned so far about Birds of a Feather.

Revision as of 15:50, 27 September 2016

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

In this section, we summarize what has been learned so far about Birds of a Feather.