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 -
(
geocities.com/timessquare/2795) (
geocities.com/timessquare)