Programming Contest

[PhilD]

Originally posted by Saber Cherry:

Problem: Determine the best path for a mage to search friendly provinces. Yes, this is harder than it sounds to make optimal. But it is not very difficult to make a working solution, even though the description below may seem difficult.

What, exactly, do you want us to solve? What should be the output?

I mean, there are a lot of things one can optimize for. Number of searched provinces within X turns? Number of likely sites within X turns? First turn where one searches a province?

[Saber Cherry]

The best path would be the one that wasted fewest gems. There would be 2 ways to determine the best solution.

1) The easy way. Scatter sites around, and determine how many gems were wasted before all provinces were searched. The person whose algorithm finds the most sites the quickest would win, even if it takes him the same amount of time to search all the sites as a worse solution. This would be done for several different site-scatterings, and the sites would be scattered according to terrain probability modifiers. Even if it was done many times, luck would still be a factor.

2) The better way. Sum the wasted probability-time... in other words, if you don't search a Plains province for 5 turns, you get penalized 50%*5. There are no real "sites", per se. For example, if there were 3 provinces, a Swamp (30%), a Forest(80%), and a Mountain(100%), where the numbers indicate their site frequency relative to mountains, and you started in the swamp...

Your output could be (substituting terrains for province numbers)

start swamp
search
move mountain
search
move forest
search
end

...which scores like this:
(30*0)+(100*2)+(80*4)=520

or:

start swamp
move mountain
search
move forest
search
move swamp
search
end

...which scores like this:
(30*5)+(100*1)+(80*3)=490

How does the scoring work? It is (swamp magic site richness)*(turns before searching the swamp)+(mountain magic site richness)*(turns before searching the mountain)+(forest magic site richness)*(turns before searching the forest), with the minimum number best.

In this case, since forests and mountains are richer in terms of magic sites, it is actually BETTER to move instead of searching first! You want to minimize the lost probability-time.

The other factors are search status and already-found sites, which affect probability. For simplicity, we'll assume that there are only level 0-3 sites, equally distributed by level and path, so that there are as many level-3 Unholy sites as level-0 Earth sites. Which is not true, but it makes things a lot easier.

I'll wait on the more complicated probabilities until I get more comments, but generally, if a province has already been searched, or already has some magic sites, the probability of finding new sites is reduced. Obviously, a province that has 4 sites, or that has been searched to level-3 (in Dominions, level-4) in all paths, cannot yield any more sites.

[ March 01, 2004, 07:18: Message edited by: Saber Cherry ]

[Norfleet]

I have a far more interesting, and far more immediately useful in-game, problem:

The challenge is simple: Be the first to fix Utgard Jotun in 2.08 without breaking anything else!

[Saber Cherry]

Originally posted by Norfleet:
The challenge is simple: Be the first to fix Utgard Jotun in 2.08 without breaking anything else!

It's easy to fix... trivial... but it can only fix new games, not current games. And you have to declare, "I'm playing Utgard" before the game even starts, since themes cannot be modded yet.

[Arryn]

Originally posted by Saber Cherry:

quote:

---

Originally posted by Norfleet:
The challenge is simple: Be the first to fix Utgard Jotun in 2.08 without breaking anything else!

It's easy to fix... trivial...

---

The fixes I have seen do not fix the entire theme, only the Seithkona. There's more wrong with it than that.

[Saber Cherry]

You just have to clear the nation, and then do #addunit and #addleader for each unit and leader, and specify the correct magic site. As far as I know...

[Norfleet]

Originally posted by Saber Cherry:
You just have to clear the nation, and then do #addunit and #addleader for each unit and leader, and specify the correct magic site. As far as I know...

Ah, but you see, it's not quite that simple: A simple mod doesn't have the capability to modify themes: A .MAP would have to be applied for every map that somebody wants to play Utgard around. None of these are obviously total solutions. That's why it's a contest! Somebody may actually have to hex the things in! Now *THIS* is a contest!