Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411275 Posts in 69323 Topics- by 58380 Members - Latest Member: bob1029

March 28, 2024, 06:24:55 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)AI, for an arcade puzzle like Magical Drop
Pages: [1]
Print
Author Topic: AI, for an arcade puzzle like Magical Drop  (Read 1098 times)
intertum
Level 0
**



View Profile WWW
« on: November 28, 2018, 06:18:44 PM »

Hello.
I'm trying to make a clone of this game



I almost have the basic gameplay with a single player, now the problem is the AI, at first I thought it will be easy but now I realize that may be very complex (or maybe not).

I have read about some IA techniques, decision trees, MinMax algorithm, and of course, Finite State Machines. But none of those seem to fit the problem (MinMax as far I could understand is for turn-based board games: player1 then player 2, player 1 again and so on).
Does anyone have some advice or guidance before I plunge into madness?, maybe it is very easily achievable but there is something I'm not seeing.
Thank you very much.
Logged

\"2V Hoverbike\"
Glyph
Level 10
*****


Relax! It's all a dream! It HAS to be!


View Profile
« Reply #1 on: November 28, 2018, 06:46:41 PM »

Here's an example of a general strategy a human might employ in one of these games:
Find a stack at the top level that can be combined to make 3 or more somewhere else, pick it up, and drop it off. If making 3 or more requires moving other pieces first, do that instead.

How would you implement this in code? It really depends how elaborate you want to get. You could just pick a random stack and find another stack that will work with it. Then if none of them work when checking this way, maybe randomly move stacks or actually do some checking to see what stack should move where to allow a valid move from there. You can expand this logic to more moves fairly easily as well. If you want to get more intensive, you can do this same basic process, but instead of choosing the first possibility, assign weights to plans of action. Depending on the amount of moves/real time needed to perform the action, the weight could lessen. This naturally biases itself towards quick sequences of inputs. Once all the weights are defined, you just need to pick one course of action randomly.

As a side note, you can implement difficulty levels very easily within this framework simply by lessening the efficacy of weighting or, even easier, controlling the speed the CPU executes its plan at.

I can't say whether or not the strategy and implementation I detailed here are truly optimal though, as there are other strategies to consider depending on the game (like setting up combos). With a weighting system, you can also assign actions like setting up for a combo weights, and you'll have to determine what sequence of moves is needed for that. In general I don't think it matters terribly much though - in a game like this, you can probably scale the difficulty from easy all the way to impossible with simple AI and just a speed modifier on the CPU's execution.
Logged


intertum
Level 0
**



View Profile WWW
« Reply #2 on: November 30, 2018, 09:24:35 AM »

Hello, thanks for your answer.

Yeah if you look closer to the IA in the example game it's quite dumb. It does not seem to go very deep in things like changing the pieces to make combos, in fact, the difficulty levels seem just to be increasing the CPU speed and the punishment row spam for the player.

I've thought of  "analyzing" the entire board and then "weight" the possible moves taking in account the moves/time consumed against pieces or points won, but it can get very complex and it seems to be an overkill.
I'm almost sure the AI in this kind of games is not very complex and just follow a certain pattern (with a little randomness), but I can figure out.
Logged

\"2V Hoverbike\"
BorisTheBrave
Level 10
*****


View Profile WWW
« Reply #3 on: December 01, 2018, 03:07:32 PM »

If you can understand min max, then you aready understand more than you need.

Firstly, your game is effectively turnbased. Each turn is making a move of picking up or droping a column. The fact that the moves occur in real time is irrelevant to the goodness of the move - you can easily add artifical delays after you have the AI decide its next move. Secondly, your AI can do lookahead simiar to min-max - out of all possible moves, it rates what the board looks like after the move, and picks just a few of those boards to look ahead further.

Or in otherwords, you want a recursive search routine in the space of possible boards, with a heuristic for rating boards (e.g. number of cubes left on the board)
Logged
intertum
Level 0
**



View Profile WWW
« Reply #4 on: December 04, 2018, 04:45:09 PM »

Hey, thank you so much for your answer. I will look more closely to minmax then.

Quote
you want a recursive search routine in the space of possible boards, with a heuristic for rating boards (e.g. number of cubes left on the board)

This is where I get lost. Min max seems straightforward, but I have no clue of how to simulate the resulting boards (without a very very complex code).
Logged

\"2V Hoverbike\"
BorisTheBrave
Level 10
*****


View Profile WWW
« Reply #5 on: December 08, 2018, 09:56:37 AM »

Quote
simulate the resulting boards
I dunno what to tell you. You managed to write the game in the first place, how is this any harder.
Just, like, have an array of tiles, and move them around like you do in the actual game. You don't need bother with graphics, user interaction or timing/animation, so sounds straighforward to me.
Logged
shay
Level 0
**


View Profile
« Reply #6 on: December 11, 2018, 09:52:02 PM »

Hi Intertum,

New Retro Studio will be happy to assist you with improving the game logic (for free).

PM me if you want to discuss how your game can be improved.

Thanks,
-Shay
Logged
intertum
Level 0
**



View Profile WWW
« Reply #7 on: December 13, 2018, 06:56:48 PM »

Hey, thanks. Sure, message sent.
Logged

\"2V Hoverbike\"
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic