Programming Contest

[Saber Cherry]

I'm thinking of having some sort of programming contest... but I'm not really sure what to do. So, a poll is in order!

[Saber Cherry]

If many people are interested, and the contest is Dominions II related, it would be neat if the devs could step in with a real problem, the solution of which is useful to the game...

Like, for example, a module that best determines AI troop choice, or something along those lines.

[Endoperez]

I WOULD like to be of help here, but my skills are very low... Java I can write won't do you any good, yet. I'm still studying, though, so I might be able to help later.

[Saber Cherry]

Hmmm...

That's a bigger response than I anticipated, though the gap between "wanting to do" and "doing" is always substantial.

So - are there any suggestions? Some examples:

A system of assuring leader names are not duplicated until all names are used?

A small algorithm that quantifies the power of a single unit? (In other words, it uses the unit's stats, and deterministically generates a number that represents the "threat rating" of the unit. My combat sim is slow and nondeterministic, as it uses pseudorandom simulation. Such a function would be crucial in AI prioritizing and targetting.)

A search-path module that produces an optimal site-finding path for a mage in friendly territory, accounting for movement speed, search status, provincial site richness (e.g., mountain vs farmland) in different terrain types?

A scripting language for the Dominions II strategic AI? If the devs could somehow enable AI modding, a competition for the best strat AI for a given nation would be awesome=) The quantification would be in running multiple all-AI games and counting wins.

Ideally, a winner would have to be correct (or else, the most correct, for hard problems), and some sort of quantification would be needed to select the best of the correct solutions. For example, runtime and code size can be useful. Thus, a problem whose solution's quality can be quantified is always good.

-Cherry

[Pocus]

you restrict the contest to C, C++ and Java ???

[PhilD]

Originally posted by Saber Cherry:

A scripting language for the Dominions II strategic AI? If the devs could somehow enable AI modding, a competition for the best strat AI for a given nation would be awesome=) The quantification would be in running multiple all-AI games and counting wins.

-Cherry <font size="2" face="sans-serif, arial, verdana">Can you make pure-AI games now? I admit I never even tried... (since you cannot even look at an AI's screen, it's not that useful, but...)

[Saber Cherry]

Originally posted by Pocus:
you restrict the contest to C, C++ and Java ??? <font size="2" face="sans-serif, arial, verdana">No! There was an option 4, "Other: Explain." And there's also the possibility of scripting in a non-language, in which case, scripting commands and an interpreter would be needed. Some possible problems could have an answer in the form of an equation or non-specific algorithm, though in order to be scored, raw algorithms would need to be implimented.

I don't want to list every language known... if you have another preference, speak up! =)

[Saber Cherry]

Originally posted by PhilD:
Can you make pure-AI games now? I admit I never even tried... (since you cannot even look at an AI's screen, it's not that useful, but...) <font size="2" face="sans-serif, arial, verdana">You can make a map with 16 AIs and script a human onto a disconnected island with 150 province defense... then run to completion.

[Saber Cherry]

This is just a preliminary idea. Please post any criticism or suggestions! If you don't understand, ask; I promise it's not very confusing or difficult, once you grasp the concept. So, also, please don't be overwhelmed!

OTOH, if you think it's so complex that you won't participate, but you WOULD participate if it was simpler, please say so! You can PM me if you want=)

OK, well, so far nobody has suggested a problem, so I'll propose one. To make it language-independant, all I/O will be handled with text files.

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.

Input:

1) a .txt file that is a simplified map file. The format will be something like this:

#provinces 3

#terrain 0 3 1
#searched 0 1 1 0 0 1 4 0 0 0 0
#found 0 1
#friendly 0

#terrain 1 1 2
#friendly 1

#terrain 2 0
#friendly 2

#neighbor 0 1
#neighbor 1 2

It's identical to a map file, except you ignore every command except #terrain and #neighbor. Also, 4 new commands are added, #searched, #found, and #friendly, and #provinces.

The syntax:

#terrain x a1 a2 a3...
means "Province X has terrain type a1, a2, and a3". Terrain types are listed later.
#found x y
means y sites have already been found in province x
#searched x fire air earth water astral death nature blood holy unholy
means the province was already searched in those paths to the specified level. If a province was already searched in any path, all 10 paths will be specified (so there are always 11 numbers after #searched)
#friendly x
means province x is friendly (your mage can only go to friendly provinces)
#provinces x
is always the first line and tells you how many provinces there are in the map.
#neighbor is just like in a .map file; it means those provinces are connected, both ways.

2) a .txt file that holds a mage. It will be something like,
#name Bobby
#magic 0 1 0 0 1 0 3 0 0 0
#moves 3
#forest
#mountain
#swamp
#start 0

This means that a mage named Bobby, with 1 Air, 1 Astral, and 3 Nature, starts in province 0. He has 3 map movement, and forest/mountain/swamp survival (meaning none of those impede his movement).

Things to consider:

To make the problem more simple, you can ignore #forest, #mountain, #swamp, #searched, and #found, and the site probability based on terrain. You will still get a correct answer that is just not ideal.

On the other hand, to make the problem more challenging, you can consider that each province has a maximum of 4 magic sites, and support the commands #aquatic, #flying, #stealthy (move through enemy provinces, if it is faster), and #amphibious.

Suggestion: Keep it simple first, and ignore all the commands except #provinces, #neighbor, and #moves, and #start. Those are the only commands you need to process to make a working program (though it will not give correct answers). Then gradually add the capability to process additional data.

Important Data:
Unless Illwinter states otherwise, terrain types will be considered like this:

0: Water, 60% richness, costs 3 strat move
1: Plains, 50% richness
2: Farmland, 40% richness
3: Forest, 80% richness, costs 3 strat move unless #forest skill
4: Waste, 70% richness, costs 3 strat move
5: Swamp, 30% richness, costs 3 strat move unless #swamp skill
6: Mountain, 100% richness, costs 3 strat move unless #mountain skill

Meaning it is more valuable to search mountains first and swamps Last. These numbers are not the same as the map file numbers, but those are too confusing.

Input Command: The program must have a command line that accepts 2 filenames, and spits out a new file. The input command is:
(your executable name) mapfile.txt magefile.txt

For example,

java Solve aran.txt joe_the_druid.txt

Output:

Output will be a text file that looks like this:

start 0
search
move 1
search
move 2
move 4
search
done

Each command other than "start 0", which indicates your start province, is the equivalent of a turn. This start province must be the same as specified in the mage file. "Move 1" means move to province 1. If you move to a non-adjacent province that is in range, only give 1 move command. All move commands must be to a province in range.

The output file should be named (mapname)_(magename)_output.txt.

For example,
run.exe aran.txt joe_the_druid.txt

should produce an output file,

aran_joe_the_druid_output.txt

-Cherry

[ February 29, 2004, 23:02: Message edited by: Saber Cherry ]

[Pocus]

I develop in Delphi. If dominions would allow us to encode our own 2h (for an AI), then it would be neat. Alas, it would poses the problem of reveling how they protect the turn file.

[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.

<font size="2" face="sans-serif, arial, verdana">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! <font size="2" face="sans-serif, arial, verdana">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:
</font><blockquote><font size="1" face="sans-serif, arial, verdana">quote:</font><hr /><font size="2" face="sans-serif, arial, verdana">Originally posted by Norfleet:
The challenge is simple: Be the first to fix Utgard Jotun in 2.08 without breaking anything else! <font size="2" face="sans-serif, arial, verdana">It's easy to fix... trivial... </font><hr /></blockquote><font size="2" face="sans-serif, arial, verdana">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... <font size="2" face="sans-serif, arial, verdana">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!