I had some basic courses on the subject of creating a minmax search tree for games in college at GaTech. I learned a lot from my professor Thad Starner and reading the "Artificial Intelegence: A Modern Approach". Creating one for something like X-Com turns out to be a big challenge. Here is a screenshot from a prototype game I developed in my free time (mostly focusing on the game engine and not the look and feel yet):
Minmax and Alpha-Beta Implementation and Challenges
It wasn't hard automating actions like moves, end turn, and using items - this was already there because it was needed by the UI. It did take a second to figure out how to represent all the different actions a player could take. Fortunately, the game already had a concept of different games having a different "process id" so that multiple games could exist at the same time. By making some processes public and ones that dealt with A.I. private... each action could be stored and evaluated.
After having separate game states and a way to evaluate them, next came minmax. This wasn't hard at all and started out with a simple BFS of items, end turns, and moves. At last, a full tree of every single possible action a player could make. However, this took a very long time. Here is a screen shot of a tree using JGraph to visualize what happened in the search (green are moves, yellow are items, and red is end of turn):
Next, I implemented alpha-beta pruning to speed things up a bit. This helped a lot! For a tree that looked 2 turns ahead, it went from 13 min down to 1 min. This was giving me about 600 nodes/sec.
Now I could test the A.I. in the game and see how it performed. Well, it turned out that I was using a very small board (4x4) and two units that didn't have many item actions. The outcome was a single unit to calculate 1 turn ahead needed over 1 hour. This was horrible and devastating at the same time. I started thinking: Is minmax not usable in practice? Do I need to use some sort of greedy, iterative deepening to come to a conclusion faster? Do I need to switch to something like Machine Learning?
I was hurt emotionally... I needed help or my A.I. would take too long for it to be useful. I asked a few people that I knew of in the field of A.I. and received a very positive response from Mark Watson. I found him by reading some of the papers he wrote on alpha-beta searches posted on his site. He stated a few pointers; the most notable of which being that 600 nodes/sec is much too slow. Some quick searches revealed that, at tournaments for chess, programs reached thousands of nodes per second. I didn't see one that did less than a few thousand (pdf).
I found that the "line-of-sight" algorithm was taking a very long time. Fixing this reduced the speed from over 1 hour down to a reasonable 30 sec for 2 turn look ahead. This gave me about 7,000 nodes/sec. Much faster and usable in the game, but not the greatest.
I played the A.I. again and it seemed fine in an open room, but now had a lot of issues with the fog-of-war. I need to add some belief information so that the A.I. will not forget about the opponent when not in sight and then forget later on when there are too many possibilities. This is very challenging because the opponent must be accounted for and a lot more special rules for evaluation and determining what the opponent did on their turn while matching it to the current state.
Another issue is that the A.I. just sits around when no other player is near. I need to add some evaluators for searching, guarding, etc. For now, this would just complicate things more.
No comments:
Post a Comment