Hi, I need help with a bit of AI for a bejeweled type game. All I really need is for the computer player to find the best combination on the board. So, it's basically just scanning the board and analyzing the pieces. That's the problem though; Doing just that. I thought of looking for the best combination and then move towards a standard 3-in-a-row. Problem is that I might be able to get a 5-in-a-row in 2 moves but a 3-in-a-row in 1 move. Even if I look for the 2 or 3 move combination, the setup moves might trigger a 3-in-a-row combination which removes the initial 5-in-a-row. So, I'd need to know how the board would be affected with each move and take the changes into consideration. So, could anyone give some advice as to how I can go about making sure I find the absolute best combination - even if it takes 3 or 4 setup moves - without accidentally triggering a lesser combination. PS. I'm using C# 2008, if it matters. Thank you

It's just like Tic-Tac-Toe, my friend. Use a minimax tree with the "other player" being how the board would change in respose to your move. Run it out a few plys and pick your best option.

I thought of using minimax, but didn't have an "other player". Your suggestion makes sense, though. Didn't think of it like that.

Thanks alot!

Do you need to always find the best combo? That would be a bit too competitive, and way too unnatural wouldn't it?

I implemented something like this for my own match 3 grid game, but not as an AI. It's used to find hints, or detect if there are any possible moves left. What I do is have all my pieces reference back to the BOARD structure, and then check if the pieces on either sides vertically or horizontally match with a matching function on the pieces themselves that allows for 'wild cards'. Very easy.

It would probably work very convincingly for AI, or at least a starting point. The combos will work themselves into place 'naturally' as the AI randomly makes the matches itself.

Quote: Original post by bixarrio
So, I'd need to know how the board would be affected with each move and take the changes into consideration.

I would go with a simple breadth-first search.

Thanks for all the advice so far.

I have one little issue; I don't know what kind of blocks would be replacing the removed ones. The "hole" will be filled with blocks from above, but the top row is unknown until it's filled. I thought of trying every possible combination of blocks in that position, but I don't think that's a good idea. Any advice?

The secret to designing AI is to put yourself in the exact same situation. With your problem of "not knowing what blocks are coming next", what would you do as a player? You can't take them into account, obviously, so you can't plan for them. Create an "unknown" placeholder that would be filled in there. Your multi-turn plans have to utilize blocks that are known. Now, since you will replan every round, if something lucky DOES happen, you can replan accordingly. In the mean time, you are still setting up your good combo with the information that you had previously.