Brute Force AI

[smalltalk]

bike:

again, I do agree to you. Here are some numbers:

-------------------------------------------------
Possible moves in chess:

1st turn
8 pawn * 8
2 knight * 2
=
20 moves

Mid game
(for example 1852 anderssen/dufresne) 15 th turn
62 moves

--------------------------------------------------
Possible moves in Civ III

1st turn
1 worker * 10
1 settler * 10
5 science goal
10 tax + lux ratings
=
35 moves

Mid game
(a very, very crude guess)
20 cities * 10 build options = 200
120 units * 3 tiles * 2 actions = 720
10 tax + lux ratings
a thousand diplomacy options
= 1930 moves

Late game (railroads !)
20 cities * 10 build options = 200
120 units * 20 citiey * 21 tiles * 2 actions = 100800
10 tax + lux ratings
a thousand diplomacy options
=
102010 moves

Then, we have to account that not only 1 unit may move, like in chess, but
maybe 120 units in different order, so we should have for late game
something like

102010 * 102009 * 102008 * ... * 101891 * 101890

if my math is right, roughly 100000 E 120 = 1 E 124
meaning a number with 124 digits
which is a really -big- number,
beyond anyones understanding
- certainly beyond any xoxxing computer storage and speed
and I didn't even account for EIGHT civs and at least 20 turns look ahead.
--------------------------------------------------

So there truly will be no CIV brute force AI.

I stand in awe before the human brain.
How did I ever win a game ?
I stand in awe of CIV III AI.
How could I ever loose out to it ?



park ranger:

Right - I forgot about recent develpement. These techniques are summarized under Artifical Live AL and include genetic algorithms (the one you describe), cellular automatons, flock behaviour and the like.

:: and tagging evolution as a brute force method is really an insight !


Still I doubt, computers could incorporate their findings into their own programming code.
That is, nowadays.


stormbind, sumthinelse:

guess, you both promote the same view: libraries of positions = classes of positions
It is about understanding the library.
(Picture of a monkey trying to decipher Encyclopedia Britannica)

 

[Bismarck]

You are assuming that Civ proceeds by brute force minimax search, akin to what chess engines do. I doubt that very much. Chess and Civ are fundamentally different games. Chess is a perfect information game (as someone else here has said), and hence it is possible to compute long move-countermove sequences. Civ is a highly stochastic game, where it is better to proceed on *heuristics*, i.e. general situational guidelines.

The only time when Civ will calculate move-countermove sequences is when they are extremely short -- two-ply sequences to be exact. So, if it can immediately capture a few of your workers, it will do so. Any sequence longer than two "plies" cannot be computed.

For longer-term decisions, Civ probably relies on heuristics such as the following (just a schematic example):

// production decisions for each city
if(at_war){
..if(wonder_available && no_city_producing_it && city_shields > N)
....produce wonder
..else if(rand < 0.75){ // produce a military unit
....if rand < 0.5
......produce offensive unit
....else if rand < 0.85
......produce defensive unit
....else
......produce bombardment unit
..}
..else
..// etc.
}

Still not trivial to code, but not impossible either. A lot of experimentation will be required to find good values.

EDIT: darnit, indentation won't show properly. Periods substituted for spaces.