Hi,

I wanted a way to know which tiles are the best for a city to work in the long-term, so I threw together this proof-of-concept to see what was possible. The algorithm is fairly horrendous right now, so I wouldn't advise having more than about 8 tiles per city, or maybe running it overnight. It's written in Ruby, which I don't expect to be a popular language round here, but I like it, so that's what I used. I'd like to expand the number of things it takes into account, such as happiness or whipping. At the moment the tile values are just randomly generated - no desert or plains here, just a bunch of numbers.



TurnsToSimulate = 80

tiles = []
tiles << "plains,none,forest,none"
tiles << "grassland,none,none,rice"
tiles << "grassland,none,farm,rice"
tiles << "plains,none,none,none"

# [Food,Gold,Hammers]
Attributes = [
base = {
"none" => [0,0,0],
"plains" => [1,0,2],
"grassland" => [2,0,1],
"tundra" => [1,0,0],
"floodplains" => [3,0,0]
},

feature = {
"none" => [0,0,0],
"hills" => [0,0,1]
},

overlay = {
"none" => [0,0,0],
"forest" => [0,0,1],
"farm" => [lambda { |tile|
bonus = 1
case tile[4]
when "rice"
bonus = 2
end
bonus
},0,0]
},

special = {
"none" => [0,0,0],
"rice" => [1,0,0]
}
]

tiles.map! { |tile|
v = tile.split(',')
Attributes.inject([0,0,0]) { |total, type|
res = type[v.shift]
3.times { |t| total[t] += res[t].class == Proc ? res[t].call(tile.split(',')) : res[t] }
total
}
}

# Calc food required to achieve a pop size
def inc(size)
10 * 2 ** size - 20 # Or similar
end

# Given a total amount of food, calc current size
def currentSize(food)
s = 1
s += 1 while food > inc(s)
s
end

puts "Starting combinations #{Time.now}"

# Generate combinations
Combinations = (1..tiles.size).inject([[]]) { |acc, node| # Combinations (ints)
acc.inject([]) { |acc, injectedNodes| acc + [injectedNodes, injectedNodes + [node]] }
}.map { |c|
c.inject([0,2,1,2]) { |acc, node| # Combinations (tiles)
(0..2).inject([acc[0].succ]) { |i,n| i + [acc[n.succ] + tiles[node-1][n]] }
}
}.uniq.sort.inject([]) { |acc, node| # Tranches
acc + [acc.size <= node[0] ? [node] : acc.pop + [node]]
}.each { |set|
set.delete_if { |test| # Prune
set.inject(false) { |acc, comp|
acc or (!test.equal?(comp) and ((1..3).inject(true) { |i,n| test[n] <= comp[n] and i } and acc = true))
}
}
}

puts "Starting permutations #{Time.now}"

# Generate permutations
class Array
def permute(i = 0, *a)
return [a] if i == size
self[i].map { |x| permute(i+1, *(a + [x])) }.inject([]) { |m,x| m + x }
end
end
Permutations = Combinations.permute

# Container to store results
bestResult = []
5.times { |x| bestResult << ([0,0,0,0,0].dup << "Pop,Food,Gold,Hammers,Total".split(',')[x]) }

# Integrate across t
PermutationResults = Permutations.map { |p|
result = [1,0,0,0]
TurnsToSimulate.times { |t|
result = [currentSize(result[1])] + (1..3).to_a.inject([]) { |i,n|
i + [result[n] + p[result[0]][n]]
}
result[0] = tiles.size if result[0] > tiles.size # Cap size
}
result
}.inject(bestResult) { |acc, node|
node[4] = 0
(1..3).each { |x| node[4] += node[x] }
5.times{ |x| acc[x] = node + [acc[x][acc.size]] if node[x] > acc[x][x] }
acc
}

puts "Writing results"

# Write results to disk
File::open("output.txt", "w") { |file|
file << "# Combinations\n"
Combinations.each { |set|
set.each { |comb| file << " " << comb.join(" ") << "\n" }
file << "\n"
}

file << "# Permutations\n"
Permutations.each { |pset|
pset.each { |p| file << " " << p.join(" ") << "\n" }
file << "\n"
}

file << "# Results\n"
PermutationResults.each { |res| file << " " << res.join(" ") << "\n" }
}

puts "Finished #{Time.now}"

if I understand you code right (at least to a verry small extend) then you want to compare different starting scenarios in order to extrapolate the weightage of tile, so to find out which combination of tiles is the best one in long run...

this is an awesome idea. I am really impressed, your results will help to improve AI in another great way, they can be as and even more helpful as Blake's Algorithms.

But let me make some suggestion. In oder to get something out of this result we need an extensive weightage system. The AI has to be able to map out all available tiles at first with Blake's Algorithms which will provide a array of different starting locations and then with your algorithms in order to jugde the best starting points out of the given set.

The code isn't ideal for others to hack on, it's a bit functional and uses a few Ruby'isms. If I can't figure out a way to make the algorithm better, I'll probly just port it to C for a speed-up, and I'll write that version in a more 'normal' style.

At the moment the intention is for a completely stand-alone utility, so the user will actually write a short input file describing the available tiles. If someone wants to import it into the actual in-game AI, they should feel free to do so, but I won't be doing it myself - I don't need it personally and Python/integration work just isn't enough fun to fuel a weekend hack. If I'm lucky I'll get the chance to replace the randomness with an input file today. There is one way in which the output is useful immediately with no further work - gnuplot can create 2d or 3d graphs of the combinations, showing the trade-off between production, food and gold, banded by city size. I'll try to post one on Monday.

I imagine doing an analysis of an entire region would be at least an overnight task, but then again, Civ is a turn-based game ;) The only consolation is that throwing away completely unproductive tiles like desert makes a big difference.

if I understand you code right (at least to a verry small extend) then you want to compare different starting scenarios in order to extrapolate the weightage of tile, so to find out which combination of tiles is the best one in long run...

this is an awesome idea. I am really impressed, your results will help to improve AI in another great way, they can be as and even more helpful as Blake's Algorithms.

But let me make some suggestion. In oder to get something out of this result we need an extensive weightage system. The AI has to be able to map out all available tiles at first with Blake's Algorithms which will provide a array of different starting locations and then with your algorithms in order to jugde the best starting points out of the given set.

Here's an example of what the input file would look like.


plains,none,forest,none
grassland,hill,forest,deer


Edit: Removed redundant code

I put the two together, added a Total row to the outputs and cleaned a couple lines up. It's now possible to use 'real' tiles, although most of the data hasn't been entered.

Edit: Code moved to first post

I think the key to speeding it up is making use of the fact that any interesting combination for size n must be composed of one of the interesting combinations for size n-1 plus another tile. If I was clever I could figure out a way to order or cut down the list of potential additional tiles. Maybe only looking at all tiles in all combinations for n-1, that aren't already listed in this combination, would be a good start. If there are none, then start picking whatever is left. It's probably not that important anyway. Another way would be to rank the tiles from the beginning into bands of competitiveness, and only select from the next band when the current one is completely gone. It would be difficult because it would be a three-dimensional rating.

I also believe that integrating over time is possibly not the fastest method for using the results. If we start by again looking at size bands, it's possible to calculate the longest time any combination can possibly take to grow. From there, mixing combinations in a single turn may give better results, but again I don't have an efficient way in mind of how to do that.

Doing these things may ruin any chance of getting cottages working properly, tho. Maybe it would be possible to give an expected average, rather than an immediate value. First thing that comes to mind would be to take the sum of gold generated during the growth phases + the maxed gold/turn multiplied by the number of turns remaining in the game minus the growth length, and divide that by the turns, to give a kind of 'average return/turn for the rest of the game'.

Carry-over production from the previous size should probably just be ignored.

Edit: I'm still interested in doing this and am working on it when I get a chance (not very often unfortunately). Hopefully the algorithm I've started implementing below will be efficient enough to make this idea work. The code is a little more reader-friendly now.



# Useful extensions
class Object
def tap
yield self
self
end
end
class Array
def Array.identity(size)
Array.new(size) { |i| i }
end
# there is a problem with this function! duplicate values mean NONE get through! ONE must get through...!!!!!!!
def findInterestingTiles
reject { |test|
inject(false) { |acc, compare|
acc or (!test.eql?(compare) and Array.identity(3).inject(true) { |i,n|
TileValues[test][n] < TileValues[compare][n] and i
})
}
}
end
def totalise
inject([0,0,0]) { |total, tile|
3.times { |t| total[t] += TileValues[tile][t] }
total
}
end
def tiles_to_s
each { |tile| puts "\t#{tile} -> #{TileValues[tile].join(",")}" }
end
end

# Convert tiles to their numeric values
TileValues = Tiles.map { |tile|
v = tile.split(',')
Attributes.inject([0,0,0]) { |total, type|
res = type[v.shift]
3.times { |t| total[t] += res[t].class == Proc ? res[t].call(tile.split(',')) : res[t] }
total
}
}

result = Array.new(Tiles.size) { |i| i == 0 ? [[]] : [] }
used = []

(Tiles.size).times { |prevSize|
size = prevSize + 1
used.uniq!
possibilities = (Array.identity(Tiles.size-1) - used).findInterestingTiles + used
puts "#{size} => #{possibilities.size}"

# Try all combinations of previously selected sets and these tiles
result[prevSize].each { |previous|
possibilities.each { |possibleTile|
if (!previous.include? possibleTile)
result[size] << (previous + [possibleTile])
used << possibleTile
end
}

} # .delete_if not a good total....

# Calculate totals for each combination
totals = result[size].map { |set| set.totalise }
}