Determine optimal strategy, taking into account chain buying about cookiemonster HOT 15 CLOSED

The idea is that Cookie Monster should calculate what the optimal strategy is in every situation.
For example, whenever you are on 98 of a building and are able to get the "own 100 achievement" it might be more efficient to buy building 99 and then 100, than buying the current best PP building.
However, I believe this is fairly difficult to implement without calculating every possible buy-strategy at every pass of the loop.

Has anybody got any good ideas on how to implement this?

from cookiemonster.

Would a way to begin tackling this be to create an index of achievements and what buildings they are related to: For example we could say that buying a bank might earn one of the "# of banks" achievements, but would never earn one of the "# of prisms" achievements.

from cookiemonster.

And maybe giving the user visualization into the optimization process is one of the most important parts - let's say it would take a year to compute every possible permutation to a depth of 20 actions. Maybe it only takes 5 seconds to determine what the next 2 optimal actions are.

Proposal:
Add a new menu similar to Stats and Options. When open it's a blank canvas with a progress bar (showing calculation on the next best action chain) and strings of proposed action chains
As optimal paths are found add a row of buttons that show what is to be purchased in what order with helpful tooltips/summary description. For example at the very beginning of the game after you buy your first cursor maybe it shows a cursor button followed by a few more cursor buttons and then a grandma button because the best course of action (assuming no manual clicking is to buy a few cursors in a row and then save up to buy a grandma.

As the algoritm realizes that 2 cursors in a row is a good idea it shows 2 cursor buttons. Once it decides a third cursor would be good it will add a third button.

Cookie monster is giving the user options to act on now while it continues to figure out longer and longer-term strategies.

from cookiemonster.

@TakGalaman's first comment: We already have this data, both from the vanilla game and from some of the things we do with CookieMonster. This would therefore not be the issue.

@TakGalaman's second comment: This would be wonderful but is akin to writing a whole new mod. The biggest problem will still be what algorithm should be used to calculate this "ideal path". (See some of the discussions in some of the mentioned issues)
Thus, the first step in implementing this would be to find a better algorithm to calculate PP or another metric of "optimality".

from cookiemonster.

You could sort the list of missing achievements by price, with a tooltip that shows what buildings/things need to be done to get the achievement.

This could be shown only to players who opt to show "Missing Upgrades".

Then you could:

• Show this list on the main page, in the store & allow people to click the achievement to buy all the buildings required for that achievement.
• This could be a new section in the store, or the tiles could be inserted into the "Upgrades" section. This would allow you to apply the PP sorting strategy to show the player the best move.
• Probably better to add a new section so you don't confuse people who click "buy all upgrades"
• Change "Missing Upgrades" from on/off to "show none, 10, 50, 200, all" or something like that?
• Separate list for achievements that are earnt vs bought?

from cookiemonster.

Oh oops, the "Missing Upgrades" CM feature does not have anything to do with missing achievements.

Missing achievements would have to be a whole new function.

This feature should almost certainly use filtered list of purchasable achievements. Either hardcoded or cached on initialisation? How often does Orteil add new achievements?

The display should almost certainly be limited to the next 10 or 20 cheapest achievements otherwise it would cause a lot of lag. Also spoilers.

from cookiemonster.

Game.Objects such as Cursor, Farm, etc. have an array "tieredAchievs" which list their achievements.

This could be used to decide what to show. Perhaps iterate over Game.Objects, filter for "locked".

Then only show the next tiered achievement for each Game Object. A new store section labeled "Purchasable Achievements" would be best for this.

I'm not sure how to easily show the "Total buildings and upgrades" achievements such as Builder or Mathematician. Perhaps a hardcoded list.

from cookiemonster.

You could sort the list of missing achievements by price, with a tooltip that shows what buildings/things need to be done to get the achievement.

This should be easily doable and is indeed something I was thinking of. We have this data already. Instead of caching PP for buildings on 1, 10 and 100 intervals we could then cache on 1, 10, 100 and next tiered achievement - current amount. This should be implementable.
The problem is though if this will then create the most optimal strategy. I think it will because I don't think there are any instance where it is better to go for the 'tiered achievement after the next tiered achievement' (so the second in line), but I am note sure. It would be nice if we could find a way that we are sure that Cookie Monster is always correct.

Missing achievements would have to be a whole new function.

Somebody had started on this but has not finished it yet. Perhaps this will be added in the future. I do know that he ran into some problems with the way Orteil currently loads the achievements and how to inject missing achievement into that.

Game.Objects such as Cursor, Farm, etc. have an array "tieredAchievs" which list their achievements.

This could be used to decide what to show. Perhaps iterate over Game.Objects, filter for "locked".

Then only show the next tiered achievement for each Game Object. A new store section labeled "Purchasable Achievements" would be best for this.

I'm not sure how to easily show the "Total buildings and upgrades" achievements such as Builder or Mathematician. Perhaps a hardcoded list.

These are all things we already cache and have as data so this shouldn't be a limiting factor in doing this.

from cookiemonster.

I can get surprisingly far without using CM at all actually. This is what I have so far.

This code loads most of the building achievements as purchasable upgrades.

Note:

• Cursor achievements are hardcoded and not tiered the same as others.
• It doesn't play nice with CM right out of the box.
• These fake upgrades appear in the stats page after being bought (until the game is refreshed). Probably need to declare a specific upgrade.pool on them.
• "Total buildings and upgrades" still needs to be done separately

var purchasableAchievements = []
Object.keys(Game.Objects).forEach(key => {
  var building = Game.Objects[key]
  building.tieredAchievs.forEach(achiev => {
    if (achiev.won) return

    var tier = Game.Tiers[achiev.tier]
    var amountToBuy = tier.achievUnlock - building.amount
    var price = building.getSumPrice(amountToBuy)

    var upgrade = new Game.Upgrade(
      `Buy "${achiev.name}"`,
      `Buy ${amountToBuy} ${building.plural} to get the achievement "${achiev.name}"`,
      price,
      achiev.icon,
      function () {
        var tier = Game.Tiers[achiev.tier]
        var amountToBuy = tier.achievUnlock - building.amount

        building.buy(amountToBuy)
      }
    );

    upgrade.price = price

    upgrade.priceFunc = function () {
      var amountToBuy = tier.achievUnlock - building.amount
      return building.getSumPrice(amountToBuy)
    }

    if (Game.cookiesEarned > price / 20) {
      upgrade.unlocked = 1;
    } else {
      var toPush = { cookies: price / 20, name: `Buy "${achiev.name}"` };
      if (!upgrade.locked) Game.UnlockAt.push(toPush);
    }

    purchasableAchievements.push(upgrade)
  })
})
Game.RebuildUpgrades()

from cookiemonster.

This code adds the cursor achievements, but highlights the problem that if you buy the buildings normally (or leapfrog over an purchasable achievement button), the now redundant "purchasable achievement upgrade" isn't removed.

E.g. Using "Buy Double-click" to purchase 2 cursors doesn't remove "Buy Click" which wants to buy 1 cursor.

var purchasableAchievements = []
var cursorAchievements = {
  'Click': 1,
  'Double-click': 2,
  'Mouse wheel': 50,
  'Of Mice and Men': 100,
  'The Digital': 200,
  'Extreme polydactyly': 300,
  'Dr. T': 400,
  'Thumbs, phalanges, metacarpals': 500,
  'With her finger and her thumb': 600,
  'Gotta hand it to you': 700,
  'The devil\'s workshop': 800
}

Object.keys(cursorAchievements).forEach(name => {
  var achiev = Game.Achievements[name];
  if (achiev.won) return
  var building = Game.Objects["Cursor"];

  var amountToBuy = cursorAchievements[name] - building.amount
  var price = building.getSumPrice(amountToBuy)

  var upgrade = new Game.Upgrade(
    `Buy "${achiev.name}"`,
    `Buy ${amountToBuy} ${building.plural} to get the achievement "${achiev.name}"`,
    price,
    achiev.icon,
    function () {
      var amountToBuy = cursorAchievements[name] - building.amount

      building.buy(amountToBuy)
    }
  );
  upgrade.price = price

  upgrade.priceFunc = function () {
    var amountToBuy = cursorAchievements[name] - building.amount
    return building.getSumPrice(amountToBuy)
  }

  if (Game.cookiesEarned > price / 20) {
    upgrade.unlocked = 1;
  } else {
    var toPush = { cookies: price / 20, name: `Buy "${achiev.name}"` };
    if (!upgrade.locked) Game.UnlockAt.push(toPush);
  }

  purchasableAchievements.push(upgrade)
})

Object.keys(Game.Objects).forEach(key => {
  var building = Game.Objects[key]
  building.tieredAchievs.forEach(achiev => {
    if (achiev.won) return

    var tier = Game.Tiers[achiev.tier]
    var amountToBuy = tier.achievUnlock - building.amount
    var price = building.getSumPrice(amountToBuy)

    var upgrade = new Game.Upgrade(
      `Buy "${achiev.name}"`,
      `Buy ${amountToBuy} ${building.plural} to get the achievement "${achiev.name}"`,
      price,
      achiev.icon,
      function () {
        var tier = Game.Tiers[achiev.tier]
        var amountToBuy = tier.achievUnlock - building.amount

        building.buy(amountToBuy)
      }
    );

    upgrade.price = price

    upgrade.priceFunc = function () {
      var amountToBuy = tier.achievUnlock - building.amount
      return building.getSumPrice(amountToBuy)
    }

    if (Game.cookiesEarned > price / 20) {
      upgrade.unlocked = 1;
    } else {
      var toPush = { cookies: price / 20, name: `Buy "${achiev.name}"` };
      if (!upgrade.locked) Game.UnlockAt.push(toPush);
    }

    purchasableAchievements.push(upgrade)
  })
})
Game.RebuildUpgrades()

from cookiemonster.

You could do up a list of known buy strategies and game states that the mod should look out for in order to account for them, for instance only calculate the building upgrades and achievements when you're within 10 of getting it, or something like that. It's a little arbitrary, but it would work. Another possibility would be to have complex buy strategies have their own shared time within the loop, so that if it needs to calculate many at once it doesn't slow down the game, instead it just takes longer to calculate the more complex strategies.

from cookiemonster.

I think there are only 4 options that could be optimal: "buy 1, "buy 10", "buy 100" or "buy till new achievement". There has been some discussion previously about situations where it is better to buy Building C > Building A > Building B instead of Building A > Building B > Building C (if A had a lower pp than B and C was higher than B). However, I don't think this situation ever occurs in the game.
I believe there is only one situation where not buying a single building has a lower PP: when you can buy something that gives an achievement. Therefore, accounting for the four options I mentioned I think we can determine the most optimal strategy in all cases.
However, I would be glad if somebody provided counter evidence with situations in which either of these 4 situations is not most optimal!

from cookiemonster.

My way works! But unfortunately doubling the number of upgrades in to the "Game.UnlockAt" array causes noticeable lag on older computers.

I think CookieMonster would need to keep track of upcoming unlockable upgrades in it's own, more efficient loop, then add the items to "Game.UnlockAt" when they're almost ready to be unlocked.

(Also CookieMonster should track and remove upgrades if they're reached without clicking the button)

Sorry I disappeared, real work got busy.

from cookiemonster.

Hmm, I think there is an approach that would be me resource-efficient.
If we store the next achievement level as a property of CacheObjects1 we can check how much it would take to reach the next achievement. Then on every loop over CachePP we could check if that amount is > 0. If not, check if there is a higher achievement and otherwise just stop considering the 4th option. If there is an amount we just need to do the CachePP loop one more time which should not be that bad. Please tell if I need to explain myself better.

from cookiemonster.

Still have not found an efficient way to do this.

Basically the issue is as follows: how can we determine the number of buildings needed to unlock the next achievement?
This should consider both "x of building", "x total buildings" and "x amount of cps" achievements and should not loop over "buy 1", "buy 2", "buy 3" to see if the number of achievements changes. Instead we want to come up with a solution that finds the correct number fairly efficiently.

I have hidden most of the old discussions as they were no longer relevant for the problem.

from cookiemonster.