From b8a6afedb14a1d54d77df918dc1d5b53be11c44b Mon Sep 17 00:00:00 2001 From: joffrey-bion Date: Sat, 28 Nov 2020 00:21:43 +0100 Subject: Make all transactions available Sometimes the strategic move can be to spend more money on a different player, rather than less money on the wrong player. We need to make these strategic moves available through the UI. To make up for the explosion in combinations, we just have to get rid of the options that result in the same money for each neighbour. As long as we give the same amounts, we don't care whether it's for wood or clay. Related: https://github.com/joffrey-bion/seven-wonders/issues/50 --- .../org/luxons/sevenwonders/engine/cards/Cards.kt | 8 +- .../sevenwonders/engine/cards/Requirements.kt | 17 ++- .../engine/cards/RequirementsSatisfaction.kt | 27 +++-- .../engine/resources/BestPriceCalculator.kt | 128 ------------------- .../resources/TransactionOptionsCalculator.kt | 135 +++++++++++++++++++++ .../luxons/sevenwonders/engine/wonders/Wonder.kt | 5 +- 6 files changed, 163 insertions(+), 157 deletions(-) delete mode 100644 sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/BestPriceCalculator.kt create mode 100644 sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/TransactionOptionsCalculator.kt (limited to 'sw-engine/src/main/kotlin/org/luxons') diff --git a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Cards.kt b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Cards.kt index d5468283..b097734a 100644 --- a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Cards.kt +++ b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Cards.kt @@ -8,7 +8,7 @@ import org.luxons.sevenwonders.model.cards.CardPlayability import org.luxons.sevenwonders.model.cards.Color import org.luxons.sevenwonders.model.cards.PlayabilityLevel import org.luxons.sevenwonders.model.resources.ResourceTransactions -import org.luxons.sevenwonders.model.resources.noTransactions +import org.luxons.sevenwonders.model.resources.singleOptionNoTransactionNeeded internal data class Card( val name: String, @@ -55,7 +55,7 @@ private object Playability { isPlayable = true, isChainable = true, minPrice = 0, - cheapestTransactions = setOf(noTransactions()), + transactionOptions = singleOptionNoTransactionNeeded(), playabilityLevel = PlayabilityLevel.CHAINABLE, ) @@ -63,7 +63,7 @@ private object Playability { isPlayable = satisfaction.satisfied, isChainable = false, minPrice = satisfaction.minPrice, - cheapestTransactions = satisfaction.cheapestTransactions, + transactionOptions = satisfaction.transactionOptions, playabilityLevel = satisfaction.level, ) @@ -71,7 +71,7 @@ private object Playability { isPlayable = true, isChainable = false, minPrice = 0, - cheapestTransactions = setOf(noTransactions()), + transactionOptions = singleOptionNoTransactionNeeded(), playabilityLevel = PlayabilityLevel.SPECIAL_FREE, ) } diff --git a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Requirements.kt b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Requirements.kt index 945f4463..b78a5057 100644 --- a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Requirements.kt +++ b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/Requirements.kt @@ -2,12 +2,9 @@ package org.luxons.sevenwonders.engine.cards import org.luxons.sevenwonders.engine.Player import org.luxons.sevenwonders.engine.boards.Board -import org.luxons.sevenwonders.engine.resources.Resources -import org.luxons.sevenwonders.engine.resources.asResources -import org.luxons.sevenwonders.engine.resources.bestSolution -import org.luxons.sevenwonders.engine.resources.emptyResources -import org.luxons.sevenwonders.engine.resources.execute +import org.luxons.sevenwonders.engine.resources.* import org.luxons.sevenwonders.model.resources.ResourceTransactions +import org.luxons.sevenwonders.model.resources.bestPrice data class Requirements internal constructor( val gold: Int = 0, @@ -37,15 +34,15 @@ data class Requirements internal constructor( } private fun satisfactionWithPotentialHelp(player: Player): RequirementsSatisfaction { - val (minPriceForResources, possibleTransactions) = bestSolution(resources, player) - val minPrice = minPriceForResources + gold - if (possibleTransactions.isEmpty()) { + val options = transactionOptions(resources, player) + val minPrice = options.bestPrice + gold + if (options.isEmpty()) { return RequirementsSatisfaction.unavailableResources() } if (player.board.gold < minPrice) { - return RequirementsSatisfaction.missingGoldForResources(minPrice, possibleTransactions) + return RequirementsSatisfaction.missingGoldForResources(minPrice, options) } - return RequirementsSatisfaction.metWithHelp(minPrice, possibleTransactions) + return RequirementsSatisfaction.metWithHelp(minPrice, options) } /** diff --git a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/RequirementsSatisfaction.kt b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/RequirementsSatisfaction.kt index f9566981..55ec1edb 100644 --- a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/RequirementsSatisfaction.kt +++ b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/cards/RequirementsSatisfaction.kt @@ -1,39 +1,40 @@ package org.luxons.sevenwonders.engine.cards import org.luxons.sevenwonders.model.cards.PlayabilityLevel -import org.luxons.sevenwonders.model.resources.PricedResourceTransactions -import org.luxons.sevenwonders.model.resources.noTransactions +import org.luxons.sevenwonders.model.resources.ResourceTransactionOptions +import org.luxons.sevenwonders.model.resources.noTransactionOptions +import org.luxons.sevenwonders.model.resources.singleOptionNoTransactionNeeded internal data class RequirementsSatisfaction( val satisfied: Boolean, val level: PlayabilityLevel, val minPrice: Int, - val cheapestTransactions: Set, + val transactionOptions: ResourceTransactionOptions, ) { companion object { internal fun noRequirements() = - RequirementsSatisfaction(true, PlayabilityLevel.NO_REQUIREMENTS, 0, setOf(noTransactions())) + RequirementsSatisfaction(true, PlayabilityLevel.NO_REQUIREMENTS, 0, singleOptionNoTransactionNeeded()) internal fun enoughResources() = - RequirementsSatisfaction(true, PlayabilityLevel.ENOUGH_RESOURCES, 0, setOf(noTransactions())) + RequirementsSatisfaction(true, PlayabilityLevel.ENOUGH_RESOURCES, 0, singleOptionNoTransactionNeeded()) internal fun enoughGold(minPrice: Int) = - RequirementsSatisfaction(true, PlayabilityLevel.ENOUGH_GOLD, minPrice, setOf(noTransactions())) + RequirementsSatisfaction(true, PlayabilityLevel.ENOUGH_GOLD, minPrice, singleOptionNoTransactionNeeded()) internal fun enoughResourcesAndGold(minPrice: Int) = - RequirementsSatisfaction(true, PlayabilityLevel.ENOUGH_GOLD_AND_RES, minPrice, setOf(noTransactions())) + RequirementsSatisfaction(true, PlayabilityLevel.ENOUGH_GOLD_AND_RES, minPrice, singleOptionNoTransactionNeeded()) - internal fun metWithHelp(minPrice: Int, cheapestTransactions: Set) = - RequirementsSatisfaction(true, PlayabilityLevel.REQUIRES_HELP, minPrice, cheapestTransactions) + internal fun metWithHelp(minPrice: Int, transactionOptions: ResourceTransactionOptions) = + RequirementsSatisfaction(true, PlayabilityLevel.REQUIRES_HELP, minPrice, transactionOptions) internal fun missingRequiredGold(minPrice: Int) = - RequirementsSatisfaction(false, PlayabilityLevel.MISSING_REQUIRED_GOLD, minPrice, emptySet()) + RequirementsSatisfaction(false, PlayabilityLevel.MISSING_REQUIRED_GOLD, minPrice, noTransactionOptions()) - internal fun missingGoldForResources(minPrice: Int, cheapestTransactions: Set) = - RequirementsSatisfaction(false, PlayabilityLevel.MISSING_GOLD_FOR_RES, minPrice, cheapestTransactions) + internal fun missingGoldForResources(minPrice: Int, transactionOptions: ResourceTransactionOptions) = + RequirementsSatisfaction(false, PlayabilityLevel.MISSING_GOLD_FOR_RES, minPrice, transactionOptions) internal fun unavailableResources() = - RequirementsSatisfaction(false, PlayabilityLevel.UNAVAILABLE_RESOURCES, Int.MAX_VALUE, emptySet()) + RequirementsSatisfaction(false, PlayabilityLevel.UNAVAILABLE_RESOURCES, Int.MAX_VALUE, noTransactionOptions()) } } diff --git a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/BestPriceCalculator.kt b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/BestPriceCalculator.kt deleted file mode 100644 index 967bee2c..00000000 --- a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/BestPriceCalculator.kt +++ /dev/null @@ -1,128 +0,0 @@ -package org.luxons.sevenwonders.engine.resources - -import org.luxons.sevenwonders.engine.Player -import org.luxons.sevenwonders.model.resources.PricedResourceTransactions -import org.luxons.sevenwonders.model.resources.Provider -import org.luxons.sevenwonders.model.resources.ResourceType -import java.util.* - -internal fun bestSolution(resources: Resources, player: Player): TransactionPlan = - BestPriceCalculator(resources, player).computeBestSolution() - -data class TransactionPlan(val price: Int, val possibleTransactions: Set) - -private class ResourcePool( - val provider: Provider?, - private val rules: TradingRules, - choices: List>, -) { - val choices: List> = choices.map { it.toMutableSet() } - - fun getCost(type: ResourceType): Int = if (provider == null) 0 else rules.getCost(type, provider) -} - -private class BestPriceCalculator(resourcesToPay: Resources, player: Player) { - - private val pools: List - private val resourcesLeftToPay: MutableResources - private val boughtResources: MutableMap = EnumMap(Provider::class.java) - private val pricePaid: MutableMap = EnumMap(Provider::class.java) - private var totalPricePaid: Int = 0 - - private var bestSolutions: MutableSet = mutableSetOf() - private var bestPrice: Int = Integer.MAX_VALUE - - init { - val board = player.board - this.resourcesLeftToPay = resourcesToPay.minus(board.production.getFixedResources()).toMutableResources() - this.pools = createResourcePools(player) - } - - private fun createResourcePools(player: Player): List { - // we only take alternative resources here, because fixed resources were already removed for optimization - val ownBoardChoices = player.board.production.getAlternativeResources() - val ownPool = ResourcePool(null, player.board.tradingRules, ownBoardChoices) - val providerPools = Provider.values().map { it.toResourcePoolFor(player) } - - return providerPools + ownPool - } - - private fun Provider.toResourcePoolFor(player: Player): ResourcePool { - val providerBoard = player.getBoard(boardPosition) - val choices = providerBoard.publicProduction.asChoices() - return ResourcePool(this, player.board.tradingRules, choices) - } - - fun computeBestSolution(): TransactionPlan { - computePossibilities() - return TransactionPlan(bestPrice, bestSolutions) - } - - private fun computePossibilities() { - if (resourcesLeftToPay.isEmpty()) { - updateBestSolutionIfNeeded() - return - } - for (type in ResourceType.values()) { - if (resourcesLeftToPay[type] > 0) { - for (pool in pools) { - if (pool.provider == null) { - computeSelfPossibilities(type, pool) - } else { - computeNeighbourPossibilities(pool, type, pool.provider) - } - } - } - } - } - - private fun computeSelfPossibilities(type: ResourceType, pool: ResourcePool) { - resourcesLeftToPay.remove(type, 1) - computePossibilitiesWhenUsing(type, pool) - resourcesLeftToPay.add(type, 1) - } - - private fun computeNeighbourPossibilities(pool: ResourcePool, type: ResourceType, provider: Provider) { - val cost = pool.getCost(type) - resourcesLeftToPay.remove(type, 1) - buyOne(provider, type, cost) - computePossibilitiesWhenUsing(type, pool) - unbuyOne(provider, type, cost) - resourcesLeftToPay.add(type, 1) - } - - fun buyOne(provider: Provider, type: ResourceType, cost: Int) { - boughtResources.getOrPut(provider) { MutableResources() }.add(type, 1) - pricePaid.merge(provider, cost) { old, new -> old + new } - totalPricePaid += cost - } - - fun unbuyOne(provider: Provider, type: ResourceType, cost: Int) { - totalPricePaid -= cost - pricePaid.merge(provider, -cost) { old, new -> old + new } - boughtResources[provider]!!.remove(type, 1) - } - - private fun computePossibilitiesWhenUsing(type: ResourceType, pool: ResourcePool) { - for (choice in pool.choices) { - if (choice.contains(type)) { - val temp = EnumSet.copyOf(choice) - choice.clear() - computePossibilities() - choice.addAll(temp) - } - } - } - - private fun updateBestSolutionIfNeeded() { - if (totalPricePaid > bestPrice) return - - if (totalPricePaid < bestPrice) { - bestPrice = totalPricePaid - bestSolutions.clear() - } - // avoid mutating the resources from the transactions - val transactionSet = boughtResources.mapValues { (_, res) -> res.copy() }.toTransactions(pricePaid) - bestSolutions.add(transactionSet) - } -} diff --git a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/TransactionOptionsCalculator.kt b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/TransactionOptionsCalculator.kt new file mode 100644 index 00000000..fbbcaa6e --- /dev/null +++ b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/resources/TransactionOptionsCalculator.kt @@ -0,0 +1,135 @@ +package org.luxons.sevenwonders.engine.resources + +import org.luxons.sevenwonders.engine.Player +import org.luxons.sevenwonders.model.resources.* +import java.util.* + +internal fun transactionOptions(resources: Resources, player: Player): ResourceTransactionOptions = + TransactionOptionsCalculator(resources, player).computeOptions() + +private class ResourcePool( + val provider: Provider?, + private val rules: TradingRules, + choices: List>, +) { + val choices: List> = choices.map { it.toMutableSet() } + + fun getCost(type: ResourceType): Int = if (provider == null) 0 else rules.getCost(type, provider) +} + +private class TransactionOptionsCalculator(resourcesToPay: Resources, player: Player) { + + private val pools: List + private val resourcesLeftToPay: MutableResources + private val boughtResources: MutableMap = EnumMap(Provider::class.java) + private val pricePaidPerProvider: MutableMap = EnumMap(Provider::class.java) + + private var optionsSoFar: MutableSet = mutableSetOf() + + init { + val board = player.board + this.resourcesLeftToPay = resourcesToPay.minus(board.production.getFixedResources()).toMutableResources() + this.pools = createResourcePools(player) + } + + private fun createResourcePools(player: Player): List { + // we only take alternative resources here, because fixed resources were already removed for optimization + val ownBoardChoices = player.board.production.getAlternativeResources() + val ownPool = ResourcePool(null, player.board.tradingRules, ownBoardChoices) + val providerPools = Provider.values().map { it.toResourcePoolFor(player) } + + return providerPools + ownPool + } + + private fun Provider.toResourcePoolFor(player: Player): ResourcePool { + val providerBoard = player.getBoard(boardPosition) + val choices = providerBoard.publicProduction.asChoices() + return ResourcePool(this, player.board.tradingRules, choices) + } + + fun computeOptions(): ResourceTransactionOptions { + computePossibilities() + return optionsSoFar.distinctBy { it.costByProvider }.sortedBy { it.totalPrice } + } + + private val PricedResourceTransactions.costByProvider: Map + get() = associate { it.provider to it.totalPrice } + + private fun computePossibilities() { + if (resourcesLeftToPay.isEmpty()) { + addCurrentOption() + return + } + for (type in ResourceType.values()) { + if (resourcesLeftToPay[type] > 0) { + for (pool in pools) { + if (pool.provider == null) { + computeSelfPossibilities(type, pool) + } else { + computeNeighbourPossibilities(pool, type, pool.provider) + } + } + } + } + } + + private fun computeSelfPossibilities(type: ResourceType, pool: ResourcePool) { + resourcesLeftToPay.remove(type, 1) + computePossibilitiesWhenUsing(type, pool) + resourcesLeftToPay.add(type, 1) + } + + private fun computeNeighbourPossibilities(pool: ResourcePool, type: ResourceType, provider: Provider) { + val cost = pool.getCost(type) + resourcesLeftToPay.remove(type, 1) + buyOne(provider, type, cost) + computePossibilitiesWhenUsing(type, pool) + unbuyOne(provider, type, cost) + resourcesLeftToPay.add(type, 1) + } + + fun buyOne(provider: Provider, type: ResourceType, cost: Int) { + boughtResources.getOrPut(provider) { MutableResources() }.add(type, 1) + pricePaidPerProvider.merge(provider, cost) { old, new -> old + new } + } + + fun unbuyOne(provider: Provider, type: ResourceType, cost: Int) { + pricePaidPerProvider.merge(provider, -cost) { old, new -> old + new } + boughtResources[provider]!!.remove(type, 1) + } + + private fun computePossibilitiesWhenUsing(type: ResourceType, pool: ResourcePool) { + for (choice in pool.choices) { + if (choice.contains(type)) { + val temp = EnumSet.copyOf(choice) + choice.clear() + computePossibilities() + choice.addAll(temp) + } + } + } + + private fun addCurrentOption() { + if (optionsSoFar.any { it < pricePaidPerProvider }) { + return + } + // avoid mutating the resources from the transactions + val transactionsOption = boughtResources.mapValues { (_, res) -> res.copy() }.toTransactions(pricePaidPerProvider) + optionsSoFar.add(transactionsOption) + optionsSoFar.removeIf { it > pricePaidPerProvider } + } + + private operator fun PricedResourceTransactions.compareTo(prices: Map): Int = when { + left == prices.left -> right.compareTo(prices.right) + right == prices.right -> left.compareTo(prices.left) + else -> 0 + } + + private val Map.left: Int get() = this[Provider.LEFT_PLAYER] ?: 0 + private val Map.right: Int get() = this[Provider.RIGHT_PLAYER] ?: 0 + + private val PricedResourceTransactions.left: Int + get() = firstOrNull { it.provider == Provider.LEFT_PLAYER }?.totalPrice ?: 0 + private val PricedResourceTransactions.right: Int + get() = firstOrNull { it.provider == Provider.RIGHT_PLAYER }?.totalPrice ?: 0 +} diff --git a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/wonders/Wonder.kt b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/wonders/Wonder.kt index 4a99b9e9..03ed2f8f 100644 --- a/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/wonders/Wonder.kt +++ b/sw-engine/src/main/kotlin/org/luxons/sevenwonders/engine/wonders/Wonder.kt @@ -7,6 +7,7 @@ import org.luxons.sevenwonders.model.cards.CardBack import org.luxons.sevenwonders.model.cards.PlayabilityLevel import org.luxons.sevenwonders.model.resources.ResourceTransactions import org.luxons.sevenwonders.model.resources.ResourceType +import org.luxons.sevenwonders.model.resources.noTransactionOptions import org.luxons.sevenwonders.model.wonders.WonderBuildability internal class Wonder( @@ -53,14 +54,14 @@ private object Buildability { fun wonderFullyBuilt() = WonderBuildability( isBuildable = false, minPrice = Int.MAX_VALUE, - cheapestTransactions = emptySet(), + transactionsOptions = noTransactionOptions(), playabilityLevel = PlayabilityLevel.WONDER_FULLY_BUILT, ) fun requirementDependent(satisfaction: RequirementsSatisfaction) = WonderBuildability( isBuildable = satisfaction.satisfied, minPrice = satisfaction.minPrice, - cheapestTransactions = satisfaction.cheapestTransactions, + transactionsOptions = satisfaction.transactionOptions, playabilityLevel = satisfaction.level, ) } -- cgit