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
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.
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
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...
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
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) Hope that helps? or maybe now you have confused me too
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
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.
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.
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.
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
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.