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

[padillah]

Originally posted by vulture
Are you sure you mean logarithmically?

No, I meant exponentially and linearly. I was trying to remember "linearly" and remembered "logrithmically" instead. I corrected it in an edit.

Tom P.

[vulture]

Originally posted by 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.

That's just a crazy way of looking at it.

I have one set of nine choices, followed by another set of nine choices. If you want to call that 18 choices, I can't stop you I suppose. I can just point out that the number 18 there has nothing whatsoever to do with the time necessary to analyse all possible choices. If you want to consider all possible sets of choices I could have made, and the consequences of them (assuming there are any), you need to evaluate 81 scenarios. That is the number of possible outcomes. [it]That[/i] is the relevant number for how much computation is needed to do a tree search algorithm.

If you want to call that 18 choices, then so be it. I call it 81 choices. The difference is that my number has some relevance to the real world implications, while yours doesn't. I'd say that when discussing the difficulty of AI programming, having your 'number of choices' mean something relevant to the programming difficulty is impotant.

The only way you can make '18' relevant is if you evaluate the choices for the first warrior, move it, and then evaluate the choices for the second warrior. Which is what you've been on about stressing the independence of the moves. But they simply aren't independent like that (which is why I ignored the possibility). Or, more to the point, an AI algorithm certainly can't assume they are independent - it can only determine that reliably by examining all 81 possibilities and seeing whether the moves are truly independent (this turn) for all 81 outcomes. If so, it can judge that in retrospect, it could have made a simplifying assumption...

[Maidel]

Originally posted by vulture


That's just a crazy way of looking at it.

I have one set of nine choices, followed by another set of nine choices. If you want to call that 18 choices, I can't stop you I suppose. I can just point out that the number 18 there has nothing whatsoever to do with the time necessary to analyse all possible choices. If you want to consider all possible sets of choices I could have made, and the consequences of them (assuming there are any), you need to evaluate 81 scenarios. That is the number of possible outcomes. [it]That[/i] is the relevant number for how much computation is needed to do a tree search algorithm.

If you want to call that 18 choices, then so be it. I call it 81 choices. The difference is that my number has some relevance to the real world implications, while yours doesn't. I'd say that when discussing the difficulty of AI programming, having your 'number of choices' mean something relevant to the programming difficulty is impotant.

The only way you can make '18' relevant is if you evaluate the choices for the first warrior, move it, and then evaluate the choices for the second warrior. Which is what you've been on about stressing the independence of the moves. But they simply aren't independent like that (which is why I ignored the possibility). Or, more to the point, an AI algorithm certainly can't assume they are independent - it can only determine that reliably by examining all 81 possibilities and seeing whether the moves are truly independent (this turn) for all 81 outcomes. If so, it can judge that in retrospect, it could have made a simplifying assumption...

I love the way that when you show someone even the smallest error in their theory, they call you crazy (or worse...)

I have been saying ever since my first post that I KNEW it wasnt the way the AI handeled it, and I have been stressing in every single post that what I was saying only worked for situations where both occurances are independant (which I know they are not)

All I meant that was it is totally impossible (As some helpful person proved) for the AI to analyse all possible moves all the time.

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?

I answered your question, and I dont want to make a point of it.


18 is the number of options the computer needs to look at if the events are not linked, 81 is the number of options it needs to look at if they are linked. Someone showed that looking at all 81 possibilites would not be possible (given that there are almost always more than 2 units at anyone time) and therefore they had to be a simpler system, of which I had no knowledge.

[qbert2]

and this is why CS students must take math courses that teaches them basic counting.

[GodSpawn]

18 is the number of options the computer needs to look at if the events are not linked, 81 is the number of options it needs to look at if they are linked. Someone showed that looking at all 81 possibilites would not be possible (given that there are almost always more than 2 units at anyone time) and therefore they had to be a simpler system, of which I had no knowledge.

And the point is that they ARE linked. The game state is determined by the position and state of ALL units. Therefore, by definition, the events ARE linked, and the AI must consider them to be so.

Whether or not a change of state has any effect on the game is a different matter - and one that can only be determined by inspecting that change of state. There is no other way to do it.

The combinational explosion exists.

[Fried-Psitalon]

Originally posted by Sir Ralph


It seems to see through the fog of war. I have a savegame proving this. This counts as rule cheat (not bonus) in my books.

Now THIS is on-topic and troubling. Ralph, can you post the save and/or conclusive screenshots that show unquestionably that this is going on?

[Bhruic]

Originally posted by Maidel

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

I'll stop all the other arguing right there - they are. How could you possibly expect that the moving of one unit wouldn't impact another? That would mean that if the AI moved a settler next to an enemy unit (ie, one it hadn't seen before it moved), it shouldn't consider the enemy unit when it moves any other unit. And it shouldn't consider that it's settler is now in danger.

Obviously it should. And does. There is very little, in game terms, that doesn't impact other parts of the game in some fashion. It would, therefore, be idiotic to consider the game-state static from the beginning of the turn, and not make any decisions based on information obtained during that turn.

Bh

[Sleestax]

I keep hearing people saying that the AI is as good as it can possibly be. If that is the case, then why have there been improvements to it over the years? Go back and read some of the patch release notes for previous Civs if you think the AI has not been improved upon.

There is am amazing amount of vitriol coming from certain people at the mere suggestion that improvements can be made.

I suspect that Sid's group thinks improvements can be made or they are not planning on making a Civ 5.

[padillah]

I could anoy everybody and bring up "play the board" mechanics that depricate combinatorials.....

but I won't.

Tom P.

[GodSpawn]

I keep hearing people saying that the AI is as good as it can possibly be.

Really? I don't see anyone saying that, but as ever I am prepared to be proved wrong, especially if pointed at a post stating that the "AI is as good as it can possibly be"...

My own position was that letting a bunch of part time programmers have a go is unlikely to elicit any major improvements to the AI/heuristics - And I cited FreeCiv as an example of a game that has had many years of development by part-time programmers, and yet has an AI that isn't as good as Civ's.

[smellymummy]

Originally posted by alva
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.

well it could also mean the players are newbies to the game...

iirc, lots of the code is rehashed from the old codebase they (firaxis) have, i know i've read somewhere about how it helps them having all that old code. just about every programmer i know has some sort of codebase they use. i'm sure there's been AI tweaks and such, improvements for sure, but like someone pointed out it would take a long time to build a decent AI.

as for all those possibilities, that doesnt mean for two units there's got to be 81 different if statements. most of the stuff we do in the game is repetitive. build the game with no AI first, just humans vs humans. then implement those strats for the computer. someone else could do that, i'll just buy the game

and on the topic of AI programming, I'm surprised no one's mentioned database driven AI. apparently people have done nice things with that.

anyway, the moment there is a good AI, we'll be seeing threads such as 'its 2005! why can't i even beat a computer game!'

[Fried-Psitalon]

The CIV AI is new.

[smellymummy]

well i was refering to sid meier's q and a on slashdot:

http://interviews.slashdot.org/interviews/05/10/21/0550213.shtml?tid=11&tid=10

from answer number 4, i just assumed some things got rehashed, tweaked and improved.

[alva]

well it could also mean the players are newbies to the game...

Which is pretty much how the AI starts each game, is it not.

I know, it's not completely correct but it's not that far off either.
Don't forget that the AI doesn't get to choose the map, can't obuse rules, has to be capable for all maps, not just pangea or continents.

I can't even begin to fathom how someone can make an AI as good as this one...
Is is perfect, certainly not...pretty impressive it damn well is though.

[Gaal Dornik]

Maidel
18 is the number of options the computer needs to look at if the events are not linked, 81 is the number of options it needs to look at if they are linked.
Correct. The unlinked state is equivalent to having two different games, occupied with one warrior each. This could very well( and probably is) be used to speed things up, as calculating 2 trees with 9 and 9 choices is obviously faster than one with 81 choices. In real game thats 9(warrior)*25(settler)*6(nations)=1350 calculations(not possibilities) or less needed for the first turn.

Although this is words-play. In reality we just used some intelligent algorithm to throw away unneeded parts out of these 81 choices to minimise calculations. In this case f.e. that every unseen unit is automatically unlinked, or similar.

padillah
So, to make a CIV game without "cheating" ... you would need to create 162 seperate and distinct AI's.
Well, the real question is, what makes a bad player play bad and a good player play good.