A Worthy Opponent

22 12th August 2015 Justin Libby

 

"’The computer cheats.' - That's what they say in the forums."

"Well, does it?" I asked myself.  It was my second month at Demiurge Studios, and I was curious how the Marvel Puzzle Quest game engine worked. It was lunchtime, and I was hounding my fellow engineers with questions: “Does it look at the upcoming tiles?  Does it try to set up combos?  Does it target player tiles?  Oh, oh, oh! Does it intentionally drop new tile colors to mess up your turn?”

I was a big fan of D3's Puzzle Quest: Challenge of the Warlords. I remember feeling waves of frustration playing boss battles. At one point, I nearly snapped my DS in half. But I noticed that opponents in MPQ felt different.

Looking for answers, I dug through our code to the place where the computer chooses a pair of tiles to swap.  The flow for the computer's turn is:

  1. Make a list of all valid swaps available on the visible board
  2. Assign a score to each swap
  3. Sort the list by the score
  4. Pick the best swap, or randomly from the top swaps if there's a tie

Here's the code that drives the score for the swap sort comparator:

    Float GetScore() const
    {
        return (m_cTilesMatched * 10.f) + (bChargesAbility ? 1.f : 0.f);
    }

The boolean value bChargesAbility is true if the match will charge up an ability on the computer's team. The integer m_cTilesMatched is the number of tiles matched after searching in a straight line, up to 4 tiles. The section that tallies up the number of tiles was written to check one tile behind the swap and two tiles ahead, so it doesn't look far enough for match‑5s in a line.  Since it only checks along one axis, it can't see L and T shaped match‑5s.

This scoring system means that the criteria for selecting a swap are:

  1. Number of matched tiles in a straight line, up to 4
  2. Does the match charge an ability on the computer's team?

That's it.  That's all the logic.  The first rule takes precedence over the second: the computer will always take a match‑4 over a match‑3. If there are two match‑4s available, the computer will prefer the one that will charge its abilities.  If there are multiple best swaps, it will randomly choose one.  Sometimes the match-4 also results in a match‑5, but the computer doesn't “see” the match-5.

The computer does not look ahead.  It does not try to set up combos. The computer has two very simple rules that could be applied equally well by a human looking at the same board.

The computer does not try to screw up your turn by dropping bad tiles either. Each new tile is selected at random, individually, without any feedback from the swap‑selection code.  I did learn that Team-Up tiles drop with a slightly lower rate than color tiles.  Each color is weighted with a value of 1.0, while Team‑Up tiles are weighted with 0.75.  That means there's about an 11% chance that a new tile will be a Team‑Up, and about a 15% chance for each of the colors.

I had answered my questions: the game was not cheating. So what made players think otherwise?

The computer is only guilty of being complete.  It never misses a match‑4. After years of playing match-3 style games, my eyes still miss match‑4s and match‑5s once in a while.  The computer, however, never makes a mistake.  This creates the illusion of an opponent that is more clever than it really is.

On top of that, as a player, we're guilty of holding a cognitive bias, only noticing when the random number generator doesn't go our way.  When I get a long cascade of matches it feels great, but it also feels expected because I’m in control. When the computer gets the same cascade, I'm left feeling powerless and enraged. That sense of frustration is what I remember later on.

I talked to Kevin, the development director on MPQ who is also an engineer, about the enemy‑turn logic. He said that he had written it for an early build of the game, then never got a chance to revisit it. Time passed, and the game got into the hands of players. Players thought the game's swap choices were already too good. That stifled any attempt to fix the underpowered computer opponent.

 

Faster Better Stronger

Convinced I could make things better, I started writing code.  I knew it would be a lot of extra work to teach the computer to set up combos for future turns.  The computer wouldn't know where a player was going to make a swap.  So I limited myself to information available looking at the current board. I added more criteria to the swap decision:

  1. Number of matched tiles, up to 7, including L and T shapes and double match-3s
  2. Does the match include a Critical tile?
  3. Does the match destroy a player-owned tile?
  4. Does the match not destroy a computer-owned tile?
  5. Does the match charge an ability on the computer's team?
  6. Does the match not use the team's weak colors?

I chose the rules and ordering based on the logic I used in my head when I was playing the game.  Using different score weights, designers could adjust the rule ordering, or turn rules on or off for different battles. The computer could be told to intentionally make mistakes, randomly. If desired, enemies would always choose the worst moves instead of the best.

Using the new default rules, fully enabled, in the order listed above, I tried playing a test build of the game.  It felt much harder.  The computer wasn't destroying its own Bombs and Strike tiles right away.  I yelped as the computer targeted my Protect tiles and Countdown tiles.

It was clear that changing the enemy-turn heuristic would have a strong effect on gameplay and balance.  After a discussion with the team, we decided to put my new code on ice.  As much as I wanted to make the computer opponent better, changing the way the computer plays would have unforeseen consequences, no matter how much testing we did.

The decision is common in established software: changes have a cost; don't make big modifications unless you understand the cost and the effect.  A change has echoes and ripples that will come back as bugs and follow-up feature requests.  The more the code is connected to other parts of the code base, the further those ripples will propagate.

What's more, the game is meant to be fun. If the game is too difficult, players would stop playing. Or worse, they would smash their phones to the ground in frustration. Making a good game means riding the line between winning with ease and losing repeatedly.  Good games feel like running down a knife's edge, with skill and luck buffeting the player from both sides.

What do you think? Would a more clever opponent make MPQ better? What about a random and unpredictable foe? Or are things fine the way they are now?

At the end of the day, MPQ is about completing many matches quickly, and then breaking for a while.  This is good from the perspective of a player that can dedicate time in bursts.  This can be in excess of 10 or even 20 fights at a time, depending on the PvE, DDP, and PvP.  By fighting weaker opponents (simply as a result of intelligence, levels, while important, do not contribute as much to difficulty as raw intelligence would), a player can feel an accomplishment in winning a seemingly difficult matchup (e.g. higher level enemies) while still having the capability (health packs and characters left) to play more matches before running out. 

By facing truly tougher enemies - many of which will actually be more capable than true players (even though players are typically intelligent enough to heuristically determine their best valued matches, they will always occasionally miss things - something a computer will be incapable of), players will become frustrated at the difficulty of the game and will lose health packs FAR quicker - even if you lower the enemy levels to below the player’s own (which has the affect of de-motivating the player by playing poorly against numerically ‘weaker’ enemies).  Even if you successfully balanced the enemy levels accordingly (which would be an incredible pain), the game will simply lack too much of that ‘reward’ value that defines a game as fun.

Alternatively, you could keep everything capable as-is today and then do one or more of the following:
1)Add a ‘hard mode’ that could be selectively enabled in the settings - this would simply change the logic from current to the more complicated and more difficult logic you added (possibly lowering enemy levels as well to max out appropriately at their * value) in exchange for higher rewards - be it higher ISO for a win or something else that truly feels rewarding for the appropriate difficulty.
2)Add a ‘hard mode’ to the prologue to allow the entire story to be re-completed for new rewards.  This has a HUGE advantage in giving the players a fairly large amount of new stuff to do that should be fairly low in effort to accomplish.
3)Add a new type of fight - similar to the wave system, where only a few matches out of a PvE take use of it - wherein the player fights some sort of hyper-genius oriented villain (Thanos, Mandarin, MODOK, or my favorite - Zombie Reed Richards please <3)
4)Add a new type of once/week event where the player must complete so many matches (similar to ant-man event) at this higher difficulty in exchange for a stronger reward.  Maybe a high HP reward (250?), or perhaps a random un-maxed 3* cover (may be annoying to build something for a special type of reward like that).  Or perhaps make it a once/month event with a guaranteed 4* reward.

These are just my 2 cents, but from a game-design perspective - higher difficulty should result in higher reward.

Aug 12, 2015

I just realized that my name looks like the engineer referred to by the author.  That is not the case, my bad.  While I do also happen to be an engineer that has worked on games, I’ve never worked on anything nearly as successful.

Aug 12, 2015

Here are my thoughts which I asked a while ago in the Monthly Q&A. Generally, making the AI more Humanlike would be awesome.

Are there plans to make the AI more intelligent / more humanlike?

Not-to-be-idiot level optimizations:
Not matching own special tiles, especially ones created just before.
Not casting sentry-sacrifice when this gives up the match.
Not casting a power which is already in effect (like Vision/Same density)
Using powers properly (Quicksilver Idle Hands = create a match)

Too smart AI = bad player experience type of optimizations:
Proper power casting orders, like Thoress blue->red, IW blue->green, Vision, etc
Using powers properly (GSBW/MnM purple)
Choosing the better powers.

Humans makes mistakes…
AI matchmaking in a more human manner:
can “properly” find possible match5s
can choose a better-color match3 than an off color match4
can miss a match5 or match4. (based on random and not on determinable tile-composition)

Aug 13, 2015

Perhaps it could be a toggle in the settings for better rewards, like more than 20 iso (gasp!). Hone your skills in the pve that you’re not grinding every node to 1 for the new 4* covers, then feel relief when you turn it off.

Prepare us for that day when you finally unveil the true 1v1 pvp where we can ante/wager iso, hp,or even extra covers.

Aug 13, 2015

I’m okay with a smarter AI, it actually makes sense.  Dmg, life, etc can all be tweaked to compensate.  What I did not like was to see TU’s have a lower drop rate.  Why do you hate C.Mags and Groot so much :(

Aug 13, 2015

Actually, the avoidance of obvious match 5s is a big big reason why players feel the game is cheating.  When a player sees the ai make an unnatural decision like avoiding an obvious easy great move, the natural conclusion is that the developers had to go out of their way to ensure the final ai design behaves like that.  Once the player locks in the assumption that the ai has that level of complication built into it, any other odd behaviors the ai is observed to perform is cast in that light as something that the devs invested a lot of complication in the ai to behave that way.  What other odd behaviors do players notice the ai doing?  Moves that cause multi-cascades and turns that feature many power activations in a row.  Obviously the devs put in a lot of work to make those happen, that’s unfair, that’s cheating!

Why are the devs declining to adapt the ai to trigger match 5s?  Because it’s a natural way for lowering the performance bar enough for casual, flawed players to enjoy games against an otherwise perfect ai.  But there’s an uncanny valley effect from this choice that’s affecting player psyches slowly and over the long term.  It can become a pretty brutal psychological effect.

There are a few approaches that might help with this situation:
- adapt the ai to consider match 5s with appropriate relative value (certainly opens another can of worms)
- add mechanisms to naturally break up multi-cascade moves or dampen their impacts
- add mechanisms to naturally break up multi-power turns

For example, to break up multi-cascades, MPQ could introduce a new reset special tile.  If it gets destroyed, the entire board is removed and replaced with a fresh board with no immediate matches.  Redesign a few characters to be able to generate this new special tile, and then the players can choose whether or not they value those abilities.

Similarly, to break up multi-power turns, MPQ could introduce a new powerlock special tile.  If an opponent activates a power while you have a powerlock tile on the board, one of your powerlock tiles is destroyed at random, and no further powers may be activated that turn.  If a few characters have powerlock-generating abilities, the players can decide their value.

As for allowing the ai to consider match 5s, well, that will reduce the uncanny valley effect, but make players suffer the full effect of their competitive disadvantage against perfect ai, which nobody wants.  Really you want a robust ai that plays much more noticeably like it’s taking human-style lines of casual play, like favoring building up for selected cool powers balanced with defending against opponent’s threats.  And occasionally makes flawed plays.  I’d love to dive into defining that behavior, but it’s too much work all at once.

But overall, things aren’t too bad with the ‘cheating’ ai if you can lower your seriousness when playing.  Keep it casual.

Aug 13, 2015

I don’t think the AI should be any smarter. The player wants to win more than he loses, naturally! Progressing through pvp events will become incredibly difficult if the winning percentage drops to - with smarter AI it could easily drop below 50%. One of the best things about MPQ is that you can roll the dice and challenge a stronger team and still come out on top because of the AI. Especially when you’re trying to push rank and you start seeing very strong teams.

Some characters will become much weaker if the AI improves as well. How useless would spidey be if they AI kept matching away his protect tiles? Or Cap if they take away his shield returns? How much stronger would some teams be if the AI properly prioritized abilities?

I feel like the game does a good job of rewarding you for playing and pushing rank. If you make the AI stronger that becomes more difficult. Additionally, you would get more points from defense (because your AI will win more often), which imo rewards passivity.

I would consider it for a special event, where you can tightly control the variables. Like if Ultron had smarter AI.

Aug 13, 2015

This sounds very cut-and-dried.  The code is not there, so the computer cannot play that way.

But despite this logic, it doesn’t feel right.  I know that the game plays mostly random.  It’s nice to know that they aren’t aiming for the match-5s, but only think they’re making a match-4, that they play for their own interests but can’t see when they’re sabotaging themselves, but there’s another element:

When you’re winning too easily in PVP, the computer turns on you like a peaceful monk, and suddenly, you’re facing the Grandmaster of the Shaolin.    Are we saying that it’s just statistically possible that uncharacteristic winning streaks tend to be stopped by uncharacteristic computer luck?  Is it confirmation bias to think otherwise?  I’m suspicious.  There has to be a hidden difficulty switch in there somewhere.

I know this:  early mook waves are way too easy to beat.  The colours are never so varied that I don’t get lots of the tiles I want.  And when you play with a team with a very limited colour palette, against an enemy with a similar palette, you often get way too much of the exact right colour.  And most matches against 2* Hawkeye place a match-5 on the initial board setup.  Same with Loki.  You’re almost always given a match-4 to trip on.    It could be confirmation bias again, but it could also be a very visible example that the computer controls these things.

Aug 13, 2015

“When you’re winning too easily in PVP, the computer turns on you like a peaceful monk, and suddenly, you’re facing the Grandmaster of the Shaolin.  Are we saying that it’s just statistically possible that uncharacteristic winning streaks tend to be stopped by uncharacteristic computer luck?”

I would say so. This happens to players too. Sometimes you will innocently match something, and it will result in a huge cascade. Its very similar to a slot machine. You’ll never hear anyone question when the slot machine pas out a big win.

Aug 13, 2015

Informative post!  Now I’d like to see one on how the AI chooses to use its abilities.

Aug 13, 2015

I’d love to challenge a more difficult ai, but the prize should match. I’m thinking a month long gauntlet style event that would lead us down a progressively more difficult path. I don’t think mixing smart ai with boosted levels would be well received. But the sythesis of teams should be explored. Characters like gsbw and quicksilver would suddenly be threats. I’d love to face a lvl 270 Thing Jean Grey and XF Deadpool challenge toward the end. And the reward should be a shot at 3 different colors of a newer 4 star. I’m game, just break it in gentle and make it worthwhile.

Aug 14, 2015

I echo what Kevin says in his comments. I would welcome the chance to choose to face more difficult opponents. Being able to pick easy fights and grind away some rewards quickly is a good and valid choice, but having a harder difficulty there when I want a challenge would be nice. A harder difficulty that offered better rewards of course! One ‘better reward’ might be that you always get one of the possible listed rewards rather than the 20 iso8. I’d face harder opponents to avoid that!

In addition having a harder baseline behavior available would allow you to weaken it in more interesting ways to lend personality to the opponent characters. Does Iron Man give more weight to red and yellow tiles because he’s vain and likes the color? Does Wolverine pick colors for his abilities rather than those for his team mates because he’s just not a team player? Being able to learn how particular characters play would add a lot of depth and satisfaction to the game.

And what’s to complain about as long is it’s an optional mode?

Aug 14, 2015

I really enjoyed this blog post; I’ve always wanted more insight into the inner-workings of this game. Write more, Justin!

The current dumb-AI serves its purpose quite well. Most people just want quick, easy games during their daily grind.

Still, I’d love to see the smart-AI get some use in the future. I can imagine playing against a seemingly standard Thanos enemy—then suddenly noticing all the smart shit he was doing. That would definitely bring a smile to my face. It would feel like a real boss fight.

Maybe add a single-node “Grandmaster Challenge” event featuring the smart-AI, then slap it next to Deadpool’s Daily Quest and rotate it once a week?

Aug 15, 2015

I would personally love the new AI algorithm. Too often I obliterate a much stronger enemy team only because they can’t play to their advantages. Changes to how AI uses hero abilities should be introduced as well. For example Human Torch will always try to create more Flame Jets instead of building up his green AP.

The level of opponents in PvE and PvP would have to be scalled down though

Aug 26, 2015

ROFLMAO this is the funnies lie I’ve ever seen. maybe D3go has gone rouge and wrote a totally different enemey AI, because that is not how they act on the mobile version of the game AT ALL.
First of all, if anything were truly random, I would get just as many cascades as the enemy team, this is simply not the case. Its a little fishy when a team containing a falcon gets 3 turns in a row with cascades that have MULTIPLE yellow matches in them. I’m not the only one either, my entire alliance has been complaining lately that the enemy is getting a lot more cascades and much longer cascades than expected.
I was playing the other day and had downed one enemy, and the rest of their team was luke cage (yellow, red, black) and hulk (green, red, black) and instead of taking the yellow or green match that was available, they went for the 3-tile purple one, the exact color I had just matched, since I needed it for doom’s power. it also happened to get rid of trap tiles that they should not have seen.
It’s also awfully convenient that when I played a team with hulk/patch for 2 full sets of turns in a row there were zero green tiles on the board. I think the devs are a little confused on what the definition of random is.

Aug 28, 2015

Oh, I forgot to mention the fact that the enemy will fire powers when they don’t have enough AP for it. For example, a recent match where 3* Iron man used his blue power WHICH COSTS 20 AP on the 3rd turn. the way the game played out it wasn’t even possible that he could have had enough AP to fire it. and that’s not the only example I can think of, but definitely the most extreme.

Aug 28, 2015

I very much want AI that fights more like the player that it represents in pvp. I never thought it was fair that I could lose points because the AI does not play as well as I do. I think a somewhat random system might be best though. Like the ai is capable of making L shaped matches after a random number of turns goes by and then can not again for a few more turns. I would also then want it to no longer be possible to take points from a shielded player if you started fighting them before they shielded as matches would take longer. Bringing the points up for a defensive win if the match takes longer than 5 minutes would also be good.

Sep 18, 2015

I like the idea of a smarter ai, I believe it would be necessary to keep players from boredom and/or looking elsewhere for a new challenge. However, as a majority of players are looking to win I believe the best way to do this would be to offer a ‘hard’ mode in which the losses would obviously come more frequently, yet intice them to try with a larger scaled payoff.

Nov 04, 2015

Local firms offer cheap alternative shelters that cost 25 percent
less than houses buijlt the traditional way. Glass Fiber Reinforced Concrete (GFRC) is used
mainly as architectural precast concrete. Many construction managers are
also given the duty of providing a budgfet for thhe construction project.

Dec 09, 2015

I would get just as many cascades as the enemy team, this is simply not the case. Its a little fishy when a team containing a falcon gets 3 turns in a row with cascades that have MULTIPLE yellow matches in them

Mar 26, 2016

You can also follow my homeschool-related boards for all subjects
and ages on Pinterest. West of Cabarete might be a known break , which
we will not name here. How about a phrase from a song that you’d
like to have as a notification.

Apr 05, 2016

good information. Thank you already share information on this one

Apr 10, 2017

Post a Comment