Information about AI to Draginol

from GalCiv2 Forums
Hi there. I remember, in one of our discussion about the AI's-core weaknesses, you mentionned that the reason the AI has difficulty considering high-movement ships is because it works on the same principles of a Chess-AI, and where the Chess-AI only has to consider 1 pawn moving (and only 2-3 destinations), the GalCiv-AI has to consider 300, with about 50 destinations each. The more you increase the ship's speed, the more difficult it becomes to the AI to efficiently move.

I read an interesting article in this week's "The Economist" yesterday, about the principles of Chess-AI, which is called "brute force". The AI anticipate every move possibles, and chooses the one that leaves the human player the less chance to win on the long run. Does the GC-AI work pretty much the same?

But in the same article, they talked about our AI's inneffectiveness at the Go game, which is more complex in term of strategy. It was saying that the scientists used a Monte Carlo-based probability estimator, which was much more efficient (speedwise and strategywise) for the AI. With recent improvement, they made it so the Go-AI can beat a strong opponent on a small-scale game, which was considered impossible a few years ago.

I tough that GalCiv looked a little more like Go than Chess in term of complexity, so maybe it would be more appropriate.

Since I am an addict to this game, I simply wished to inform you. Perhaps it could help you for GC3, or whatever future project StarDock develop.
11,274 views 10 replies
Reply #1 from GalCiv2 Forums Top
Good thinking, would be nice if brad would give his reaction.
Reply #2 from GalCiv2 Forums Top
I started playing Go about a year ago and its a fantastic game. Definetly a game I would recomend to a AI programmer.
Ashes of the Singularity II
Reply #3 from GalCiv2 Forums Top
I'm interested in how this works. Do you have more information on the article?
Reply #4 from GalCiv2 Forums Top
I started playing Go about a year ago and its a fantastic game. Definetly a game I would recomend to a AI programmer.


I used to play, but our gathering place shut down. Now I play MTG.
There are, however, many more similarities to chess than Go when concerning GCII.
1. The ships/pieces move.
2. They each have various MPs, as opposed to one piece per turn.
3. From what I've heard, the AI runs mathematically too algorithms. It simply takes numbers and responds to them based on what's put in.
Reply #5 from GalCiv2 Forums Top
The biggest problem with Monte Carlo simulation is the raw computing power required to run them. If the AI were to analyze all ship moves in a given turn it'd require enormous processing power. Of course, with Moore's law and all, we'll get to the point where that's possible in due course. It's a really neat idea, actually, it's just probably a long way off from being practical.
Reply #6 from GalCiv2 Forums Top
The biggest problem with Monte Carlo simulation is the raw computing power required to run them


It was, until recently. They have found ways to make Monte Carlo simulations much more power-efficient. Or so I remember the article saying. I will give the magazine's exact stats and page when I will get back my copy (we trade books ).

However, I doubt I can really make a direct retranscription without violating copyrights.
Reply #7 from GalCiv2 Forums Top
A simple summary of the techniques involved would be nice... after that, google does the rest!
Reply #8 from GalCiv2 Forums Top
Well, as I understood the idea (but I may be wrong. This post is open to future editing), they used a Monte-Carlo simulator, and when the AI finds a senario having 80% probability of success, he tries to apply it.

For explanation of the monte-carlo method of simulation, here http://en.wikipedia.org/wiki/Monte_Carlo_method

As I understood it in my financial course, you set the tree of possibilities, and the actions you can take. You set the optimal solution for every situation that can happen, then you run the scenario, seeing what is the value of every choices in front of you. For example, if business is good, you have the option to expand or to sell. since the decision to expand is much better (in this situation) than to sell, the face value of the "Sale" option is 0 if "Sale" isn't also the optimal solution if business isn't good.

The application in a video game would probably check the value of building a ship on planet X. The AI could calculate the added value of building this ship based on the probability of you [put every contingencies that a crazed human player would do]. He would then choose the option having the higher value.

This is where my (very very very limited) comprehension of Monte Carlo probability and video-game programming ends.

I will give a summary of the article when I get my hands on the paper. If someone else is an Economist fan here, I would be grateful to learn that I am not alone
Reply #9 from GalCiv2 Forums Top
The Economist, edition of the 27th January
p.80

"Artificial Intelligence: Winning ways"

Researchers in the field of artificial intelligence have long been intrigued by games, and not just as a way of avoiding work. Games provide an ideal setting to explore important elements of the design of cleverer machines, such as pattern recognition, learning and planning. They also hold out the tantalising possibility of fame and fortune should the program ever clobber a human champion.

Ever since the stunning victory of Deep Blue, a program running on an IBM supercomputer, over Gary Kasparov, then world chess champion, in 1997, it has been clear that computers would dominate that particular game. Today, though, they are pressing the attack on every front. They are the undisputed champion in draughts and Othello. They are generally stronger in backgammon. They are steadily gaining ground in Scrabble, poker and bridge. And they are even doing pretty well at crossword puzzles. There is one game, however, where humans still reigh supreme: Go. Yet here too their grip is beginning to loosen.

Go was invented more than 2,500 years ago in China (Confucius considered it a waste of time). It is a strategic contest in which two players take turns to place stones on the intersections of a grid with 10 lines on each side. Each player tries to stake out territory and sourround his opponent. The rules are simple but the play is extraordinarily complex. During a game, some stones will "die", and some will appear to be dead but spring back to life at an inopportune moment. It is often difficult to say who is winning right until the end.

Deep Blue and its successors beat Mr Kasparov using the "brute force" technique. Rather than search for the best move in a given position, as human do, the computer considers all white's moves-even bad ones-and all black's possible replies, and all white's replies to those replies, and so on for, say, a dozen turns. The resulting map of possible moves has millions of branches. The computer combs through the possible outcomes and plays the one move that would give its opponent the fewest chances of winning.

Unfortunately, brute force will not work in Go. First, the game has many more possible positions than chess does. Second, the number of possible moves from a typical position in Go is about 200, compared with about a dozen in chess. Finally, evaluating a Go position is fiendishly difficult. The fastest programs can assess just 50 positions a second, compared with 500,000 in chess. Clearly, some sort of finesse is required.

In the past two decades researchers have explored several alternative strategies, from neural networks to general rules based on advice from expert players, with indifferent results. Now, however, programmers are making impressive gains with a technique known as the Monte Carlo method. This form of statistical sampling is hardly new: it was originally developed in the Manhattan project to build the first nuclear bomb in the 1940s. But it is proving effective. Given a position, a program using a Monte Carlo algorithm contemplates every move and plays a large number of random games to see what happens. If it wins in 80% of those games, the move is probably good. Otherwise, it keeps looking.

This may sounds like a lot of effort but generating random games is the sort of thing computer excel at. In fact, Monte Carlo techniques ar emuch faster than brute force. Moreover, two Hungarian computer scientists have recently added an elegant twist that allows the algorithm to focus on the most promising moves without sacrificing speed.

The result is a new generation of fast programs that play particulary well on small versions of the Go board. In the past few months Monte Carlo-based programs have dominated computer tournaments on nine- and 13-lines grids. MoGo, a program developed by researchers from the University of Paris, has even beaten a couple of strong human players on the smaller of these boards -unthinkable a year ago. It is ranked 2323rd in the world and in Europe's top 300. Although MoGo is still some way from competing on the full-size Go grid, humanity may ultimatly have to accept defeat on yet another front.


For when GalCiv2?
Reply #10 from GalCiv2 Forums Top
bump

no comments..?