wood burning stoves 2.0*
The moose likes Game Development and the fly likes A.I. idea --> Free Cell proof Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Game Development
Bookmark "A.I. idea --> Free Cell proof" Watch "A.I. idea --> Free Cell proof" New topic
Author

A.I. idea --> Free Cell proof

Jessica Sant
Sheriff

Joined: Oct 17, 2001
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 ]

- Jess
Blog:KnitClimbJava | Twitter: jsant | Ravelry: wingedsheep
Jessica Sant
Sheriff

Joined: Oct 17, 2001
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

Joined: Dec 20, 2001
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.


SCJP Tipline, etc.
Mark Spritzler
ranger
Sheriff

Joined: Feb 05, 2001
Posts: 17257
    
    6

I got to the point of having 300 wins in a row, and got really tired of playing.

Mark


Perfect World Programming, LLC - Two Laptop Bag - Tube Organizer
How to Ask Questions the Smart Way FAQ
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    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

Joined: Dec 04, 2000
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

Joined: Apr 14, 2011
Posts: 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 ]
 
 
subject: A.I. idea --> Free Cell proof