|
Gil R. -> RE: Detailed battles AI sucks (12/20/2006 5:34:57 AM)
|
Kid,
In the "Command/Control madness!" thread in the Support sub-forum Eric posted the following message (the latest in a series of such posts on both this forum and the "Crown of Glory" one). This will explain why asking for superior AI often falls into the category of "easier said than done."
The AI is never going to be able perfectly to simulate the minds of commanders on the field of a Civil War battlefield -- there will always be little things wrong with the AI. I'm happy to work at identifying and correcting some instances of poor behavior, however, as I've mentioned, I have found in the past that often in doing this, the "fixes" that rule-out poor behavior end up crippling the AI in other ways and frequently create just as many problems as they solve... though not always! sometimes fixes do work, but it's a lot of effort to separate the wheat from the chaff, so to speak.
Every six months or so I write a little post on the theoretical limitations of AI; I won't go through the whole thing now, but will summarize. The way that AI works is by searching through something called a "state space" for the game, to look for optimal changes to the game's current state. The larger the size of the game's state space, the longer it takes the AI to find maxima within it. For most games that people enjoy playing, the state spaces are so enormous that AI's never actually search the entire state space, even for a single turn. A game like tic-tac-toe (or, uhm, noughts-and-crosses) does have a solubly small state space; a game such as Chess does not. I've calculated the rough size of FOF's state space, and to search through all the permutations of the state space for a single turn at PC processor speeds would take longer than trillions of times the age of the Universe. So most games using AI have to use approximation techniques to search subsets of the state space -- they have to identify vast parts of the state space to exclude from their search in order to whittle down the size of the space to something that is a searchable size. For a game like FOF, this means excluding more than 99.99999999999999% of the possible moves from the AI's consideration.
Programmers working with AI spend a lot of time refining the approximation to the search of the game's state space, and there are many documented techniques for doing this. Even for relatively simple games, however, these techniques have not been very successful. I've studied the AI for the game Go quite a bit in the course of trying to teach myself how to program AI. Go has a state space that is considerably larger than Chess, but much, much smaller than a game like FOF's. There have been PhD computer scientists who have dedicated their careers -- one guy I read has been working on this for 30 years -- to developing good Go AI algorithms, and there's a whole community of computer scientists who are working on solving the problem of Go's AI. Given all the enormous human effort poured into writing a good Go algorithm, it's disappointing to learn that the best Go algorithm that's been developed to date only has the Go ranking of "weak amateur" when playing against human opponents, and even that algorithm requires more computing power than a standard PC has and takes a long time between turns to make its moves. Given that FOF's state space is exponentially larger than Go's, and also considering that I'm not about to devote my entire career to developing a FOF AI algorithm, and also considering that there is not a community of PhD computer scientists working on this problem, to expect the AI to play above amateur level or (much harder) to simulate what historical generals might do is, I humbly submit, an unreasonably high expectation.
|
|
|
|
