Blake: On BtS AI Programming...?

[Kuciwalker]

It's because the rules of chess are very, very simple, and the theory behind chess AI's has been well understood for a long time

[Solver]

Programming a chess AI is simpler due to a multitude of factors.

1. The rules of chess are very simple and thus an AI can easily have complete understanding of them.

2. The amount of possible moves in chess is low enough that it can be min-maxed 3-4 turns ahead even on slow computers via brute force. Not a good approach, though.

3. Evaluating your position in chess is much easier than in Civ. Even modern chess computers are far behind the best human players in this regard, but evaluating your position is relatively simplistic. As such, a chess-playing algorithm can quite easily discard the really poor moves and narrow down its selection to moves that are actually good.

4. Chess AI has been researched since ~1950 and the game itself has been seriously researched for 150-200 years, so the approaches to playing chess and to programming chess AIs are well-refined.

5. This one applies to modern chess applications - they make use of extensive game databases that simulate "experience". Chessmaster 9000 really knows every important game ever played. Given that one move (white move and black response) can be represented in 4 bytes without even giving optimization much thought, that'd be 160-200 bytes per game, let's say. So in a database of just 1MB, which is a laughable amount of data by modern standards, you'd be able to store ~5800 games on average, which could well cover the required experience.

[Kuciwalker]

2. The amount of possible moves in chess is low enough that it can be min-maxed 3-4 turns ahead even on slow computers via brute force. Not a good approach, though.

That is the standard approach. (Allowing for trticks like alpha-beta pruning, of course, and using a database of basically pre-generated knowledge.)

[Blake]

Just because it's standard doesn't mean it's good.

[Solver]

If you use a database and pruning algorithms, then it's no longer brute force, is it?

And if I recall correctly, then Deep Junior, which is a very successful program lately, uses an approach that significantly differs from min-maxing.

[joncnunn]

That would depend on implementation. I can envision a rather poor implemenation that searches trees longer but was based on info one turn ago.
Also as the number of civs were increased that would give each AI less time during this phase.

Originally posted by OliverFA
GalCiv has an option for the AI to be "thinking" always, including the player's turn. Would something like that make Civ AIs more powerful?

[joncnunn]

Re: Re: Blake: On BtS AI Programming...?

There's actually one major AI advantage in Nobel unmodified handicap.xml; major discount on unit upgrades. This basically results (on normal speed) in the AI getting its units upgraded much faster than a human's can possible be.

Also in Civ IV, the don't know what your doing is Settler with some pretty substantal AI penalties in other aspects.

Originally posted by vilemerchant

What makes you think the 'default' level is ever supposed to be any sort of actual challenge? The AI doesn't get insane bonuses on harder levels, it gets sensible bonuses that allow a computer to compete with more advanced human players. What you get on Noble is a level of play which applies to a n00b that just opened the box and doesn't really know what he's doing. It's easy because it's meant to be easy, there's 5 higher levels that apply to people who want it harder. Any lower than that and it's basically in 'baby mode' so your girlfriend/wife/any other female or AAHZ can play. :P

[joncnunn]

Actually a well designed program would be very easy to change search depth; just change it's the constants file from say 5 to 10; Done.

Now as to having it an option; I think the easyist way would be exposing it as a varaible to be loaded from the .ini file.

Now on my current machine (2004), the last thing I'd want is the AI to take longer, but whenever I get a duel-core processor then it might be a good idea.

Originally posted by Jon Shafer

In which case you'd essentially be writing 2 different AIs. It's not as though there's some mythical "Take longer and be smarter" switch that just needs to be flicked somewhere deep, deeeep in the code.

Jon

[joncnunn]

Most definately the case. Plus a flat depth search isn't particularly efficent and is subject to the horizon effect. Secondary searchs of promising paths are much more efficent.

Originally posted by Kuciwalker

Originally posted by Jon Shafer
You could, but you're more likely to end up with a better AI if you design it in a specific way, rather than making it "uber smart" and super-slow at one level, with the option of "stupifying" it to make it run at a reasonable speed for how 95% of players will want to play. It's not a hard-and-fast rule, but when available time and resources is your main consideration it's better to focus your efforts on the best payoff.

That's true. Plus, the way the search works a 10x increase in time would not give a corresponding increase in intelligence (however you measure that).

[joncnunn]

Don't feel bad being beaten in chess by a computer; grand masters generally don't win any more.

For that matter, Chess is probably close to being a solved game (loosest defination). My guess is with perfect play on both sides it's a tie. But unless your a grandmaster, that's not going to happen frequently so it still has interest among humans.

The bigest difference though between something like Chess and Civ IV is that in Chess there is no additional units being created. The unit count consinstly goes down, which is a whole lot easier to mechnically search than games in which unit counts go up.

Originally posted by Unimatrix11
I am not a programmer at all and i also mentioned this like two years ago. Also this is not to insult anyone or complain to anyone in specfic, BUT: I just wonder how on earth this chess-program on my C64 ("Grandmaster"), consisting of 8 KBytes of code (graphics included) and running on a 0.97 Mhz 8-bit-processor, managed to beat my ass pretty quickly (1 or 2 minutes per move IIRC) every single time for years... i actually never managed to beat it - and it didnt get any bonuses AFAIK ...

Yeahyeah - i know: It´s probably because i am a really poor chess player - but i am not (tho not a exactly a "grand-master" neither)...

[joncnunn]

The best chess programs contain:

1: A directory of standard opening moves.
2. A directory of standard end games.
3. Min - Max with secondary search aprox 50% longer than primary search.

And their look ahead on their best settings are a whole lot longer than 3-4 turns.

They are known to have found mates half way thru.

Originally posted by Kuciwalker

2. The amount of possible moves in chess is low enough that it can be min-maxed 3-4 turns ahead even on slow computers via brute force. Not a good approach, though.

That is the standard approach. (Allowing for trticks like alpha-beta pruning, of course, and using a database of basically pre-generated knowledge.)

[Blake]

Actually a well designed program would be very easy to change search depth; just change it's the constants file from say 5 to 10; Done.

Uhhhh no.

Because the AI behavior would also change, certain buggy or exploitable behavior would only emerge on certain search depths.

Further complicating things would be that it'd mess with difficulty levels.

Also it's exceedingly difficult to implement a temporal search depth, mainly because even a very shallow search is VERY slow. There are so many possible moves, with so many units on a map with many plots. Furthermore there is imperfect information making it extremely difficult to evaluate the strength of the position of opponents, which makes it extremely difficult to evaluate THEIR best move.

A spatial search depth is less problematic (for one it's only O(N^2)), other than that it would effect the unit behavior hugely, at low depths the AI would be blind, and at higher depths the AI would be easily baited. The present search depth, is for the most part, an unhappy medium where the AI isn't too blind, and isn't too easily baited.

The concept of search depth only really works for brute force approaches, which don't work at all for a game like CIV.

edit:
It's worth noting that human chess players "Brute force" chess, they just use a smarter approach than AI's, but they're still basically evaluating "all" possible moves, iteratively, just with smarter pruning and better evaluation functions (things which human minds are naturally good at).

Human players do not "brute force" CIV, they play by instinct for the most part. The AI plays the same way, it basically has hardcoded instincts. It's certainly not right to call it an artificial intelligence, probably in much the same way that you can't really call a Rabbit intelligent.
The AI is purely a creature of instinct ("doing what seems right") and impulse ("random numbers"), it doesn't have the faintest glimmer of intelligence.

One of the marks of a good player, is being able to overcome "instinctive playing" (also known sometimes as "One more turn") and actually engage in some intelligent thought about strategy. It's dead easy to get stuck just moving units and assigning builds and not actually "thinking" about the big picture. I'm obviously a good instinctive player because I programmed the AI's instincts, when I mess up in a CIV game it's always because I'm playing too instinctively and not thinking, this is things like getting stuck in a prolonged unproductive war, or letting opportunities slip by.

So finally:
"The real question, is not whether machines think, but whether men do"
The answers:
"They don't, and they often don't."

[rjmatsleepers]

Originally posted by Unimatrix11
I am not a programmer at all and i also mentioned this like two years ago. Also this is not to insult anyone or complain to anyone in specfic, BUT: I just wonder how on earth this chess-program on my C64 ("Grandmaster"), consisting of 8 KBytes of code (graphics included) and running on a 0.97 Mhz 8-bit-processor, managed to beat my ass pretty quickly (1 or 2 minutes per move IIRC) every single time for years... i actually never managed to beat it - and it didnt get any bonuses AFAIK ...

Yeahyeah - i know: It´s probably because i am a really poor chess player - but i am not (tho not a exactly a "grand-master" neither)...

The algorithm for a simple chess program is relatively straight forward; roughly consider all possible sequences of moves, evaluate the position at the end of each sequence and make the move that leads to the best end result. The number of pieces and their possible moves is (relatively) small. You need a small amount of code for the display, and also for the relatively simple interface. Voila - a chess playing program. As described the strength of the program depends on how many move sequences it can consider. There are a few tricks that allow it to eliminate "bad" moves quickly. The program has to look quite a few moves ahead before it can play a decent game.

The AI in Civ 4 does not work this way and there would be a number of problems in trying to apply the same approach. For example on the first move in chess there are 20 possible moves; in Civ 4 there are at least 800. In chess, you know the position of all your opponents pieces and their legal moves; in Civ 4 you do not know what units your opponent has or where they are situated. In chess, nothing happens by chance; in Civ 4, probability enters into the game regularly. This is not to say that the approach used in chess programs could not be applied. But it would require many orders of magnitude more processing power - perhaps ten to the power twelve more processing power to attempt to look 3 moves ahead.

In addition - unlike chess - the sound and graphical display (probably) consumes a significant proportion of the processing power. And the interface is significantly more complicated.

Chess playing by computer has had 50 years of academic and theoretical computing research. Even so it took more than 30 years before programs reached good club standard. I don't think we will see 30 years of research into AI programing for Civ 4.

RJM

Edit

The numbers above are way out. The number of possible positions after the human's first move is closer to 8,000 than 800. (I forgot to allow for the 9 possible positions of the citizen after founding a city.) As a result, a 3 move look ahead probably requires ten to the power eighteen times as much processing power in Civ 4 than it does in chess.

2nd Edit

The numbers in the above edit are still way out. I forgot to allow for the 11 possible tax rates. This suggests that the number of possible positions after the human's first move is closer to 80,000 than 8,000. A three move look ahead might require ten to the power twenty four times as much processing capability in Civ 4 as it does in chess. These numbers are beginning to look silly.

[rjmatsleepers]

Originally posted by Blake

It's worth noting that human chess players "Brute force" chess, they just use a smarter approach than AI's, but they're still basically evaluating "all" possible moves, iteratively, just with smarter pruning and better evaluation functions (things which human minds are naturally good at).

I was under the impression that research into human chess playing had concluded that humans do not evaluate all possible moves, rather, they consider only a small number. That only in complicated situations involving multiple captures do humans look many turns ahead. Their strength is (as you say) in their ability to evaluate a position. As a result, humans will miss obscure good moves such as a sacrifice that has a benefit many moves ahead.

RJM

[Unimatrix11]

800 moves in the first turn in civ4 ? Really ? Hmmm... let´s say you have a scout and a settler... each has 2 MPs and thus has a maximum of 24 tiles to reach... +1 to stay on... then where to settle, fortify or not... then building and research... hmm maybe you are right... but maybe its more about being able to move more than one piece each turn ?

BTW: What is the factor of processing power when you compare a C64 with a total of 64KBytes of RAM with a 2 or 3 Ghz 32/64 bit processor, assisted by a modern graphics card and 1 or 2 GBytes of RAM (running on Windows XP / Vista) ? I know it´s pretty impossible to give a straight foward answer to that question, and it is rather rethorical anyways - the difference must be huge.

I dont have any issues with BTS´s AI. I am perfectly okay with it (pretty much at least). So this is not to bash anyone. In deed i´d like to say "thanks" to Blake and all the others for their efforts. I am just thinking that, back in the days, programmers were simply more able to get more out of the hardware at hand. Just compare a C64 game of 1984 with one from 1988 (same goes for the playstation with different years of course - both are just examples). Nowadays it´s just: Get a new computer... it´s the backside of the OSA-coin, i guess.

Yeah i know i come off as pretty backasswards, but: Someone mentioned that a lot of the processing power in Civ4 (and every modern game for that matter, i might add) is used up for handling the graphics and the interface. Personally, i dont give a damn about the graphics - indeed i find them contra-productive sometimes in a sense that they kill off my own phantasy (pretty much like the difference between reading a book and watching the movie based on it) - so to be honest: I crave for civ1-style graphics (with a higher resolution and more colors alright) and really dont bother about 3D(ish)-graphics. But it´s been a trend ever since computer-games became popular: Better graphics - worse game-play (not that this applies to civ4 in particular). There is only a few exceptions to that - like the strategic commands (I & II) or the paradox titles (tho since EU3 that is off the exception list as well). In fact, the "new" Sid Meier titles are kinda symptomatic: The games themselves are like 15 years old - they just get renewed graphics and the game concept gets dumbed down a bit - et voilà: the "perfect" mass-compatible game. It´s a bit of a shame: When those games where new (late 80´s early 90´s), they were ground-breaking - Sid had rightfully earned an eternal place in the hall of fame of game-designers - but now that fame gets kinda tarnished (IMHO) for i would expect something new from the best game designer of all times (as i call him), instead of just re-launching old ideas. Did he really run out of new ones ? Or might it rather be, that the ideas that he still has are simply not compatible with the mass-market ?

The "audience" of computer games has changed quite a bit in the last 20 years: Back then, whoever played a strategy computer game, was more or less a hardcore-gamer, compared to modern standards. As there were no real casual gamers (i just assume that, based on my own experience), games tended to be more sophisticated and less about the graphics (that of course as a lot to do with the advent of CD and SVGA). (RT-) strategy titles nowadays more about "i wreck havoc by my mouse and it better look good" than about the strategy behind it. With the poor graphics two decades ago, such games would have simply not sold themselves. If they did come out, they were more correctly labeled as "action", rather than "strategy" - cause thats what RTS-games really are about: Fast clicking and enjoying the visuals - just like "R-Type" and "Katakis" were. They are for the casual gamers and without them they were non-existent.

All that wouldnt be too bad, if mass-market wouldnt tend to "kill off" the niches. If You can make a a) "smart" computer game with a ground-breaking idea, but a somewhat steep learning curve, that requires a weekend to even get into it OR b) just another ego-shooter or RT"S"-game with prettier graphics than the competition as its only selling point, which you know will work, it´s b) that´s gonna be made, for it will sell in millions, while your nerdy-hardcore title will probably not even make it to the shelves...

But enough of "babblebabble**********..."