Need to know what approach to take toward building an artificially intelligent program to play spider solitaire

I want to write a program to play a complex solitaire game (spider) with some kind of AI framework. I have taken basic Machine Learning classes on Coursera and am currently enrolled in a Coursera course that introduces one to using Tensorflow/Keras to do the Neural Networks. I have experimented with conventional programming to do this job and run into things such as memory limitations on my PCs and have not successfully been able to conquer this program. I need advice on WHAT capabilities I need to solve this problem.

2 Likes

@Ralph_Gable being honestly unfamiliar with this game, the first question I might ask myself: Do you know the size/state space of this game ? Seeing as it is a form of Solitaire afterall I imagine this must be a game of perfect information.

For such problems understanding the scope is the first step (can I brute force it, and if so, then how do I optimize on top of that ?)-- Or is the state space simply too computationally large, so we try to break the problem down into workable/manageable segments and rely on heuristics.

1 Like

Game simulation typically uses an architecture called Reinforcement Learning. This method is very good at picking the best next action based on the current and previous states.

The RL method is introduced in the Machine Learning Specialization in Course 3, Week 3.

1 Like

I am interested in the state space being the same that a human being would see and that is the up cards in the solitaire layout. I interfaced with chatGPT for ideas but it (at first) wanted the state space to give access to the learning environment to be the layout of ALL cards (104 of them) including the down cards. I objected to that - since I wanted the learning environment to be the same as a human player - namely the up cards visible and the down cards as they were made visible by game play. Unfortunately chatGPT did not choose an RL environment. I took some coursera courses about 3 years ago but didnā€™t use them so had pretty much forgotten the things I had learned - so I signed up for a refresher using tensorflow and Keras. The recommendation (originally) of chatgpt did not work because it did not choose RL and I went down a rabbit hole with chatGPTā€™s suggestion and it didnā€™t work. Thatā€™s why I am seeking info from knowledgable people such as yourself. I am (at this moment) looking at a quick and dirty description of RL on YouTube. By profession I was an engineer working on Avionics software for the last 40 years but am retired and donā€™t want my brain to rot - so any help from guys such as yourself would be appreciated. The state space is VERY large BUT an entire game doesnā€™t take that many steps - maybe a hundred or so.

2 Likes

PS the game uses two 52 card decks - so there IS a huge state space. But not as huge as for example an image with a huge number of pixels.

1 Like

Chat bots are not a reliable source of programming advice.

1 Like

By state space specifically I was thinking about the total number of possible ā€˜movesā€™ in the game starting from the initial condition of the deck. For example, as far as I know, in the case of Chess, this space is enormous and still only ā€˜estimatedā€™ at around 10^{46}, which would be the size of your initial (inverse) search tree.

I mean a number of years ago I took a Coursera course on AI from UC Berkeley and at that time Deep Networks werenā€™t necessarily king of everything in this space. Nor, really do they have to be, if your state space is small enough.

@Tmosh is correct in that RL is conventionally used for these types of game situations, but unfortunately I donā€™t have much experience there so canā€™t suggest to you any really good texts at this time.

One thing to consider at least is insofar as with ConvNets and image processing, while the absolute number is quite large, the images considered are often quite small by comparison to anything we, as humans are used to.

I mean though still a computationally large task with 1024 input nodes, CIFAR-25 images are merely 32 x 32 pixels by comparison.

As a still, unanswered, question of my own, of course the use of ConvNets is in a sense designed for very complex feature identification and downscaling, could a similar technique be used in the case of a ā€˜game playā€™ example-- Or would ConvNets simply use much to broad brush strokes and wipe over the final details in the data ?

I mean, as an example, if youā€™re talking 52 card decks, even for one deck there are 8*10^{67} ways to sort that one deck. But to make things somewhat simpler, could this be represented by a set of colors of pixels in an image ? So if you have 4 suits, so one color for each suit (say a CMYK scheme), and then say gradient variations on that particular pixel color to represent the face value of the card. Plus reserved colors for special cards.

So essentially, you could generate synthesized data for every state in the form of an image and then process it convolutionally that way.

Noooo idea if it would work/help, but just a thought (also possibly for other types of data too ?).

1 Like

The things you are thinking about state space correlations to pixels in a picture HAS crossed my mind but I havenā€™t yet given that idea the thought it needs. The nice thing about this problem is you have a layout of x number of cards arranged in 10 columns and making a list of the number of possible moves is fairly trivial and it IS a manageable number. The problem is exploring the COMPLETE state space (i.e. every possible move in this state x every possible move for each of those moves) quickly becomes HUMOUNGOUS. I have tried implementations of things like that (as you would approach a chess or checkers game). It rather quickly used up all my PC memory. Then I tried pruning those selections severely but I thought about the possibilities that might not be optimal NOW but might blossom into a winner later down the tree. THEN I thought about how I play the game - a simple human that just observes and sees opportunities and explores different possibilities and without going through ALL combinations of moves conquers the game. I thought of approaching it as I would in a game. I have played some VERY complex games - I have spent SIX hours on some games and beat them. I have a VERY detailed paper that examines the game and states that most deals are winnable but also says there are some that are not. I was going to try to approach it as I would but always got back into exploring too many alternatives. It is REALLY difficult to think about EXACTLY HOW you approach something like this as a human. I have noticed that most of my problems are that when I backtrack and replay sequences (sometimes OVER and OVER) my brain WANTS to keep making the same mistakes. Usually the problem is that there is an alternative thing to do but my dumb brain does the wrong thing over and over. Sometimes the sequences that get you down the correct path are VERY complex and it is hard for your brain to see that one little mistake you make. I am ABSOLUTELY positive that if I could sit down and REALLY analyze HOW I play the game I could conquer this but THAT IS NOT trivial. The cool thing is once you get to a certain point the alternatives become less and less and by that time you have killed it. I should just sit down and start with stream of conscious and analyze what I do - probably a good idea would be to record video on iPhone for several games and then in tranquility just analyze what I do. I may try that because like I said after you get past the rough spots and believe me there are plenty it gets LOTS easier. I am not stuck on HAVING to do it the AI/RL or any other way.

1 Like

Yes - to Tom Mosher - I have found that out about chatbots - but chatgpt is helpful for syntactical things etc and he has taught me many things. He let me down on this though - and there IS a disclaimer that I should have paid more attention to.

1 Like

A couple of additional thoughts-- and Iā€™m not a card player at all, sorry-- I donā€™t play video games and I can barely recall the rules of poker.

But since this is solitaire, you also might not need to find a ā€˜completeā€™ solution.

Or given any starting state, as even with chess, over time your possible set of moves becomes less (the play tree of possibilities shrinks).

Rather than trying to solve the entire problem, you might be able to deduce/attack some smaller subset of it (again, I donā€™t know, but lets say a round of 5 or 6 moves) and from their deduce a general strategy that, at least, out of all possible games, gives you a higher chance of winning.

Of course also, DeepMindā€™s huge advantage is there are loads of recorded chess/Go games to pretrain the network on before simulating with RL. I have no idea if that is the case with Spider Solitaire, which would make working with a neural network architecture so much harder.

I mean I know a lot of people on here (myself too, within reason) triumph Deep Learning, but, at least thus far, if you have no dataā€“ You basically have no network.

Further, as to the color coding for convolutional data, again just a wild thought, but it seems at some point in the network youā€™d have to have a sort of ā€˜conditioningā€™ layer that you really donā€™t see in traditional CNNs.

Or perhaps, with gradients for the face numbers, as you go down you start to get ā€˜in-betweenā€™ values from those exact colors you specified, which even adequate represents this is ā€˜not just a math problemā€™-- There is some probability, or ā€˜chanceā€™ here; But at the end of the day you are playing with real cardsā€“ So you have to choose one. Perhaps a softmax after each layer, but youā€™d have to update the ā€˜stateā€™ of your image before the next conv layer, something I just donā€™t think you find yourself dealing with when you are looking at/analyzing pictures.

Thanks for the back and forth. One thing I have been thinking is I need to analyze the current state and figure out goals. I have run scenarios where I just randomly choose moves and there are SO many possible ways that can go that you end up with garbage. I have been thinking today about analyzing the entire set of cards for ALL possible combinatorial moves and then defining goals to get to certain ones that create combinations that are going to move progressively to a win. I have been lax in adequately defining a heuristic also and I intend to change that. You hit the nail on the head - there is no big archive of training data. Training with totally random games is worthless - thatā€™s more or less what I was doing when I tried chatgptā€™s approach - it was worthless because this is not a classification situation. I AM thinking (similar to what you are suggesting), maybe creating a million or so first 100 moves randomly and being VERY careful about my heuristic and see how that goes.

That is the classic discrete programming method of implementing a state machine. It has limitations as the space of potential states increases.

It has nothing to do with machine learning.

A Reinforcement Learning method would train a small NN (a ā€œQā€ network) to learn what the best next state is. The more games the network is trained on, the better the Q network becomes.

Like I said I am not necessarily committed to any particular solution. I am leaning toward a really smart move analyzer that analyzes the state to find short term goals to work toward - just like I play the game. That could solve the problem and would be fascinating if I got it to work. Think of having a chess program that worked like human chess players think rather than dealing with exhaustive move tree analysis. It would be paradigm breaking.

This is what RL is for. I would start with Casino - Gymnasium Documentation and reading how RL explores that. Most likely it clicks some pixels, records what happens, and if that helped the final goal in the end.

1 Like

Dear Ralph,

So I am glad I was able to at least stir some thoughts-- especially on a topic I know nothing about.

And yes, I know there may be more conventional or accepted standard practices for solving some of these problems-- Yet even then I remain the sort of person that likes to ā€˜think about itā€™ first, before jumping straight to some accepted architecture.

I mean consider even transformer models which today are all the rage-- Obviously at some point someone had to design that architecture, and for us sometimes that is half the fun. These are discoveries, adventures, not problems we are trying to solve for our boss.

That said, from the first I admited Iā€™d no experience in RL (but I should)-- And DeepLearning.Ai doesnā€™t offer a real substantial equivalent.

Nor, exactly are there a ton of books on the RL topic, but of those I saw Iiked this book: Foundations of Deep Reinforcement Learning: Theory and Practice in Python [Book]

And also, notably, from the University of Alberta (Iā€™m American but I did my M.A. at University of Toronto, so go Canada !)-- It doesnā€™t seem like the most popular specialization, but does seem highly rated. And the topics covered do look pretty through.

Best of luck to you.

Hello, i also think you should use RL, which is very good in games. I was into RL too for some months use some algorithms from RL to DRL, if thereā€™s any way i can help iā€™m happy to. Good luck

The most classical RL book offers a free PDF copy - the Sutton and Bartoā€™s book. The official site is offline, but you may find the PDF online somewhere.

However, I would start approaching this game with a simpler approach: a Monte Carlo Tree Search (MCTS). Itā€™s loosely related to RL, but it can be better described as a type of search, which allows you to control the amount of time (and indirectly, space) you want it to use. You will have to think how to treat the unknown cards, but I think itā€™s feasible.

By the way: MCTS is an important element in the revolutionary AlphaGo family of algorithms that ultimately dominated Go, Chess, Shogi (and virtually any board game) years ago.

1 Like

This sounds like a reinforcement learning challenge. Study what the researchers did with AlphaGo for inspiration. Great documentary available and lots of information regarding architecture online.

I actually started to enroll in this class and you can find the full (legit) free PDF text here:

http://incompleteideas.net/book/the-book-2nd.html

*I would also agree with you, though it is not an area I dabble in much, Iā€™m not sure always the best or most efficient solution is ā€˜deep everything !ā€™, which is where I tried to hintā€¦ I mean, LLMs today are almost the exact opposite of that.

Yeah, that book looks pretty cool. I REALLY like where they showed what all the symbols used in these expositions mean. Career wise I was an engineer who worked 40 years on airplane avionics systems. I have a degree in Engineering (Cal State LA wasnā€™t certified to give EE degrees - so they gave degrees in ā€œEngineeringā€ with an electronics specialization). I had attended Oklahoma State U but had not graduated. Cal State reqs for an EE degree were almost exactly like Okie Stateā€™s. I didnā€™t really care - all I wanted was a ā€œsheepskinā€. Generally though EE classes donā€™t use that math notation (or didnā€™t when I was in school). I worked on some pretty interesting avionics systems but didnā€™t really have to have any aeronautical knowledge but often implemented things aero engineers had specified. My specialties were really multitasking, multiprocessor type applications -especially interfacing with Real Time operating systems. Didnā€™t have much need for the mathematical notations so that stuff hurts my brain but I am adjusting.