It's 2005, why does the AI still need to cheat?

[Godzilla]

The way that I would see that:

I have 2 warriors, I can send him 9 different ways (including not at all), then depending on what move I make with that warrior, I have 9 possibilities per option.

"Strateegery" to quote an imbecile.

[theNiceOne]

Originally posted by -Ab-
* -Ab- climbs into flame proof suit!
ok if you got 2 warriors and the first one has 9 choices,why then does the second multiply it by 9?
why is it not 9 choices and then 9 more choices?

Because there are 81 different combined positions for the two warriors after the turn. (There are actually far more, because this assumes that the warriors can do nothing but stay or move to an adjacent hex).

I'm really surprised that you act as if you know anything about programming AI, but then fail to understand even the most basic examples.

If you were right, then the movement of the second warrior is completely unrelated to the movement of the first. It would be a horrible AI that didn't consider the possible movement of other units when deciding the movement of one.

The decision of attacking an enemy unit is highly dependant on other friendly units that can back up the attack, etc.

[Maidel]

Originally posted by Gaal Dornik
Imagine you have 1 simple warrior. Each warrior can move to 8+1 fields. For the AI to see whats going on next turn there are 9 possible positions to calculate. No probs. Now lets take 2 warriors 9*9=81. With 3 warriors thats 9*9*9=729 possibilities.

Now lets take a normal map, 7 nations, warrior+settler. A settler is faster, allowing him to go to 25 fields. makes it (9*25)^7=29'192'926'025'390'625= 29 Peta-possibilities. Todays PCs can do like 3gHz( 0,000003petahetz) And that excluding everything else(like graphics, music..)

Making todays PCs twice as fast, like 6gHz will not even scratch the above number.

Well, that was for one turn at the beginning, imagine late game with 100+units, railroads, and deep 10 turns AI strategic. Thats a number highly unimaginable.

While I totally aggree with the concept in this thread (that the AI is as good as it can be) I am afraid to say that you are working out the maths wrong here.

The warriors moves are independant of each other and therefore there are only 9+9 (18) possiblities, not 81 and with 3 warriors it is 27 not 729.

[Gaal Dornik]

-Ab-
3 warriors have 729 possibilities? give an example of that
yeah like Godzilla said. Thats similar to our decimal system. with 3 spaces and 10 possible numbers from 0 to 9, one can get 10*10*10=1000 different numbers. (000 - 999) For example 444, where all three warriors are going left.

9+9 is 18 out of possible 81,( like 99 in decimal system) which means only 2 branches were calculated. For situations, where one of the warriors passed the turn.

"Peta" is a way for lazy ppl to say a number has fifteen zeroes attached

[Gaal Dornik]

Originally posted by Maidel

I am afraid to say that you are working out the maths wrong here. The warriors moves are independant of each other and therefore there are only 9+9 (18) possiblities, not 81

What do you mean exactly. If i understand correctly what the AI is doing is building a decision tree, which it will then run down and choose the best way to go. If there is something independent, it means that there are two or more trees and each of them neglect other units. I dont understand. Plz elaborate.

The trick is to cut its branches with smart algorithms, and this is where open source would help(or not), in my opinion.

[GodSpawn]

Maidel, you're wrong. As far as the AI goes, you'd have to consider all the possible moves - and the number of permutations goes up exponentially, as others have already pointed out.

This is well-known in the realm of game theory (and AI/heuristics programming), and is commonly referred to as a "combinational explosion".

There are many ways to attempt to deal with this, for example alpha-beta pruning and minimaxing. What you can never do is enumerate all possible game states. (There's plenty on the net about this, for example: http://www.insight.demon.co.uk/Compu...am/formcmp.htm)

Chess is a much easier game to consider when appreciating the difficulties of programming an AI to play a game. And when you try to write code to play it (I've tried myself, years ago) you soon realise how tricky it is to make the code work quickly enough.

Well, you can take that level of coding difficulty and increase it many times for a game like Civilization!

[Maidel]

I am not sure that I am wrong.

IT depends on how it is looked at. From a purely mathematical perspective (using the laws of probability which are very similar in this situation) the way that one warrior moves does NOT affect the way the other warrior moves (directly)

Therefore the probabilies/possibilties add. So working in a linear fashion the AI moves one unit in any one of 9 ways, then moves the next unit in any one of 9 ways. meaning a that the numbers add.

the only way it could mulitply is if the AI takes ALL the possible moves into consideration at the same time and then works out how to move all the units together. Which as the guy showed was impossible for it to do as it would go FAR above the processing power of a typical PC.

I am not necessarily saying that I am correct, I know very little about computer programming, but I do know quite a bit about mathematics. And looking at the two systems that have been shown its been proved that one is impossible

Now lets take a normal map, 7 nations, warrior+settler. A settler is faster, allowing him to go to 25 fields. makes it (9*25)^7=29'192'926'025'390'625= 29 Peta-possibilities. Todays PCs can do like 3gHz( 0,000003petahetz) And that excluding everything else(like graphics, music..)

and mine is not. However if I am missing something please correct me.

[-Ab-]

hmmm ok i understand why its a high number now
i had to get a bit of paper and write it down and it made my brain hurt

im not sure if 81 is the actual number but yeah the possible number of moves is high if every time the 2nd warrior moves you include the ones it could have took but didnt

"Peta" is a way for lazy ppl to say a number has fifteen zeroes attached

hehe

[vulture]

Originally posted by Maidel


While I totally aggree with the concept in this thread (that the AI is as good as it can be) I am afraid to say that you are working out the maths wrong here.

The warriors moves are independant of each other and therefore there are only 9+9 (18) possiblities, not 81 and with 3 warriors it is 27 not 729.

Wrong. Very, very wrong. This is something very basic to probability theory, or anything like this kind of programming.

Consider a warrior and an archer on the same square at the start of the turn. Both can move 1 space. Each has a choice of 9 spaces to move in to (including the square they are in). Try and count the number of possible final combinations of positions of the two units - is it 18 or 81?

Using the standard numeric keypad designations for movement, we can put the warrior's final position in the first column, and the archer's final position in the second column. Our options are:

11
12
13
14
15
16
17
18
19
21
22
23
24
25
26
27
28
29
31
32
33
34
35
36
37
38
39
41
42
43
44
45
46
47
48
49
51
52
53
54
55
56
57
58
59
61
62
63
64
65
66
67
68
69
71
72
73
74
75
76
77
78
79
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99

Which is 81 possibilities. If you think any of those are duplicates of each other, please feel free to point them out.

The number of possibilities to consider for even a single turn late in the game is simply staggering. There is asbolutely no way you can do some kind of exhaustive look-ahead to determine the best course of action. And even if you could, how much would it really help? Long term planning is based a greta many terms ahead, and would still be vastly beyond the capability of a 10-ply lookahead AI algorithm (which itself would require vastly more computing power than is currently available in the world).

[padillah]

The basic problem this raises is this: we do not need a single AI. We need 9, one for each difficulty so as to not have to hamper or reward to present a different level of difficulty.

So, now you are creating 9 different AI's rather than just one. But, that means all the computer opponents will think the exact same way so we really need one AI for each trait paring: or 18 types of AI for each of the 9 difficulty levels.

So, to make a CIV game without "cheating" or presenting rewards in any way inconsistent with the rules, you would need to create 162 seperate and distinct AI's.

So, start coding.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Oh, and for those of you wondering, the math would be 2 (choices) times 9 (moves for coice one) times 9 (moves for chioce two) or 162 branches with two warriors. The AI needs to determine which warrior it will move first, then it can decide which move to make. Then it decides which move to make for the other warrior.

That's (3 * 9) * (2 * 9) * 9 = 4374 branches for three warriors. Again, the decision of which of three warriors to move then which of the last two warriors to move, then which move for the last warrior.

It increases exponentially, not linearly. (edit: got that wrong a second ago)

Tom P.

[alva]

Then let's perform an expert. Can you beat the AI on 'Noble' (the level closest to no AI-cheats)? If so, do you ever lose? If not, do you cheat in any fashion (reloading, etc)?

You make some good points.

The only way - IMHO - to judge an AI, is to judge your first game against it.
Read the manual, learn the rules and then have a game on standard difficulty.
How many here got their bééhind handed back to them in their first game on noble, there's plenty that I know of.
To me, that says that the AI definatilly is doing more than ok. You can't expect it to keep beating you as you start to learn more, especially with the weath of info that is avallaible on forums like this one.

The AI (programmer) is not just playing you but he's playing against hundreds of people, many who are quite brilliant themselves.

[Maidel]

You see this is the problem when people just dont read my posts...

the way the numbers combine depend on whether you feel that one warriors movement is intrinsically dependant on the other.

I realise that this form of probability maths is not directly applicable to computer programming (something which I have admitted I have no concept of)


IF the warriors movement is NOT directly linked then their movement is 9 options PER warrior. Therefore they have 9 opitions each and the numbers add.

IF the warriors movement is directly linked then you are correct and the probabilites multiply.

I do realise that the system is obviously NOT one or the other, but every time the AI moves a group of warriors it is NOT choosing between 9^x moves where x is the number of warriors.

[vulture]

Originally posted by padillah


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Oh, and for those of you wondering, the math would be 2 (choices) times 9 (moves for coice one) times 9 (moves for chioce two) or 162 branches with two warriors. The AI needs to determine which warrior it will move first, then it can decide which move to make. Then it decides which move to make for the other warrior.

That's (3 * 9) * (2 * 9) * 9 = 4374 branches for three warriors. Again, the decision of which of three warriors to move then which of the last two warriors to move, then which move for the last warrior.

It increases logrithmically, not exponentially.

Tom P.

Fair point, since we are not dealing with a perfect information game: if the units are non-unique, the order of which moves when makes a difference - particularly with combat, but also in response to information gathered about the position of enemy units by the movement of the first unit.

Are you sure you mean logarithmically? Or are you just using the word differently? Looking n moves ahead means testing roughly X^n possibilities- that's an exponential increase in my book. A logarithmic incrase would be very, very easy to deal with computationally - looking 10 turns ahead might cost time T more than looking 1 turn ahead, but looking 100 turns ahead only costs an extra time T. Deep lookaheads would be trivial in that scenario.

[vulture]

Originally posted by Maidel
IF the warriors movement is NOT directly linked then their movement is 9 options PER warrior.

See, you're doing well up to this point...

Therefore they have 9 opitions each and the numbers add.

... and then it all goes down hill. Why do they add? When in combinatorial problems do these things ever add? Can you give an example of the set of 18 possible outcomes that cover all eventualities of moving these 2 warriors?

IF the warriors movement is directly linked then you are correct and the probabilites multiply.

If they are independent they multiply. If they are linked, it depends on how they are linked.

If the warriors are identical, there are still 45 discrete outcomes after moving them both from the same starting position. If they are seperated from each other, there are the full 81 outcomes. Likewise if the units are different. Double that if the order in which they move matters.

If you disagree, feel free to give an example where there are only 18 unique combinations of positions at the end of the turn.

I do realise that the system is obviously NOT one or the other, but every time the AI moves a group of warriors it is NOT choosing between 9^x moves where x is the number of warriors.

That is just what the AI would be doing if it was performing an exhaustive breadth-first tree search algorithm.

[Maidel]

Its not a case of having ONLY 18 possible outcomes. ITs whether the out come of one affects the other.

Think of a number between 1 and 9.



now think of a second number between 1 and 9 (it can be the same)


how many options did you have? you certainly didnt have 81 options - you only had 18. This is because you processed the first one before ever contimpating the second one.


If the warriors movements are completely unlinked the computer would think of where to move the first one - 9 options and THEN and only then think about where to move the second warrior - also 9 options meaning its had to contimplate only 18 options in total.

As I said this is NOT the way the pc works it out, but as someone has already proved it is totally impossible for it to work out all possible outcomes and choose the best one, the PC obviously does not work out all the warriors possible moves.