for brainiacs...solitaire algoritm?

Discussion in 'Game Design' started by jankoM, Oct 3, 2006.

  1. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    Hi, I was googling about it but couldn't find anything... (except a lot of solitare encryption algoritm). The thing is I made this mini solitare for kids. And to make it more kid friendly (quicker to play and understand and for learning numbers) I made just two colors of cards with cards 1-10. So the whole deck has 20 cards.

    Because of this I can't (no way) just randomly mix the cards and hope to came to a solvable solution but I must generate a solvable positioning in some way. I do this now by head and the way I do it is totally brain hurting - I need a lot of time (and few times forget where is what in the middle and have to restart) just to make 1 "level". I am thinking there must be a smarter way of doing it manually or even better to do it programatically. Does anyone know anything about it?

    (the way I do it now is that I plan the moves player will have to make and put the cards to positions to enable this.

    the working version of game is here: http://www.bravekidgames.com/flash_game_solitaire.php

    A sample level if it helps anything is here: http://www.itmmetelko.com/storage/lvl_easy1.txt you can try to make a level if you think it's easy...
     
  2. Sol_HSA

    Indie Author

    Joined:
    Feb 27, 2005
    Messages:
    470
    Likes Received:
    1
    Not looking at your game at all, how about starting from the solved position and generating random reverse moves until the game is at the beginning?
     
  3. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    I tried going backwards and it didn't work... but now that you say "from solved position" I am thinking that wasn't exactly solved position... it was a clear board and then .... uh... I will try it and tell you how it goes.
     
  4. Gilzu

    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    368
    Likes Received:
    8
    do a game tree from the solved position, using DFS where each move goes in reverse. stop searching the tree where it is unsolveable. where it is solveable, save it in a file.

    You'll only have to run this search once since results would be saved in a file :)
     
  5. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    I tried to do as you said but I think it doesn't work.... I solitare would be about filling one stack from another stacks then this would work probbably but when it comes to moving a partial stack left and fight (for example from stack (1) 3A 4B 5A to a card 6B that opened on neighbour sack (2) then opening card on stack (1) and you see it is 7A so you can move that partial stack back to it and open the card below....) it stops

    Thanks Glizu for the link ... I will study DFS because I have no clue what you are talking about :) .. just a question... do you know DFS can solve solitaire or do you think?

    btw... the joke is that I never played normal solitare before I started making this... so now I am just amazed how many combinations and stuff this peewee deck of cards can provide.
     
    #5 jankoM, Oct 3, 2006
    Last edited: Oct 3, 2006
  6. Roman Budzowski

    Indie Author

    Joined:
    May 7, 2005
    Messages:
    839
    Likes Received:
    2
    OT: Yay, I always want to add cute little minigames that I can develop within a day and then when you get the core running you want to add that and this feature and realize than one day is more likely to be one week (or two) :D

    Roman
     
  7. Gilzu

    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    368
    Likes Received:
    8
    Both DFS and BFS can solve solitare from each direction. You use the same method in Chess and Checkers only that they compute x steps in advance.

    do a google search on BFS/DFS and game trees.

    and since i'm so nice, i found you some interesting links that might apply as they are about other similar games :rolleyes: :

    I recommend reading about it anyway, since its both interesting and useful method/algorithem for all kinds of problems.
     
  8. luggage

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    2,132
    Likes Received:
    0
    I know this is of no use but...

    does it matter if it's not solvable? The person playing isn't going to know that - they'll just think they failed. Which is exactly the saeme feeling they'll get if they fail a solvable grid.
     
  9. Christian

    Original Member

    Joined:
    Mar 22, 2005
    Messages:
    769
    Likes Received:
    0
    I belive that solitarie works because of how many kind of cards exists in the deck, not because of a complex algorithm, so, i would tell you to reconsider the composition of the deck, change that so that it would be easy to handle the code. Think about why there are so many games made with just one kind of deck?, because that when there is such a deck, there are a number of universal rules that can be apllied to games made with that deck, you should search about card games in general instead of code, because its more a game design problem than a programming one... my two cnts.
     
  10. Artinum

    Original Member

    Joined:
    Dec 19, 2005
    Messages:
    536
    Likes Received:
    0
    I don't have the first clue how practical this is but here's an alternative idea for you to consider...

    Step 1 - make a "solver" program that follows a basic algorithm to solve games. Basically, you give it a layout of cards and it will try every sequence of moves available - following every branch of a "tree" of possible moves - to a certain depth (as you don't want (a) to spend (literally) forever on it and (b) there's a limit to how far it *should* be able to go).

    Step 2 - create random decks as you already know how. Plug these into the solver program from step 1.

    Step 3 - log any random decks the solver program flags as "solvable". Discard any that it fails to complete.

    You might need to leave your computer running overnight for this, but we all need to sleep some time!
     
    #10 Artinum, Oct 3, 2006
    Last edited: Oct 3, 2006
  11. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    Uh thanks a lot guys!

    Roman B. : Yes it's very enjoyable to make little games... at least it's very enjoyable to start making little games, finishing is more of a problem (to me at least) and takes much longer than it takes the main game mechanics.

    Glizu: You are being too good.... I will study these things and thank you for the links!!

    luggage: If 5% would not be solvable I would think as you suggest but with this small number of cards I believe most of randomly set position-sets are unsolvable.

    Christian: I agree that game im this case "level" setup is complicated to prepare theoretically and that this is conceptual not programing challenge. But I will not reconsider the game design because I very much like how the game is being played / solved. And it's a mini game for kids.... But level creation for now (wait untill I study your recommandations) is problematic thats why it will stay this mini bini game with few levels unless Glizus and Artinum's ideas bring me somewhere.

    Artinum: Thanks for idea... I have to figure what DFS/BFS stuff is about as I suspect that it might be related or similar to the procedure you proposed (your is nicely logical). Now this is begining to interest me in a new way... time to start some python and do some solving ;)

    Thanks all really!
     
  12. rhm

    rhm
    Original Member

    Joined:
    Jul 28, 2004
    Messages:
    17
    Likes Received:
    0
    You could also try using a deck of 40 cards with 2 colors, 10 cards, but every card coming twice. This should increase the probability of solvable positions. Just look at the Spider Solitaire pre-installed in Windows.
     
    #12 rhm, Oct 4, 2006
    Last edited: Oct 4, 2006
  13. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    yes this is an option, but I like very much that this is solvable as quick as it is now which is IMO more appropriate for kids.

    You are the artist of Swap (from phelios) ? I saw your page and I like your style a lot - it's a little different from todays tipical art.

    I will try to do this generator solver as others suggested... the problem is that I don't have much time these days... I will tell you if I manage to make it.
     
  14. Huge

    Original Member

    Joined:
    Sep 22, 2005
    Messages:
    142
    Likes Received:
    0
    I think this is the way to go - you could then have various levels of "solver" - ie, one that always puts cards in certain spots, does no backtracking or whatever. And one that does 7-move lookahead or other devious techniques. This would then give you a progression of "levels" - each matching a solver's profile.
     
  15. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    :( I gues I am too stupid to make a solver for this solitaire in a given time.. I looked at DFS BFS too.

    I made a python script but now I became aware of some new complication which I don't know how to solve. I will probably try to make it again but right now It seems more reasonable that I make 3 more levels by hand so I have 12 and publish it than to wait (because I have 2 other games half done which would be wise to finish and I spend 4 evenings on this without any result).

    The problem that stopped me is quite complex and hard to explain... if someone is interested I can try... here is the python code that I came up so far:

    PHP:
    import copy

    stacks 
    = {
            
    'backup': [],
            
    'm': { 0: [], 1: [], 2: []},
            
    'mo': { 0: [], 1: [], 2: []},
            }
    stop False;
    stepCount 0

    def createRandomPositioning
    ():
        global 
    stacks
        stacks
    ['backup'] = [(1,1), (2,1), (1,3),]
        
    stacks['m'][0] = [(1,2),]
        
    stacks['m'][1] = [(2,2),]
        
    stacks['m'][2] = [(2,3),]
        
    stacks['mo'][0] = []
        
    stacks['mo'][1] = []
        
    stacks['mo'][2] = []
        

    def step(stacks_depth):
        global 
    stop
        
    global stepCount
        stepCount 
    += 1
        
    if stepCount 500:
            
    stop True
            
    print '+++++STEP OWERLOAD+++++'
            
    return 
        if 
    stop:
            print 
    '+++++STOP+++++'
            
    return
        if 
    depth 60:
            print 
    '+++++TO DEEP+++++'
            
    stop True
            
    return
        print 
    stacks_
        
    print 'depth'depth
        
    #make a copy of stacks
        
    stacks copy.deepcopy(stacks_)

        
    #at each step we must create a copy of stacks with that modified situation
        #
        
    if len(stacks['backup']) == and len(stacks['m'][0]) == and len(stacks['m'][1]) == and len(stacks['m'][2]) == :
            print 
    "======"
            
    print "======"
            
    print "solved"
            
    print "======"
            
    print "======"
            
    print stacks
            stop 
    True
            
    return 0
        
        
        
    #we open all closed cards on mixers if they are free to open
        
    for idxstack in stacks['mo'].items():
            if 
    len(stack) == 0:            
                if 
    len(stacks['m'][idx]):
                    print 
    "open:"idxstacks['m'][idx]
                    
    stacks['mo'][idx].append(stacks['m'][idx][len(stacks['m'][idx])-1])
                    
    del(stacks['m'][idx][len(stacks['m'][idx])-1])
                    if 
    not stopstep(stacksdepth 1)
            
        
    #we see if any mixer is empty and put each possible a card there
        #and call the new step for each one (we must go in some predefined order
        #so we know what we have allready done and whatnot

        
    for i in range(3):
            if 
    len(stacks['mo'][i]) == and len(stacks['m'][i]) == 0:

                
    ##first we put every possible card from vackup stack to that position and call
                ##it again
                
    for card in stacks['backup']:
                    
    stacks['m'][i].append(card)
                    if 
    not stopstep(stacksdepth 1)


                
    ##then we put every open card on three stacks (two remaining)
                ##(with it's stack to that position)
                
    for i2 in range(3):
                    if (
    != i2):
                        for 
    i3 in range(len(stacks['mo'][i2])):
                            
    #prestavimo to in vse nad njo
                            #print 'bb:', i3, len(stacks['mo'][i2])
                            
    for curI in range(i3len(stacks['mo'][i2])):
                                
    #print 'aaaaaaaaa', stacks['mo'][i2], curI
                                
    stacks['mo'][i].append(stacks['mo'][i2][curI])
                                
    #del(stacks['mo'][i2][curI]) ###todo continue here
                                #step(stacks)
                                #for curI in range(i3, len(stacks['mo'][i2])):
                                #print 'aaaaaaaaa', stacks['mo'][i2], curI
                                #stacks['mo'][i].append(stacks['mo'][i2][curI])
                            
    del(stacks['mo'][i2][i3:]) ###todo continue here
                            
    if not stopstep(stacksdepth 1)

            
        
    #we try if anything from backup goes to any of the open cards on mixers
        #if it goes we call another steep() with this new situation
        
    idx 0
        
    for card in stacks['backup']:
            for 
    i in range(3):
                
    #if of diferent color
                #print "aaaaaaaa", stacks['mo'][i][0]
                #print "count - 1", len(stacks['mo'][i])
                
    if len(stacks['mo'][i]):
                    if 
    card[0] != stacks['mo'][i][len(stacks['mo'][i]) - 1][0]:
                        
    #if of previous number
                        #print 'ere', stacks['mo'][i][len(stacks['mo'][i]) -1][1]
                        
    if card[1] == stacks['mo'][i][len(stacks['mo'][i]) -1][1] - 1:                    
                            
    stacks['mo'][i].append(card)
                            
    del(stacks['backup'][idx])
                            if 
    not stopstep(stacksdepth 1)
            
    idx += 1


        
    #we try if anything from opened cards goes to any other open cards (with stack
        #above it also and call the new step with that situation
        #for each stack

        
    for stack1 in range(3):
            
    ##then we put every open card on three stacks (two remaining)
            ##(with it's stack to that position)
            ##for each stack
            
    for stack2 in range(3):
                
                
    #if stacks are differentv
                
    if (stack1 != stack2):
                    
    #for every card in mixer-open
                    
    for card in range(len(stacks['mo'][stack2])):
                        
    move False
                        
    #if mixer-open has any cards
                        
    if (len(stacks['mo'][stack1])):
                            
    #if cards are of different color
                            
    if stacks['mo'][stack1][len(stacks['mo'][stack1]) -1][0] != stacks['mo'][stack2][card][0]:
                                
    #if of previous number
                                
    if stacks['mo'][stack1][len(stacks['mo'][stack1]) -1][1] - 1  ==  stacks['mo'][stack2][card][1]:
                                    
    #move
                                    
    move True
                        
    #prestavimo to in vse nad njo
                        
    if move:
                            print 
    'move'stacks['mo'][stack2][card], 'stack:'stack1'->'stack2
                            
    for curI in range(cardlen(stacks['mo'][stack2])):
                                
    stacks['mo'][stack1].append(stacks['mo'][stack2][curI])
                            
    del(stacks['mo'][stack2][card:])
                            if 
    not stopstep(stacksdepth 1)
                            break
    #                            if not stop: step(stacks, depth + 1)


        
    createRandomPositioning()
    step(stacks0)
    Thanks for all that told me stuff. I will get back to this probably.
     

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer