another pesky algorithm

Discussion in 'Game Development (Technical)' started by ztownsend, Aug 19, 2004.

  1. ztownsend

    Original Member

    Joined:
    Aug 12, 2004
    Messages:
    21
    Likes Received:
    0
    following on from cliffski's request, I've got another problem that I know is simple but I can't quite get my head round it. Its been a long time since I did anything like this!!

    Basically, I want to calculate all possible moves for say upto 40 pieces in a boardgame type scenario. The pieces can each have only two possible moves (e.g.) one space left, or one space right, but can move in any order.
    In fact it is possible that piece 5 might go left 3 times, then piece 2 might go right 7 times.

    With this basic premise I want the routine to go through each of the possible outcomes.

    I started off by saying, that there are actually 3 possible moves for each piece - to include NO MOVE. i.e. if we take each piece in turn, then each piece can go either left, or right, or stay still. This allows us to have the possibility that it might be the 6th piece that moves first, on the basis that the first 5 pieces stayed still.

    Hopefully, I've explained it reasonably clearly. Trying to write a simple alogorithm that goes through each of these moves, or can just write them to an array is confusing the hell out of me though. I've spent a day on it so far, and I keep going round in circles!!

    It seems there are a lot of different outcomes. Even with just 4 pieces, each with 3 possible moves, I reckon there are 81 possible start moves in total. Then allow this to re-iterate for say 10 times, i.e. 81 possible moves each time = 810 moves.

    3^4 (3 to power 4) = 81

    and now I've confused myself again. I can't decide whether this is just so simple, I'm missing the plot, or whether I just can't get it straight in my head.

    Can anyone help??

    Zach
     
  2. ztownsend

    Original Member

    Joined:
    Aug 12, 2004
    Messages:
    21
    Likes Received:
    0
    Here's a quick representation of how I see it working for just two pieces on the board. These are all the possible first moves, and then each move after this, they need to take another possible move, so that each possible move in sequence is exhausted.

    A,B
    0,0
    1,1
    2,2
    0,1
    1,0
    0,2
    2,0
    1,2
    2,1

    Two pieces on the board, A and B
    The numbers underneath are the possible move for each piece:
    0 = no move (stay still)
    1 = go right
    2 = go left

    so 1,0 means
    A goes left and B stays still

    9 possible moves each turn of the game.

    This needs to be re-iterated for say 10 turns, to see where each piece will end up.
     
  3. grimreaper

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    35
    Likes Received:
    0
    Building up a tree of all the possible moves is consumes memory like crazy especially if stored ineffeciently; you would need to specify a maximum depth to limit the number of combintations.

    Chess games do something similiar - I suggest you look through the code of a freeware chess game.

    Why do you need this for exactly?

    grimreaper
     
  4. ztownsend

    Original Member

    Joined:
    Aug 12, 2004
    Messages:
    21
    Likes Received:
    0
    I agree, say 10 turns max. It doesn't have to store the moves, if it can calculate them on the fly. It's for a puzzle-type game, nothing as complicated as chess.

    I'd have though a simple re-iteration of for-next loops would be able to go through each move, but I can't quite get there...
     
  5. grimreaper

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    35
    Likes Received:
    0
    Ofcourse it wont! At time t = 0 there are 2 possible moves left (0) or right (1). So at time t=0 you have the following:

    |
    / \
    0 1

    At t+1 you have the following:

    |
    / \
    0 1
    / \ / \
    0 10 1

    So at time t+1 you have doubled the number of leaf nodes from 2 to 4. You cant have a fixed size array - you need a tree.

    You still havent said why you need to know the all possible positions of the pieces at t+10. The only reason for this, AFAIK, is for a computer AI to choose the best move for playing.

    grimreaper
     
  6. Sunshine

    Original Member

    Joined:
    Aug 7, 2004
    Messages:
    173
    Likes Received:
    0
    If it is true that each piece can stay still, this indicates that there is a scenerio in which none of the pieces move, thus the player can pass.

    Which makes the formula:
    (2 ^ PIECES)+1 --since there are really only 2 moves plus a possibility of pass

    heres the outcome
    Pieces Possible moves
    1 3
    2 5
    3 9
    4 17

    Taking for granted these things:
    1)Each piece can only move 1 space per turn.
    2)During each turn only one piece can move. (or pass)
    :cool: Hope that helps? or maybe now you have confused me too ;)
     
  7. ztownsend

    Original Member

    Joined:
    Aug 12, 2004
    Messages:
    21
    Likes Received:
    0
    Ah, yes, I'm confused even more!

    the only reason for me including the (no move) move, is to allow another piece to move first, i.e. the possibilty exists that any of the 40 pieces can move first, so my idea is to allow the other 39 pieces to have a (no move) as their move. E.g. using a loop that runs through all the pieces, it will asign (no move) to all but the piece that it wants to make the FIRST move - does that make sense?, sorry its 8:30pm here, and I've had a few drinks!!

    Maybe this is not the best way to do it -
    to recap, each piece can move left or right. But of the 40 pieces, anyone can move at any different time. e.g. piece 5 can go left, then left again, then piece 8 can go right, then piece 5 can go right and then left, etc, etc.

    I still think its 3^pieces per turn, but then my maths is very rusty.

    grimreaper - its a simple puzzle game - AI I don't think will work, as there are other things going on that would make an AI based routine even more complicated. This should be a simple number crunching algorithm. The idea of the routine is to calculate if within a certain no. of moves a certain situation can exist. Now, I'm making what should be a simple scenario sound complicated - LOL.

    sunshine - yes, each piece can only move once each time, but, next turn , the same piece could make the same move, or another move. Each turn, ANY ONE piece can move either left or right. Next turn, ANY ONE piece can move either left or right.

    I'm sure a simple algorithm is the way forward, but my simple brain won't go there, especially with alcohol involved!

    Zach
     
    #7 ztownsend, Aug 19, 2004
    Last edited: Aug 19, 2004
  8. Gilzu

    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    368
    Likes Received:
    8
    Do a search on minimum/maximum search trees and alpha/beta trees, Learnt those on my Artificial Inteligence & Prolog course in uni.

    What you so, is make a heuristic function for every situation (min - good for you, max - good for your enemy) and then search the tree down to a limited level.

    Then comes the alpha&beta algorithem, which cuts the complexity from N to logN. What it basically do, is remember the best "route" to a board, and stops checking a sub tree when it sees its not better than yours.

    I think I still have even more complex program (but in prolog) that calculates up to 10 (!) moves in Hexagon.
     
  9. mkovacic

    Original Member Indie Author

    Joined:
    Jul 28, 2004
    Messages:
    127
    Likes Received:
    0
    Are you just looking to play through all possible combinations?

    Code:
    void MovePiece(int pieceIndex, int direction, int depth)
    	{
    	 //do your move-doing/isValidMove checking stuff here
    	 //... 
    	 
    	 //do your board evaluation here
    	 //...
    	 
    	 //check for recursion depth
    	 if (depth==0)
    	 	return;
    	 	
    	 //do all possible next moves
    	 for(int i=0; i<NUMPIECES; i++)
    	 	{
    	 	 MovePiece( i, DIRECTION_LEFT, depth-1 );
    	 	 UndoMove( i, DIRECTION_LEFT );
    	 	 MovePiece( i, DIRECTION_RIGHT, depth-1 );
    	 	 UndoMove( i, DIRECTION_RIGHT );
    	 	}
    	}
    	
    int main
    	{
    	 int depth = 10;
    	 InitBoard();
    	 
    	 for(int i=0; i<NUMPIECES; i++)
    	 	{
    	 	 MovePiece( i, DIRECTION_LEFT, depth );
    	 	 UndoMove( i, DIRECTION_LEFT );
    	 	 MovePiece( i, DIRECTION_RIGHT, depth );
    	 	 UndoMove( i, DIRECTION_RIGHT );
    	 	}
    	 	
    	 return (0);
    	}
    Is that it? Modulo bugs, ofcourse. ;)
     
  10. TamLin

    Original Member

    Joined:
    Aug 20, 2004
    Messages:
    31
    Likes Received:
    0
    Here's the math as I understand it:

    VARIABLES
    x = # of pieces
    m = # of moves
    n = # of turns

    Total # of outcomes = ((m^x)*x!)^n

    The x! ("x factorial") component accounts for the sequence in which the pieces move in a given turn (forget about the imaginary "no move" action; it will throw your math off).

    So, if there are 4 pieces and 2 moves, the number of possible outcomes for a single turn is (2^4 * 4!)^1 = 16 * 24 = 384.

    After 10 turns, the number of possible outcomes is 384^10 = 69712754611742420055883776 (a 26 digit number!).

    For 40 pieces, the number of paths after 10 turns is (2^40 * 4!) ^ 10 = a 600 digit number that I daren't reproduce here. ;-)

    Of course, the formula I've given tells you only the number of possible outcomes; it doesn't generate the outcomes.
     
    #10 TamLin, Aug 20, 2004
    Last edited: Aug 20, 2004
  11. ztownsend

    Original Member

    Joined:
    Aug 12, 2004
    Messages:
    21
    Likes Received:
    0
    Thanks for the replys. I think you are all on the right track.

    Having done a couple of experiments, it looks like a routine to go through each possible move would simply take far too long. Maybe a minute would be okay, but even a routine like mkovacic's takes far too long on my PC when you have a few pieces and 10 turns.

    On one hand, my brain was saying that the numbers are too big, and its gonna take to long to calculate, and on the other hand, it was saying that this is a SIMPLE problem - each piece can only go left or right - and a simple number cruch/tree/path algorithm should pump out the answer in a few seconds.

    Ah well, I think its the former. If anyone can tell me I'm wrong, please tell me now!! :)

    Zach
     
  12. mkovacic

    Original Member Indie Author

    Joined:
    Jul 28, 2004
    Messages:
    127
    Likes Received:
    0
    Well, depending on the game itself you can easily discard entire sub-trees. For example, if moving any piece N times to the left followed by moving the same piece N times to the right is equal to no-op then you just don't recurse any further when you detect that. Or if you have a specific goal position, you can come up with a distance heuristic and prefer moves that minimize the distance metric (like A* in pathfinding). This is what we do for Light&Shadows' "hint" solver.
     

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