Writing Intelligent Games - Zafer Barutcuoglu ===================================================== Decades have passed from the first appearance of chess computers to the cunning strategies of Warcraft II, and machine intelligence looks like it will be at least as popular in the future. Especially with the recent struggle between Kasparov and Deep Blue, the subject once again gained world-wide popularity. Artificial Intelligence (AI) being one of the oldest and widest research areas in computer science, it is not possible for me to give a read-this-know-all tutorial here. Yet, as few housewives who use a washing machine know how it works, we don't need to go that deep; only deep enough to use in games we write. What is intelligence? Amusingly, that single question makes up a massive bunch of the AI-related scientific texts around. Our case- specific answer would be the ability to challenge the other player in the game. Lets not get into this void discussion and move on to the real question: How. So, how do we achieve AI? This again must be considered specific to the case, and even specific to your game itself. There are numerous methods developed for different types of task. A chess playing algorithm is nowhere similar that of a football games, or even Go, another table game. Therefore our methods depend completely on the nature of our game. As I cannot explain AI for each single game written, I will describe certain major methods utilised. The Simplest Level =================== If you have ever written an arcade game with computer opponents, most probably the computer opponent works on a set of if statements. That's the simplest level of AI. Actually, its not even clear that its AI, but as I said, we will not discuss that here. Just keep in mind that a major branch of AI research called expert systems is exactly that; a set of ifs. For harder problems though, you need something better. Enter the game-tree. Game-Trees and Chess ===================== Chess, however complicated it seems as a strategy game, is among the simplest to analyse. This results from its nature as a board game, with finitely many piece positions (64 in all), and finitely many pieces (32 in all). So in all positions of the board, the player has a finite -and indeed relatively small- number of moves. On this basis, we can say that there are a finite number of chess game sequences on earth. At each instance of the board, we can list all the possible moves. Similarly, after each of these possible moves, we know what the board will be like. In this way we can construct what we call a game tree, whose root is our current position, whose branching points are intermediate board instances, and whose leaves are game endings. If we construct this tree once at the beginning, we virtually win the game NO MATTER WHAT. Actually we lose only if we are black and playing against someone who also has the complete tree. However in practical terms, this tree is huge. Huge. HUGE. It is virtually impossible to create completely, even using the worlds most powerful computers today. So what we do is, before making a move, we construct the game tree rooted at the current instance, with a fixed depth. So the leaves are no more necessarily game ends. Now we need something else to decide about towards which leaves we want to go. That is to say, which leaf is the more advantageous for us? For this problem we construct a scoring function which takes a board instance as input, and outputs a numerical score indicating which side is in a better position, and how much better. This function typically depends on the number and nature of pieces left on each side, mobility (number of moves possible), castling ability and other factors. This is left to your level of chess playing. When we have this function, we score the leaf positions. Then assuming that our opponent will make their best move, and that we will make our best, we advance up the tree. This is called the minimax algorithm because if its the opponents turn, we will take minimums, as he will try to minimise our score, and if its our turn, we will take maximums. Each node will take the min-or-max of its children, and when we reach the level just below the root, we will be left with our possible list of moves, but each having a score coming from the leaves. Then all we have to do is to make the move with the highest score. All that simple. The depth -called ply- to which we construct the tree is important, as time and space increase exponentially with it. 4-Ply is accepted as minimum, but I could hardly go up to 3 in my first chess program. Other methods exist that increase the depth conditionally, like in case of a capture at the leaf. This, while very simple and primitive, is the general basis for a chess program, and while it is unlikely to win, you CAN get a chess program running that will challenge beginners. I did. It was about 600 lines of Pascal and taught me more than 600 pages on AI, because this method, the game tree, is in no way restricted to chess. Indeed it makes up the skeleton of many AI engines around. Still, do yourself a favour. Write a chess program. Heuristics =========== Observe that we reduced the search depth to make it more applicable. This is an example of the often encountered trade-offs in engineering. Actually, that's where the trick lies, because everybody knows how to do the work, but the fastest wins. Heuristics is the name for making wise trade-offs. Imagine a heuristic to be a tour guide that takes you to the best places in the shortest time. Another example would be a car parking process. The driver parks his car to the first place he finds when he is close enough to his destination, although there might be empty places nearer ahead. Similarly you can stop branching your game tree at really stupid moves before full depth, and although that move might be an utterly clever trap, the odds are very high that it is not, and your program will only run faster. This is called alpha- beta pruning, or pruning for short. In any way, pay attention to your heuristics. Advanced Methods: Planning =========================== When your problem is too complicated for a brute-force game tree, you've really got yourself a problem. If you've come down to this, either your time or space, or both, is not discrete. Well, of course everything is discrete for computers, but we know that doesn't help us much when we have a game board of 640*500 pixels instead of the 8*8 squares of chess. An illustrative example is the Japanese game of Go. Its played on a 19*19 grid with identical game pieces. And you can NOT look ahead more than 2 or 3 moves, simply because after 3 moves you have 391*391*391=59776471 possible boards. Plus, due to the nature of the game, the result heavily depends on the beginning moves and a game takes between 200 and 350 moves to finish. In these terms, you can easily imagine that this game is impossible to implement on a microcomputer. Fortunately, this is not so. Under such heavy problems, we can no more think at low levels like game trees. We use high level AI techniques, like Planning in this case. Planning is the process of dividing a task into smaller tasks, ordering them according to their nature and dependencies, and carrying them out in this order. In our game of Go, this might mean deciding whether to attack the corners or dominate the centre, for example. I don't assume that you know the game, but note the difference between this decision and that of whether to move the Knight or the Bishop. If you give a little thought to this, you will notice that real-life decisions such as commanding an army or banking investments are often in this broad nature. That's also how you play games yourself. Well, so why didn't we apply this to all of our games since the beginning? Simple. What we used worked for us. If you sit down, do some hands-on programming and implement these methods, you will discover that as you get smarter methods, your code gets increasingly bulky and difficult to manage. Moreover, game-trees for example are proven to be more efficient than planning in chess playing. This is not that surprising when you remember that you are more intelligent than your computer, but it calculates faster. So, use simpler methods when you can. Coda ===== Although there's so much more I would like to talk about on AI, I limit myself to game programming, and I suppose, that much should get you programmers going. Coding something intelligent gives you a pleasure that few other things can. Be it tic-tac-toe or Warcraft XXI, try it. Read, read code, code. These three always pay back. Zafer Barutcuoglu -