Any java devs interested in working on a MPQ Simulator?

NorthernPolarity

This is a long shot, but I figured what the hell.

Some time ago, I thought it would be cool if we could have some more accurate statistics regarding character abilities. For example, ever wonder how many cascades are actually caused by a surgical strike? What about what the probability is for activating Blade's thirst passive assuming that you avoid red matches for levels 4 and 5? There have been some scripts written for calculating the odds of some basic stuff like expected matches from Loki and tiles destroyed from X-Force.

Well, the only way we as a community can know the answers to these tantalizing questions is if we somehow recreated the MPQ game engine from scratch and ran a bunch of simulations on that. Well, I've had some time on plane rides to and from break to start writing that up, and here's what I have so far: https://github.com/NorthernPolarity/MPQSimulator. The base framework is pretty much there, but it's pretty buggy and doesn't actually work yet. With school starting back up, I'm going to have a lot less time to work on this, so I was wondering if there was anyone here that had Java experience and wanted to help complete the damned thing: otherwise you guys will probably have to wait until the end of the year before we can finally get these random, probably useless statistics about this sort of stuff.

simonsez

I applaud this effort, but aren't we crippled by the fact that there's a great deal of skepticism that tiles drop randomly from above? Isn't there a consensus that these drops are contrived to yield extra matches? Curious to know where you stand on this.

NorthernPolarity

simonsez wrote:

I applaud this effort, but aren't we crippled by the fact that there's a great deal of skepticism that tiles drop randomly from above? Isn't there a consensus that these drops are contrived to yield extra matches? Curious to know where you stand on this.

Yeah, thats the one snag that I'm not too sure about. If only there was a generous developer or representative from the company that could give some insight on how the tile dropping algorithm works... Even if the simulator isn't 100% accurate though, the relative numbers are probably good enough to allow us to reach some sort of conclusion regarding abilities, such as how many cascades level 3 dino purple causes compared to level 5, and whether or not the upgrade is worth it. The absolute numbers may not be important when all we care about is whether or not those 2 extra covers are worth.

Unknown

If the tile drops are not random the only other pattern that'd remotely make sense is that it gives slightly more weight to the color that is missing. But it's certainly not a very high weight, otherwise you'd see a board after Surgical Strike just keep on drop 3 of whatever color was eliminated on a regular basis, so there's really no reason to assume anything but random.

Unknown

There was a post a while back where one of the devs verified that the drops were random. I don't remember where, but I know it was re-posted in a thread not too long ago.

simonsez

Phantron wrote:

If the tile drops are not random the only other pattern that'd remotely make sense is that it gives slightly more weight to the color that is missing.

No it's not the only pattern, because that's not what I'm thinking they're doing. My assumption is something along the lines that the probability vector for a given tile is skewed such that there's a higher probability assigned to a color that matches an adjacent tile.

jojeda654

Here's a year old thread where tile drops is discussed. viewtopic.php?f=7&t=679

Relevant quotes:

IceIX wrote:

Misguided wrote:

I remember when the original Puzzle Quest came out and people cried foul that the AI was cheating because of the cascades, but Steve Fawkner at I.I. said the code was astonishingly simple and having the AI look ahead to see what was about to drop and making decisions based on that would have been crazy complex. Iirc, the original code in the first game didn't have any sort of streak breakers in it, either.

Correct, it did not. All it did is roll a random percentile, look up which value that was on a weighted table, and drop the right gem. This game does pretty much the same thing with a couple added minor streak breakers to figure out which tile to drop.

IceIX wrote:

Spoit wrote:

Streak breakers?

There's a bit of code that lessens the (already) low chance of getting more than 5 tiles of a single type in a row, and also a little code to increase the odds of a tile dropping of a certain color if there aren't any of that type on the board.

While the algorithm may have changed, it probably isn't anything too major.

NorthernPolarity

jojeda654 wrote:

Here's a year old thread where tile drops is discussed. viewtopic.php?f=7&t=679

Relevant quotes:

IceIX wrote:

Misguided wrote:

I remember when the original Puzzle Quest came out and people cried foul that the AI was cheating because of the cascades, but Steve Fawkner at I.I. said the code was astonishingly simple and having the AI look ahead to see what was about to drop and making decisions based on that would have been crazy complex. Iirc, the original code in the first game didn't have any sort of streak breakers in it, either.

Correct, it did not. All it did is roll a random percentile, look up which value that was on a weighted table, and drop the right gem. This game does pretty much the same thing with a couple added minor streak breakers to figure out which tile to drop.

IceIX wrote:

Spoit wrote:

Streak breakers?

There's a bit of code that lessens the (already) low chance of getting more than 5 tiles of a single type in a row, and also a little code to increase the odds of a tile dropping of a certain color if there aren't any of that type on the board.

While the algorithm may have changed, it probably isn't anything too major.

The changes to the algorithm do indeed seem minor. Now if only we had the exact percentages that they use to do this...

JamieMadrox

The streak breakers don't work. lol

I've had two matches this week where the AI destroyed an entire column and the gems that dropped were an entire column of the same colour.

simonsez

Jamie Madrox wrote:

The streak breakers don't work. lol

Gotta agree with you. I think somewhere in that little piece of code, they're multiplying when they should be dividing

Unknown

simonsez wrote:

I applaud this effort, but aren't we crippled by the fact that there's a great deal of skepticism that tiles drop randomly from above? Isn't there a consensus that these drops are contrived to yield extra matches? Curious to know where you stand on this.

no computer generated code can be truly random due to it requiring a numerical sequence (at least to the best of my knowledge

Demiurge_Will

NorthernPolarity wrote:

If only there was a generous developer or representative from the company that could give some insight on how the tile dropping algorithm works...

Just triple-checked in the code - there's no streak breaker, or increased odds if there are no tiles of a particular color on the board. There's always an exactly equal chance of each of the 7 tile types (except in certain missions in Chapter 1, before Team-Up tiles are introduced).

Sorry for the misleading information last year. Joe must have been thinking of another game in the PQ family - he's worked on all of them.

Unknown

Demiurge_Will wrote:

NorthernPolarity wrote:

If only there was a generous developer or representative from the company that could give some insight on how the tile dropping algorithm works...

Just triple-checked in the code - there's no streak breaker, or increased odds if there are no tiles of a particular color on the board. There's always an exactly equal chance of each of the 7 tile types (except in certain missions in Chapter 1, before Team-Up tiles are introduced).

Sorry for the misleading information last year. Joe must have been thinking of another game in the PQ family - he's worked on all of them.

So, if I read what you're saying correctly, IceIX's real name is Joe, then?

HailMary

Archimedes1902 wrote:

no computer generated code can be truly random due to it requiring a numerical sequence (at least to the best of my knowledge

Kinda, but "sufficiently random" is pretty easy to do.

Unknown

simonsez wrote:

Jamie Madrox wrote:

The streak breakers don't work. lol

Gotta agree with you. I think somewhere in that little piece of code, they're multiplying when they should be dividing

Nah, the ai just divides by zero.

simonsez

Archimedes1902 wrote:

no computer generated code can be truly random due to it requiring a numerical sequence (at least to the best of my knowledge

Depends what you mean by "random". It's random in the sense that it will produce a series of results that conform to a random distribution, but the actual numbers are generally predetermined based on the initial seed; but if you seed it with digits taken from your system clock, it's hard to see how this wouldn't satisfy whatever requirements you place on what "random" means.

pmorcs

With that straightforward an implementation of the tile drop logic, NP's simulator should probably already be capable of telling us the exact spread of odds on getting certain-sized cascades.

Unknown

I've built a good start on a simulator in C++ already. I hacked it together pretty quickly just to test out Devil Dino's purple, but it could easily accommodate other moves. My current implementation just counts initial matches; it doesn't cascade anything. One of the issues I have with cascading is where to place the critical tile on a match 5+. With just match 5 it's easy, but some abilities can yield some pretty funky shapes in a match 11 or so. Can anyone shed any light on that?

NorthernPolarity

sarlok5 wrote:

I've built a good start on a simulator in C++ already. I hacked it together pretty quickly just to test out Devil Dino's purple, but it could easily accommodate other moves. My current implementation just counts initial matches; it doesn't cascade anything. One of the issues I have with cascading is where to place the critical tile on a match 5+. With just match 5 it's easy, but some abilities can yield some pretty funky shapes in a match 11 or so. Can anyone shed any light on that?

I'm working on the algorithm being the top-left most intersection of two or more match-3s in the shape.

Dayv

HailMary wrote:

Archimedes1902 wrote:

no computer generated code can be truly random due to it requiring a numerical sequence (at least to the best of my knowledge

Kinda, but "sufficiently random" is pretty easy to do.

Especially when all you need is one out of seven possibilities, over and over again.

Dayv

NorthernPolarity wrote:

I'm working on the algorithm being the top-left most intersection of two or more match-3s in the shape.

I think I've seen them in the top right of some shapes, such as an inverted U of eight tiles.