Programming Contest

[Saber Cherry]

Originally posted by Pocus:
you restrict the contest to C, C++ and Java ???

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

You can make a map with 16 AIs and script a human onto a disconnected island with 150 province defense... then run to completion.

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

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

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