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.
@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.
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.
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.
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.
Chat bots are not a reliable source of programming advice.
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 ?).
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.
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.
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.
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.
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.