Balancing the prices of UQM's ships
Based on Shiver's forthcoming PvP guide, I think we could mathematically calculate new and perfectly balanced values for UQM's ships (using the data about how well each ship fares against each other ship).
I have uploaded a C++ version here, but it makes an ugly oversimplification and it's not exactly mathematically proven. The probability of each outcome of each match-up should be taken into account, I guess.
-With hope that you can sort things out, Valaggar 17:33, 15 January 2008 (CET)
Yes, I had this in mind as an application of the idea I put on that page, I guess the only thing at the moment is that my real life has been quite busy in recent times, resubmitting our paper (it's morning where I live and I only just saw this before heading out to face a busy day). I was actually thinking of running the simulations in matlab too, but we can do it every which way :)
There are all kinds of issues to consider here, but I may have some time coming up. I've been watching Shiver's guide with keen interest.
There are also other things we can look at with the approach I suggested. For example, I saw the talk in the dreadnought=banana boat thread on UQMF and actually I think one of the main reasons for the weakness of the dreadnought is that the limited number of directions is a disadvantage for any ship with long range weapons which do not track the enemy. This effect we could test by seeing what happens when we add more directions. There are many other interesting speculations like this too.
For instance, it was also mentioned that the dreadnought was not designed for retreat, it is for frontal assault. Now, I think that because one is never really concerned with holding a position in melee, ships against which this would be difficult are disadvantaged. Like the dreadnought, which is no banana boat, at least as I argue here, because melee doesn't do it justice.
I also think the dreadnought is better in numbers, and that there are some ships which would be terrible in numbers like the eluder.
All kinds of things we could test. But a lot of work. Anyway, thanks Val --Zeracles 21:46, 15 January 2008 (CET)
My apologies, for I was in a great hurry yesterday - I didn't have time to look at your program and misunderstood what you had in mind, Val. I see now that it's mainly an algorithm which deduces values assuming quantities which summarise the match-ups, and what those quantities are is a different but related question. I don't know when I'll have time, but this is really excellent, I will look more closely ASAP.
Oh and it was also mentioned in the dreadnought=banana boat thread that the marauder was better - just as an aside, I suspect this could change completely with numbers. Both of the marauder's weapons are more likely to cause friendly damage than the dreadnought's. --Zeracles 19:22, 16 January 2008 (CET)
- Thank you very much, Zeracles. But what do you mean with the Marauder causing friendly damage? The Marauder doesn't collide with its own shurikens or F.R.I.E.D. jets. Valaggar 19:36, 16 January 2008 (CET)
- If your algorithm is what I suspect it is (and if it isn't, this is because I don't know any of C's variants), I think it's clever. You'll correct me if I'm wrong, but here is what I understand it to be:
- The outlook for each match-up is summarised with a number between 0 and 1. It would seem natural to me to have this as probability of victory.
- The sum of these for each ship gives one a first guess at how effective it is, its x-value.
- The cleverness of the algorithm comes in here - a ship is not necessarily very useful if it is only really good against weak ships (which opponents may never choose). So, we reward it for being good against other ships which are strong, i.e., ships which have high x-values. This is achieved by weighting the sum of match-up values with the opposing ship's x-values.
- These weighted sums give us a new x-value for each ship, a ``second guess".
- These new x-values are used to again make weighted sums of the original match-up values for a third guess at the x-values.
- We continue iterating until these x-values converge.
- If this is right, it sounds good to me. Well done! A possible worry is whether we can guarantee convergence (and related to this could be how you normalise the values between iterations, which I'm not clear on), but seeing as how it seems to work now, we can probably already be almost certain that this is sound.
- If you go with interpreting the input as probabilities, then even if Shiver's values are not very precise for individual match-ups, I think this should work well when all of them are thrown together. It would be interesting to see what you get if you put the match-up values in assuming computer vs computer - I suspect this will deliver ship prices closer to the default ones than that guy's mod (I'd put a link but again I'm just posting quickly before another busy day!). Also, if we ever do get to doing melee simulations, the probabilities we get out of that would be refinement of Shiver's values.
- You speak of an ugly oversimplification . . . you put the problem very well, so I'll just quote you :)
- Also note that I used the rather gross oversimplification that ships merely have a certain chance of winning, not taking into account how damaged the victor's ship comes out of the combat (it's not necessarily directly proportional to the chance of winning, as, for instance: the Scout barely has a chance of winning, yet it still can deal considerable damage; the Drone barely has a chance of winning, yet it doesn't deal much damage generally; etc.). This is something that really needs improvement (and professional help ;)).
- Maybe we'll think about that if I haven't embarrassed myself and completely missed the point of your algorithm. It may then be that probabilities as input are not the way to go. Then again, for the precision required to pin down how much damage ships will do, on average, it seems to me that simulations would be most valuable. But we can always guess and see what happens. Great work! I stand ready (well, apart from my real life interfering) to assist in any way I can. This could be worthy of a page - I think in the main body of pages, but a user page at least.
- About the marauder, I was just assuming that while an individual marauder can't hurt itself, it would still be able to hurt its friends. I suppose because if melee was to be extended to third person, it would be natural to be consistent and allow friendly fire for all the ships (but obviously kzer-za fighters will have enough sense not to attack friends). Still, it could be argued that it would be equally consistent to retain all the settings of the first person melee, then again we know it wasn't designed with third person in mind.
- Well, how's this for a tactic dreadnoughts could employ in numbers (which marauders couldn't!) - the fighters don't necessarily return to the ship from which they came. They return some friendly ship which is low on crew, to make it last a bit longer (or even be sent out only for the purpose of jumping into a friendly ship rather than attacking the enemy - with enough support, the front line dreadnoughts could be virtually indestructible!). These are the sorts of interesting tactics not reproduced in third person games I have seen. But then again the only third person games I've played are Dune II and StarCraft (terminators are the zealots of Star Control, are they not?). --Zeracles 19:53, 17 January 2008 (CET)
- You've got it completely right. That's my algorithm summarized.
- Regarding the converging and normalizing of values: At the very least, empiric testing shows they converge (unless one ship has 1 against each other ship, in which case the limit of the uber ship's price is infinity, and the limit of all other prices is zero. Which reflects the idealized reality represented by the algorithm pretty well, as a ship that always defeats every other ship renders those other ships useless). By "converge" I mean that the proportions between them stabilize (as, without normalizing, the variables themselves will quickly overflow, even as doubles; were overflowing not a problem, the proportions between them would still be conserved by normalizing... I think. I'll look into it tomorrow).
- To normalize, I first search the initial array of match-up values for the cell with the highest number (if there are multiple such cells, the first of them gets chosen). Its x coordinate is assigned to the variable maxx, its y coordinate is assigned to the variable maxy. In every iteration, I divide match-up value and each x-value by (curmax / 100), where curmax is the cell with the x coordinate maxx and the y coordinate maxy in the current iteration.
- And "that guy" with the balance mod is Elvish Pillager, the world champion at Super Melee, so show some respect. ;) Actually, he provided the inspiration for Point 3 in your bulleted list. We dueled once (many months ago) on #uqm-arena, and he won, and I blamed my defeat on the imbalance of UQM's ships. He said that the ships are only slightly imbalanced. I replied that my algorithm shows they are badly imba. (yes I still remember that dialog!) He said that my values are off, and said that a ship good against a single good ship is worth more than a ship good against multiple weak ships. I had to concede on that point. He suggested an inaccurate approach, though (calculating the "first guess" x-value by adding 1 for each ship that the current ship has a probability higher than 50% of defeating; and the x-value stopped at this "first guess"). But still, the credit for the idea goes to him, just as the credit for the idea of *colours* being related to perception goes to you, although it was me who integrated it into my theory and refined it. Rant over. Valaggar 21:36, 17 January 2008 (CET)
- I'm starting to think that the input should be how much damage gets done as a proportion of the opposing ship's max crew. This introduces some complications, though. Like with the podship and penetrator, negative values come into it. And it's more difficult. But of course, we can try everything. Under this, whether one can get negative values in those cases depends on what the opposing ship's crew was at the beginning. But the probable outcome of a fight depends on the respective crews too. What this starts to question is the assumption of both ships initiating with a clean slate (though this isn't clear in Shiver's thinking, I think this is mostly assumed in the outlooks). Related is the question of how to handle the intruder's ability to warp close to the enemy.
- Possibly the only solution is to hit the problem with full melee simulation. So, we have virtual players show up for a nuke BBQ and choose their ships based on some initial ship prices. As the melee progresses they make choices based on experience of previous outcomes regarding crew levels and such. Er, which assumes this is part of informing the tactics of these virtual players. Anyway, after some fighting, see how useful the ships were and update values.
- Um, forget my stupid idea (although it probably just seems more work than it is because this would be a simulation, you wouldn't have to sit there watching and turning the handle). This is far far away and we should probably just go with probability/damage fraction as input for your algorithm.
- I haven't really thought the normalisation through but is there a reason why you divide by (curmax/100) and not simply curmax?
- About credit for ideas . . . hmm. --Zeracles 20:41, 18 January 2008 (CET)
- Regarding normalizing: Yes, it does indeed preserve proportions. If mtch[x][y][n] stands for y's match-up value against x as of iteration n (x and y range from 0 to 24, n is greater than 0), and curmax[i] stands for the curmax as of iteration i, then:
- mtch[x][y][n] = ((mtch[x][y]/curmax) * ((a[x][n-1]/curmax[n-1]) + (a[x][n-1]/curmax[n-1]) + ... + (a[x][n-1]/curmax[n-1]))) / curmax[n]
- mtch[x][y][n] = (mtch[x][y] * (mtch[x][n-1] + mtch[x][n-1] + ... + mtch[x][n-1])) / (curmax * curmax[n-1] * curmax[n])
- Without normalizing, mtch[x][y][n] would be equal to only the numerator of that last fraction. Since all members of the array (as of iteration n) are divided by the same denominator, the proportions between the members of the array are indeed preserved.
- Regarding dividing by curmax/100 instead of curmax: It was a matter of personal preference, I preferred having values between 0 and 100 rather than between 0 and 1. Nevertheless, I've changed the algorithm so that curmax = mtch[maxx][maxy][cur] / 100 and division is by curmax, not curmax / 100. And the final X values are now normalized too, to be more fit for using in-game (no need for a 20000pts maximum fleet). 
- I'll ramble on about your idea of using damage/max_crew instead of chance_of_victory tomorrow, it's past midnight right now. :) Valaggar 23:41, 18 January 2008 (CET)