What would be the most efficient way to solve a bejeweled type game, with emphasis on combos i.e 3 x 3 , 4x 3 x 3. Id rather not bruteforce each move.
Any Ideas, I know info is short but basicly searching a grid to find the best move to get a combo in one move.
Thanks
Blair
Solving Bejeweled type game
21,607
June 27, 2010 05:23 PM
Finding the best combo in a single move is an extremely small problem for a computer to solve by brute force. Did you give it a try?
If you want to maximize the probability of getting a good combo (since you don't know what jewels are coming down), it gets trickier, and you would have to define what you want very carefully.
If you want to maximize the probability of getting a good combo (since you don't know what jewels are coming down), it gets trickier, and you would have to define what you want very carefully.
June 27, 2010 05:30 PM
I was thinking of going through each possible move for example each 3 x 3 represented like:
xx0x00
and
x0
0x
0x
and so on..Seems a very hard way to do it...Its not exactly bejeweled but very similar in terms of gameplay.
Thanks
Blair
xx0x00
and
x0
0x
0x
and so on..Seems a very hard way to do it...Its not exactly bejeweled but very similar in terms of gameplay.
Thanks
Blair
3,556
June 27, 2010 05:34 PM
The bruteforce method is negligible. I've been doing it in my game for ten years, and it wasn't any trouble back then.
Your playing field will only be a small grid 8x8,10x10,12x12, or whatever size you choose. I treat every piece in there as it's own object that can do it's own check with it's neighboring parts for possible matches or moves.
I only run it at the appropriate times, but I could easily run it every frame and not feel a thing. This type of game is very cheap to run on the CPU, and just checking that small array for matches and move possibilities is trivial compared to the processing that other types of games have to do on a per frame basis.
If you want, you can simply find all the possible moves, and simulate them. Then execute the move that has the highest score out of all possible moves.
Your playing field will only be a small grid 8x8,10x10,12x12, or whatever size you choose. I treat every piece in there as it's own object that can do it's own check with it's neighboring parts for possible matches or moves.
I only run it at the appropriate times, but I could easily run it every frame and not feel a thing. This type of game is very cheap to run on the CPU, and just checking that small array for matches and move possibilities is trivial compared to the processing that other types of games have to do on a per frame basis.
If you want, you can simply find all the possible moves, and simulate them. Then execute the move that has the highest score out of all possible moves.
June 27, 2010 06:10 PM
Ill give it a shot, When you say you sorted them as object doe you mean each having a position in the array stored in its own class so it knows where it is?
3,556
June 27, 2010 06:30 PM
Quote: Original post by Catkill
Ill give it a shot, When you say you sorted them as object doe you mean each having a position in the array stored in its own class so it knows where it is?
My game has just has an x*x array of class instances, and when it's time to check, I just for loop over them.
Each object on the board knows it's x, and y grid positions (same as their array position), their color, and other things. Then I can just have each game object look at it's own neighboring objects and decide if they can make a move to score.
I did it this way because I found writing the code to be easier. It made more sense, and easier to write code for the situation of every object on the board doing it's own check.
for (y = 0; y < BoardSize; ++y){ for (x = 0; x < BoardSize; ++x) { Board[x,y].CallWhateverFunctionToCheckForAPossibleMove() }}You can simply store a list of which objects can be moved to get a score, and then simulate them on a copy of the current state of the board you are playing on. Store the scoring potential for that move, sort them by highest, and execute the highest one. You can even skip the sorting step by just replacing a variable with the highest potential move so far, and keep updating it as you check possible moves if they end up with a higher potential score.
//example move classclass Move{ int x; int y; int Direction; int Score;}for (list of moves iteration){ //try the move on a copy of the current board //don't over write the copy, you'll need it for each //of these tests //--- //store the score from the simulation //--- //if the score is higher than whatever was stored //as the highest, then replace it with this info }//Now act on whatever the best Move was
183
July 06, 2010 06:09 PM
I bet Mike.Popoloski I could write a Bejeweled solver in an hour in C#. It's a little brute force, but it works. Here's the code for the "AI".
The "Board" class simply contains a one-dimensional array of gem colors. It starts somewhere on the board, checks the neighboring gems, uses a different "strategy" depending on what works (or if it even has a color as determined by the samples it takes from the Bejeweled screen), and returns two points--one where the gem is, the other the vector to move it by. We favor "hypercubes" by checking those combos first (5 in a row, 4 in a row, etc.).
In this case, the brute force solution is not that bad and if elegance isn't your concern, it works very well.
I see you ask for combos, though, for which I do not have an example. To handle combos, you'd need to predict where the gems end up based on your move. You could do some array maniupulation to "move" the gems after each move, then run a separate algorithm to see what lines up using functions like those I provide (naturally, however, you will not have anything for the new gems entering the board, so you'll have to keep track of that). Again, brute force, but not bad. You can get into more complex searches if you wanted to, but simple array math and checking and re-checking is pretty fast on its own.
If you are trying to make something that plays Bejeweled specifically, I wouldn't even bother with that approach since you can simply make lots of moves very fast and things are always blowing up and messing with your view anyway.
Hope that helps.
-- Steve.
private static Point[] DiagonalNeighbors(Board board, int GemNum){Point[] p = new Point[2];p[0] = new Point(GemNum / 8, GemNum % 8);p[1] = new Point(0, 0);int[] neighbors = new int[4];// No color, returnif (board.Gems[GemNum].Color == GemColor.None)return p;// Corner gem, no diagonal neighborsif (GemNum == 0 || GemNum == 7 || GemNum == 56 || GemNum == 63)return p;neighbors[0] = GemNum - 9; // up leftneighbors[1] = GemNum - 7; // up rightneighbors[2] = GemNum + 9; // down rightneighbors[3] = GemNum + 7; // down leftif (CheckGems(board, neighbors[0], neighbors[1], GemNum)){// upp[1] = new Point(0, -1);}if (CheckGems(board, neighbors[1], neighbors[2], GemNum)){// rightp[1] = new Point(1, 0);}if (CheckGems(board, neighbors[2], neighbors[3], GemNum)){// downp[1] = new Point(0, 1);}if (CheckGems(board, neighbors[0], neighbors[3], GemNum)){// leftp[1] = new Point(-1, 0);}return p;}private static Point[] SlideInto(Board b, int GemNum){Point[] p = new Point[2];p[0] = new Point(GemNum / 8, GemNum % 8);p[1] = new Point(0, 0);if (b.Gems[GemNum].Color == GemColor.None)return p;bool A, AL, AR, B, BL, BR, L, LA, LB, R, RA, RB;A = Above(b, GemNum);AL = AboveLeft(b, GemNum);AR = AboveRight(b, GemNum);B = Below(b, GemNum);BL = BelowLeft(b, GemNum);BR = BelowRight(b, GemNum);L = Left(b, GemNum);LA = LeftAbove(b, GemNum);LB = LeftBelow(b, GemNum);R = Right(b, GemNum);RA = RightAbove(b, GemNum);RB = RightBelow(b, GemNum);// favor stars and hypersif ((A && AL || A && AR || AL && AR) && (GemNum > 8)){p[1] = new Point(0, -1);return p;}if ((B && BL || B && BR || BL && BR) && (GemNum < 55)){p[1] = new Point(0, 1);return p;}if ((L && LA || L && LB || LA && LB) && (GemNum % 8 != 0)){p[1] = new Point(-1, 0);return p;}if ((R && RA || R && RB || RA && RB) && (GemNum % 8 != 7)){p[1] = new Point(1, 0);return p;}// otherwise defaultif ((A || AL || AR) && (GemNum > 8)){p[1] = new Point(0, -1);return p;}if ((B || BL || BR) && (GemNum < 55)){p[1] = new Point(0, 1);return p;}if ((L || LA || LB) && (GemNum % 8 != 0)){p[1] = new Point(-1, 0);return p;}if ((R || RA || RB) && (GemNum % 8 != 7)){p[1] = new Point(1, 0);return p;}return p;}private static bool Above(Board board, int GemNum){return (CheckGems(board, GemNum - 16, GemNum - 24, GemNum));}private static bool AboveLeft(Board board, int GemNum){return (CheckGems(board, GemNum - 9, GemNum - 10, GemNum));}private static bool AboveRight(Board board, int GemNum){return (CheckGems(board, GemNum - 7, GemNum - 6, GemNum));}private static bool Left(Board board, int GemNum){return (CheckGems(board, GemNum - 2, GemNum - 3, GemNum));}private static bool LeftAbove(Board board, int GemNum){return (CheckGems(board, GemNum - 9, GemNum - 17, GemNum));}private static bool LeftBelow(Board board, int GemNum){return (CheckGems(board, GemNum + 7, GemNum + 15, GemNum));}private static bool Below(Board board, int GemNum){return (CheckGems(board, GemNum + 16, GemNum + 24, GemNum));}private static bool BelowLeft(Board board, int GemNum){return (CheckGems(board, GemNum + 7, GemNum + 6, GemNum));}private static bool BelowRight(Board board, int GemNum){return (CheckGems(board, GemNum + 9, GemNum + 10, GemNum));}private static bool Right(Board board, int GemNum){return (CheckGems(board, GemNum + 2, GemNum + 3, GemNum));}private static bool RightBelow(Board board, int GemNum){return (CheckGems(board, GemNum + 9, GemNum + 17, GemNum));}private static bool RightAbove(Board board, int GemNum){return (CheckGems(board, GemNum - 7, GemNum - 15, GemNum));}private static bool CheckGems(Board b, int g1, int g2, int g3){if ((g1 > 63 || g1 < 0) || (g2 > 63 || g2 < 0) || (g3 > 63 || g3 < 0))return false;if (b.Gems[g1].Color == b.Gems[g2].Color && b.Gems[g2].Color == b.Gems[g3].Color)return true;return false;}}The "Board" class simply contains a one-dimensional array of gem colors. It starts somewhere on the board, checks the neighboring gems, uses a different "strategy" depending on what works (or if it even has a color as determined by the samples it takes from the Bejeweled screen), and returns two points--one where the gem is, the other the vector to move it by. We favor "hypercubes" by checking those combos first (5 in a row, 4 in a row, etc.).
In this case, the brute force solution is not that bad and if elegance isn't your concern, it works very well.
I see you ask for combos, though, for which I do not have an example. To handle combos, you'd need to predict where the gems end up based on your move. You could do some array maniupulation to "move" the gems after each move, then run a separate algorithm to see what lines up using functions like those I provide (naturally, however, you will not have anything for the new gems entering the board, so you'll have to keep track of that). Again, brute force, but not bad. You can get into more complex searches if you wanted to, but simple array math and checking and re-checking is pretty fast on its own.
If you are trying to make something that plays Bejeweled specifically, I wouldn't even bother with that approach since you can simply make lots of moves very fast and things are always blowing up and messing with your view anyway.
Hope that helps.
-- Steve.
337
July 07, 2010 09:32 AM
In the past i've programmed many many bejewled and clones solver.
Depeneding on the game and its special scoring you need to "code-in" the right strategy besides the brute-force algorith which is always straight forward:
- make a list of all possible moves
- "execute" each move in memory and consider the resulting board and scores, do this until no score is made.
- take the move with the best score
Witht the above strategy you will simply have a good solver which will, depending on the game, beam you up in the highscore list.
As for bejewled you need additional strategy to "bring" the board to good positions which will have a higher propability to give combos etc.
Depeneding on the game and its special scoring you need to "code-in" the right strategy besides the brute-force algorith which is always straight forward:
- make a list of all possible moves
- "execute" each move in memory and consider the resulting board and scores, do this until no score is made.
- take the move with the best score
Witht the above strategy you will simply have a good solver which will, depending on the game, beam you up in the highscore list.
As for bejewled you need additional strategy to "bring" the board to good positions which will have a higher propability to give combos etc.
183
July 07, 2010 08:17 PM
Quote: Original post by AticAtac
As for bejewled you need additional strategy to "bring" the board to good positions which will have a higher propability to give combos etc.
Right, I considered trying that at first since that's a very computerizable task, but I never tried to implement it and favored the brute force approach instead.
Basically, take my solver above that operates on the 1-D array derived from the 8x8 Bejeweled screen. Make a move and determine what gems are affected. Two cases arise:
You eliminated gems horizontally:
Let's say you eliminated gems 10, 11, and 12. Now, gems 10 - 8 = 2, 11 - 8 = 3, and 12 - 8 = 4 are affected. These gems will move down and become gems 10, 11 and 12. Gem[10] = Gem[2]; etc. Gem[2] = null (or something that your program disregards).
You eliminated gems vertically:
You eliminated Gems 10, 18, and 26. Gems 10 - 8 = 2, 2 - 8 = -6, and -6 - 8 = -14 are affected. You throw out the two negative indices because that doesn't make sense. You drop gem 2 down by doing Gem[26] = Gem[2].
Once you move your board, you check to see if anything lines up, then run the algorithm again.
---
Steps:
1. Make move (the code I gave you).do 2. Move gems 3. Check board for horizontal/verticals. Remember the chain lengths of each of these and keep a score.loop---
Do that many times over until you've analyzed every move and pick the one that yields the most combos.
Of course, stuff dropping down may affect your best move, but in Bejeweled you need only 12 gems eliminated in one move to get a multiplier to drop down, so running with the best move without anticipating randomness or setting up the board in a certain way would get you pretty far in that game.
In short, I think I'm overanalyzing this, and in all my time spent thinking about how to beat Bejeweled, I could have programmed Bejeweled on Steroids. Still, this is fun. The message is: "brute force" isn't so bad after all, and in this case you don't need a supercomputer to run the solver.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
