This week's book giveaway is in the Other Languages forum.We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!

A.I. idea --> Free Cell proof

Jessica Sant
Sheriff
Posts: 4313
So, I was a tad bored today and trying to avoid studying for my Mid-term in Machine Learning when I clicked on the standard "Windows Freecell" game... and it got me to thinking.

On the front page of the FreeCell help page it says:

FreeCell overview
The object of FreeCell is to move all the cards to the home cells, using the free cells as placeholders.

To win, make four stacks of cards on the home cells, one for each suit, stacked in order of rank, from lowest (ace) to highest (king).

Note
It is believed (although not proven) that every game is winnable.

So... what if we build a game, teach it to play free cell and have it play every possible board??

Step 1- code the rules of free cell, all the legal moves and whatnot. Set up the Free Cell World.
Step 2- create an agent that determines all the possible legal moves given a particular state of the board and randomly selects a move to make, til there are none left. (Doubt we'll win many games this way, but its a start!)
Step 3- give the agent some smarts -- (this is where it gets tricky). Need to figure out a heuristic so that the agent can judge how "good" a particular move is compared to the others. Have it play by always choosing the best move and see how we do.
Step 4- get the agent to look ahead a few steps, and then determine which move is really the best one. -- If its possible, and if our heuristic is good -- this should win all the boards.

So... whaddya think? I think Step 3 is the really interesting part to discuss. The first two steps is simply a matter of coding.... and step 4 is just an extension of step 3... But what kind of heuristic do we come up with to judge the state of the board?
[ August 01, 2004: Message edited by: Jessica Sant ]

Jessica Sant
Sheriff
Posts: 4313
Ok... so Google just showed me that this guy has already stated that there are unsolvable boards -- but I'm still curious as to how we train an AI agent to play FreeCell...

Corey McGlone
Ranch Hand
Posts: 3271
Actually, I did this in college - it was a project for my AI class. I'm trying to recall what language I did it in, now, though...ML, maybe. I can't recall. I'll have to see if I can find my notes.

Mark Spritzler
ranger
Sheriff
Posts: 17278
6
I got to the point of having 300 wins in a row, and got really tired of playing.

Mark

Eric Pascarello
author
Rancher
Posts: 15385
6
I taught the computer to play peg solitaire awhile back to find solutions. All I can say it was painfully slow!

Eric

Mark Herschberg
Sheriff
Posts: 6037
I must admit to being a FreeCell junkie. I'm excited to learn that som board are unsolveable. Personally I think it would be cool if in the next generation of the game, the make two changes...

1) allow every possible game
2) after winning a game, the series of moves are sent to a central server as proof that the board is solveable

As for your algorithm, you are of course describing a simpler version of the alpha-beta algorithm, except there's no beta here (there may be another term for alpha only games). You do need an evaluation algorithm. Off the top of my head evaluation factors would be...

1) placing cards into the final cells
2) leaving cells or columns free
3) more points for longer runs of ordered cards
4) maybe negative points for disordered runs of cards, or for cards above their natural parent

--Mark

Pham Cong
Greenhorn
Posts: 1
• 1
Hi Jessica Sant!
i read your comment, and i also want to this program. I think now is 2011 year, so you are completed it. Could you get a intruction for me? Or i can source code this. Thanks you so much.
Note: Who can help me, i also thanks.

Jessica Sant wrote:So, I was a tad bored today and trying to avoid studying for my Mid-term in Machine Learning when I clicked on the standard "Windows Freecell" game... and it got me to thinking.

On the front page of the FreeCell help page it says:

FreeCell overview
The object of FreeCell is to move all the cards to the home cells, using the free cells as placeholders.

To win, make four stacks of cards on the home cells, one for each suit, stacked in order of rank, from lowest (ace) to highest (king).

Note
It is believed (although not proven) that every game is winnable.

So... what if we build a game, teach it to play free cell and have it play every possible board??

Step 1- code the rules of free cell, all the legal moves and whatnot. Set up the Free Cell World.
Step 2- create an agent that determines all the possible legal moves given a particular state of the board and randomly selects a move to make, til there are none left. (Doubt we'll win many games this way, but its a start!)
Step 3- give the agent some smarts -- (this is where it gets tricky). Need to figure out a heuristic so that the agent can judge how "good" a particular move is compared to the others. Have it play by always choosing the best move and see how we do.
Step 4- get the agent to look ahead a few steps, and then determine which move is really the best one. -- If its possible, and if our heuristic is good -- this should win all the boards.

So... whaddya think? I think Step 3 is the really interesting part to discuss. The first two steps is simply a matter of coding.... and step 4 is just an extension of step 3... But what kind of heuristic do we come up with to judge the state of the board?
[ August 01, 2004: Message edited by: Jessica Sant ]