Tribalwars units algoritme

[TheBlasphemer]

Ik heb een applicatie geschreven waarin ik de units die beschikbaar zijn in het spel tribalwars (tribalwars.nl) in een lijst heb, en waar ik dan simpele queries op kan uitvoeren.
Elke unit heeft 4 kosten, en 4 baten:
Kosten: Hout, Leem, Ijzer en Villagers
Baten: Aanval, Verdediging, Cavalerie-verdediging, en Boogschutter verdediging.
Er zijn 12 verschillende units in het spel

Simpele queries als "Meeste aanval per villager" kan ik al uitvoeren, maar ik wil eigenlijk nog flinke stap ingewikkelder:
Ik heb een aantal grondstoffen (kosten), en ik wil zo hoog mogelijke baten, waarbij ik zelf kan aangeven welke baten ik belangrijker vindt dan anderen (bijv. geen aanval, 3 verdediging, 3 cavalerie-verdediging, 2 boogschutter-verdediging), en ik wil weten welke units ik het beste kan bouwen.

Ik heb al geprobeerd om alle mogelijkheden recursief door te lopen, maar dit is simpelweg te veel. Als je meer dan 20 units kan bouwen, zijn er al 20*19*18*...*2 mogelijkheden
Verder heb ik geprobeerd om een evolutionair algoritme te implementeren, maar hier komen zelden echt optimale waarden uit
Ik heb het idee dat het wat weg heeft van linear programmeren, maar ik heb moeite om te bedenken hoe dit dan precies moet...

Heeft iemand enig idee hoe ik dit probleem het beste kan oplossen?

[ Voor 5% gewijzigd door TheBlasphemer op 22-10-2007 00:30 ]

[Sjaaky]

Je kunt dit probleem als linear probleem formuleren.

u1 = unit1
u2 = unit2
u3 = unit3
u4 = unit4

Stel vergelijkingen op:
Je hebt 8 hout en 4 leem.
Om unit 1 te bouwen heb je 3 hout en en 2 leem nodig
unit2 is 1 hout en 0 leem
unit3 is 2 hout en 1 leem

3.u1 + 1.u2 + 2.u3 <= 8 (eenheden hout, constanten zijn bouwkosten hout per unit)
2.u1 + 0.u2 + 1.u3 <= 4 (eenheden leem)
zo ook voor ijzer en villagers

Waardering van units:
De waardering per unit reken je al van te voren uit tot 1 getal. Als unit1 2 aanval, 1 verdediging oplevert en jij aanval met 1 waardeert en verdediging met 3, dan heeft unit1 waarde 2x1 + 3x1 = 5.
Als je de waardering unit1 = 5, unit2 = 1 en unit3 = 3 hebt, dan moet je de volgende functie maximaliseren: Z = 5.u1 + 1.u2 + 3.u3.

Dit kun je met simplex oplossen. Probleem daarmee is dat je dan geen integer oplossing hebt. Hoe je dat doet weet iemand anders vast wel.

[ Voor 187% gewijzigd door Sjaaky op 22-10-2007 22:15 ]

[BestTested!]

Sjaaky schreef op maandag 22 oktober 2007 @ 20:27:
uitleg linear programming....

Dit kun je met simplex oplossen. Probleem daarmee is dat je dan geen integer oplossing hebt. Hoe je dat doet weet iemand anders vast wel.

Inderdaad. Door een zogenaamde relaxation van het oorspronkelijke linear programming probleem. Het is iets te lang geleden om het nu zo uit mijn hoofd hier neer te zetten, maar de termen waar je op moet googlen zijn: interger linear programming relaxation

Voor meer informatie kan je kijken of je dit boek kan lenen/kopen: Chvatal: Linear Programming

[joepP]

Ik stel voor dat je het eens met de solver van Excel probeert, dit soort kleine probleempjes zijn daarmee uitstekend op te lossen. Sim-pel