Revision as of 16:44, 22 August 2016

Challenge Problems

The creation and sharing of challenge problems aid the AI educator in that (1) the best education is through experience, and (2) novel challenge problems provide unique experiences, questions, and answers that cannot simply be searched online.

StacksSquared

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. Users[1]

StacksSquared is an original 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 tableau 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 initial 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 a 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 form 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.

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 StacksSquared 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 StacksSquared 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.

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.

Model AI Assignment Highlights

We would also invite past publishers of Model AI Assignments to highlight their work and encourage instructors to take advantage of the resources found on the Model AI Assignments website.