Let's Make a Solitaire AI!
May 2025 | by Dani
Programming
Ok so I got really depressed recently and started passing the time by plaing google solitaire??? And I realised that there were certain strategies about what moves to make and I wanted to see if I could make an AI that could play solitaire as well as I can. So let's program solitaire.
struct Solitaire {
stock: Vec<Card>,
tableau: [CardStack; 7],
foundations: Vec<Card>,
}
In solitaire, cards can be in three places.
There's the stock, which is like the deck that you flip over one at a time. For our implementation, we're playing one card solitaire (equivalent to google solitaire's "Easy" mode), which means you can basically access any card in the stock at the time. Here it's basically kept as just a plain collection of cards.
Then there's the tableau, which is the 7 stacks of cards in the middle. For this we have a special CardStack class:
struct CardStack {
hidden: Vec>Card<,
visible: Vec>Card<,
}
Which basically just keeps a list of the cards from lowest to highest, seperating the face down and face up ones.
Lastly, we have the foundations; the place you put your cards at the end, stacking them up by suit from aces to twos and so on. For simplicity, we just keep an array of all cards that have been moved here, in no specific order.
Now, in order to actually play solitaire, we have to be able to make moves. Thus comes the move enum!
pub enum SolitaireMove {
Release(usize, usize), // take stock[a] and place it on stack b
Move(usize, usize, usize), // take the top a elements on stack b and place them on stack c
Stow(usize), // take the top of stack a and put it in foundations
StowFromStock(usize), // take stock[a] and put it in foundations
Unstow(usize, usize), // take the thing from foundations[a] and put it on stack b
}
Really, there's five kinds of move in solitaire. "Unstow" here is the weird one, and in order make this easy, and to stop the ai from getting stuck in loops, we're not gonna let it unstow cards.
And here's the method that actually allows us to make these moves!
fn make_move(&mut self, game_move: SolitaireMove) {
match game_move {
SolitaireMove::Release(i, n) => {
let card = self.stock.swap_remove(i);
self.tableau[n].place(&mut vec![card]);
},
SolitaireMove::Move(i, n, m) => {
let mut cards = self.tableau[n].grab(i);
self.tableau[m].place(&mut cards);
},
SolitaireMove::Stow(n) => {
let card = self.tableau[n].grab(1).remove(0);
self.foundations.push(card);
},
SolitaireMove::StowFromStock(i) => {
let card = self.stock.swap_remove(i);
self.foundations.push(card);
},
SolitaireMove::Unstow(i, n) => {
let card = self.foundations.swap_remove(i);
self.tableau[n].place(&mut vec![card]);
},
}
}
And of course we need a fn generate_moves(&self) -> Vec<SolitaireMove> that lets us generate all legal moves. As mentioned before, We're going to remove certain kinds of moves in order to prevent the AI getting caught in loops. Specifically:
- Our
generate_movesmethod won't give us unstow moves, otherwise we might get in loops of stowing/unstowing - We're only allowed to move one stack to another if it means moving the whole stack (and once the king is on the bottom of a stack, we don't allow that stack to be moved). Otherwise the AI could get stuck moving part of a stack back and forth again.
After this I basically just implemented some format methods so I could print out the whole thing... look at this lovely screenshot!
Ok. So. How does one win at solitaire? The first thing I begin to notice as I play is that there are certain moves we can consider "safe". As in, they don't actually cut off any opportunities. For instance, releasing a card from the stock is safe if its "pair" (ie, the other card with the same number and colour) is already "out". By "out" I mean that it's either also in the stock, or its already been played into the tableau (and isn't hiding any cards), OR, the card is in the foundations or could immediately be played to the foundations if discovered.
In these cases, releasing your card doesn't prevent you from freeing up its pair, and so its safe to do so. This is the same with moving any card from one stack to another. It's safe if the other card is already free. Releases and Moves are also safe if there are two possible places it could move to; in which case it doesn't matter if the pair is still trapped, because the pair will still have some place to go.
(There's sort of a weird case here with kings, since you need to worry not just about the pair but about all other kings which could occupy the empty spots. Thus I need my own seperate "is_king_safe()" method which decides if there's enough space to put all the kings or not yet.)
Deciding when stowing is safe is another matter. In order for stowing card to be safe, it means that any cards that could be placed on top of it must already be stowed or otherwise free and out.
fn is_safe(&self, solitaire_move: SolitaireMove) -> bool {
match solitaire_move {
SolitaireMove::Release(i, n) => {
let card = &self.stock[i];
if (card.value != 13) {
self.is_out(&card.get_pair()) ||
(self.is_visible(&card.get_successor().get_other()) && self.is_visible(&card.get_successor().get_other().get_pair()))
} else {
self.is_king_safe()
}
},
SolitaireMove::Move(i, n, m) => {
let card = &self.tableau[n].visible[i-1];
if (card.value != 13) {
self.is_out(&card.get_pair()) ||
(self.is_visible(&card.get_successor().get_other()) && self.is_visible(&card.get_successor().get_other().get_pair()))
} else {
self.is_king_safe()
}
},
SolitaireMove::Stow(n) => {
let card = &self.tableau[n].visible[self.tableau[n].visible.len()-1];
self.is_out(&card.get_predecessor().get_other()) && self.is_out(&card.get_predecessor().get_other().get_pair())
},
SolitaireMove::StowFromStock(i) => {
let card = &self.stock[i];
self.is_out(&card.get_predecessor().get_other()) && self.is_out(&card.get_predecessor().get_other().get_pair())
},
SolitaireMove::Unstow(i, n) => {false},
}
}
In the above code, we use various methods to manipulate cards without having to type out whole objects... get_predecessor() subtracts one from the value, get_successor() adds one. get_pair() flips the suit without chaging the colour (Hearts <-> Diamonds and Spades <-> Clubs) while get_other() flips the color (Hearts <-> Spades and Diamonds <-> Clubs).
So we've made some very good observations. It turns out if you only make these "safe" moves you can get ten or so moves into the game before getting stuck. But this is very unlikely to ever actually solve the game, and so we'll need to improve our AI somehow.
We'll start by playing just safe moves until there's none left, and we'll return back the number of moves we get to make before we get stuck. This will be a rough measure of how well we do.
fn progress_safe(&mut self) -> u32 {
let mut count = 0;
'outer: loop {
for game_move in self.generate_moves() {
if self.is_safe(game_move) {
self.make_move(game_move);
count += 1;
continue 'outer;
}
}
break;
}
return count;
}
This allows us to evaluate "risky" or "non-safe" moves. Ignore the depth parameter for now.
fn evaluate_move(&self, solitaire_move: SolitaireMove) -> f64 {
const NUMBER_REPEATS: u32 = 10;
let mut total = 0.0;
for _ in 0..NUMBER_REPEATS {
let mut new = self.shuffle_clone(); // make a clone of the current game, shuffling unknown cards around
new.make_move(solitaire_move);
// this is an alternative evaluation method where we try to maximise the numbner of cards moved into the foundations.
// this actually makes the algorithm worse... goes down to about 22% success rate :/
// total += new.foundations.len() as f64;
total += new.progress_safe() as f64;
// prograss_safe() returns the number of safe
// moves that can be made from this position
}
return total;
}
Essentially, we make the move, and then see how many safe moves it then allows us to play after that point. We need to clone the game when we do this (to make sure we can undo our simulated changes just by going back), but we also need to make sure it doesn't let us know anything we didn't previously. That's what shuffle_clone() does. It shuffles all hidden cards before making the move. That also means the results are a bit random, so we'll repeat it 10 times and take the average (actually, since we're just using this to compare, we don't need to divide, we can just take the total).
So, whenever we don't have any safe moves left to make, we can just pick the unsafe move with the highest average rating:
fn make_best_move(&mut self) {
let mut best_score = 0.0;
let mut best_move = self.generate_moves()[0];
for solitaire_move in self.generate_moves() {
let score = self.evaluate_move();
if score > best_score {
best_score = score;
best_move = solitaire_move;
}
}
self.make_move(best_move);
}
And to play, we just alternate and see how far we get!
fn attempt() -> bool {
let mut game = Solitaire::new();
loop {
game.progress_safe();
if game.is_won() {
return true;
} else if game.generate_moves().len() == 0 {
return false;
}
game.make_best_move();
}
}
This pretty simple algorithm is already pretty good. It wins about 35% of the time! But according to wikipedia, other people have made algorithms that can win up to 52% of the time!
Really, the issue is that we're not looking ahead at all. Instead of evaluating a move based on how many safe moves we can make immediately after it, we should try making another dangerous move after it, and seeing how far we get two dangerous moves ahead. This means we need a depth parameter on our make_best_move function:
fn make_best_move(&mut self, depth: i32, thoughtful: bool) {
let mut best_score = 0.0;
let mut best_move = self.generate_moves()[0];
for solitaire_move in self.generate_moves() {
let score = self.evaluate_move(solitaire_move, depth, thoughtful);
if score > best_score {
best_score = score;
best_move = solitaire_move;
}
}
self.make_move(best_move);
}
Ignore the thoughtful argument for now. We'll come back to it. Now, our evaluate move function must now take into account the depth:
pub fn evaluate_move(&self, solitaire_move: SolitaireMove, depth: i32, thoughtful: bool) -> f64 {
let NUMBER_REPEATS = if thoughtful {1} else {10};
let mut total = 0.0;
for _ in 0..NUMBER_REPEATS {
let mut new = if thoughtful {self.clone()} else {self.shuffle_clone()}; // make a clone of the current game, shuffling unknown cards around
new.make_move(solitaire_move);
let mut depth = depth;
loop {
total += new.progress_safe() as f64;
depth -= 1;
if depth == 0 {break;}
if new.generate_moves().len() == 0 {
break;
}
new.make_best_move(depth, true);
}
}
return total / (NUMBER_REPEATS as f64);
}
See? Now we loop around a number of times equal to depth and progress each time, and then make another move (at a lower depth) for each loop!
The thoughtful flag serves to tell the program that it doesn't need to re-randomise the arrangement at each level, and only at the first step (since we're gonna run a lot of simulations anyway). This helps stop the runtime from exploding once we increase the depth.
Now, here's where you tell me what's wrong with this code, because despite this improvement??? It still has a winrate of 35%. I straight up don't know why I can't improve beyond that. I can increase the number of random trials, I can increase the depth, and it still is just as bad!
Anyways. I cannot for the life of me figure out how to improve beyond this point. But if you're reading this and you think it sounds fun, I'd love to get in contact and talk about it!
Frankly this project has just been a big excuse for me to learn a bit of rust. Feel free to make fun of my programming.
Here's the ZIP file: solitaire.zip.
