Professorial Dissertation, 2009, 63 Pages
Table of Figures
2. PROJECT GOALS
3. INTRODUCTION TO STRATEGY COMPUTER GAMES
3.1 Tools and Technologies
3.1.1 The Microsoft .NET Framework
3.1.2 Available Literature
3.1.3 Overview of Existing Open Source Projects
3.2 Strategy Games Theoretical Concepts 10
3.2.1 Turn-Based Strategy Games: Classic Model Overview
3.2.2 Modern Approach for Turn-Based and Real-Time Strategy Games
The 4X: eXplore, eXpand, eXploit and eXterminate
3.3 Artificial Intelligence Algorithms and Concepts for Strategy Computer Games 32
3.3.1 Choosing the Right Algorithm
3.3.2 Theoretic Al Concepts
Defining the Problem Domain
Basic Movement: Bresenham's Algorithm
Advanced Movement: Extended A* Algorithm
Obstacle Avoidance in Dynamic Environments
Flocking: Follow the Leader
Next Target to Handle (NTH)
Next Pawn to Attack (NPA)
Next Pawn to Defense (NPD)
Next Pawn to Build (NPB)
Next Resource to Harvest (NRH)
Retreat Under Pressure (RUP)
4. FURTHER DIRECTIONS
6. APPENDIX: THE IPHA API
6.1 Disclaimer for the code and the document
FIGURE 1: ANCIENT EGYPTIANS PLAYING "SENET"
FIGURE 2: HEXXAGON BOARD LAYOUT WITH HEXAGON TILES
FIGURE 3: 8X8 "WESTERN CHESS" BOARD LAYOUT WITH SQUARE TILES
FIGURE 4: CHINESE CHECKERS BOARD LAYOUT WITH CIRCULAR TILES
FIGURE 5: INTERNATIONAL GRAND MASTER GARY KASPAROV PLAYS AGAINST IBM'S "DEEP BLUE" CHESS SUPER COMPUTER
FIGURE 6: "COMMAND & CONQUER 3: TIBERIUM WARS" (2007) − AN RTS GAME BY EA STUDIOS
FIGURE 7: "CIVILIZATION IV: BETOND THE SWORD" (2007) − A MODERN TBS GAME BY FRAXIS
FIGURE 8: CAMPAIGN VS SCENARIO SEQUENCE
FIGURE 9: THE FOG OF WAR − A PAWN OF TYPE "DOCK" HAS A CIRCULAR RANGE OF SIGHT. BLACK AREAS REPRESENTS
UNREVEALED TILES WHILE DARKENED AREAS REPRESENTS NON UPDATED TILES
FIGURE 10: AN EXAMPLE OF A RETICULATED 3D MAP SURFACE. EACH TILE HAS SPECIFIC ATTRIBUTES: MATERIAL, GEOGRAPHIC LOCATION, ALTITUDE AND MORE
FIGURE 11: RANGE OF HIT: A TANK HAS 7 RANGE OF HIT. GREEN LINES INDICATES "WITHIN RANGE"
FIGURE 12: MINERALS FIELD − A FICTIONAL RESOURCE PROCESSING CENTER AND HARVESTING PAWNS (STARCRAFT 2™ BY
FIGURE 13: EVOLUTION OF PAWNS: TECHNOLOGY BASED DEVELOPMENT
FIGURE 14: THE PROCESS OF ACQUIRING NEW KNOWLEDGE IN LEARNING MACHINES. "YOU DON'T KNOW A FLAME CAN
BURN UNTIL YOU ACTUALLY TOUCH IT ."
FIGURE 15: DIRECTED GRAPH STRUCTURE FOR ROUTE FINDING
FIGURE 16: BINARY TREE STRUCTURE FOR ROUTE FINDING
FIGURE 17: TILE BASED MOVEMENT − NONE OF THE EIGHT DIRECTIONS FOR THE HMMWV LEADS DIRECTLY TO THE
FIGURE 18: CHASING METHODOLOGIES − TO THE LEFT IS A SIMPLE CHASE. TO THE RIGHT IS A LINE OF SIGHT CHASE
FIGURE 19: BRESENHAM'S ALGORITHM (LEFT PATH) VS ANOTHER POSSIBLE ALGORITHM (RIGHT PATH)
FIGURE 20: PATTERN−BASED MOVEMENT − EXAMPLE OF GUARDING A FACILITY
FIGURE 21: OBSTACLE AVOIDANCE − RIFLEMAN A'S WIGGLE WALK
FIGURE 22: SQUARE FORMATION
FIGURE 23: ARROW FORMATION
FIGURE 24: TWO−FILE FORMATION
FIGURE 25: NPA UTILITIES TREE
FIGURE 26: NPD UTILITIES TREE
This project is dedicated to my family
"Unless a variety of opinions are laid before us, we have no opportunity of selection, but are bound of necessity to adopt the particular view which may have been brought forward."
Herodotus, 5th century B C, Greek historian
Strategy computer games are nowadays a very popular and exciting genre in the world of computer games. Many succeeding commercial games were developed since the end 1980's and contributed to the growth and interest in computer games in general and strategy games in particular. Games such as Command & Conquer TM series (by Westwood and EA Studios), Civilization TM series (by Sid Meier), Warcraft TM and StarCraft TM series (by Blizzard) entered to the computer games' hall of fame, thanks to their inventiveness, artificial intelligence challenge and visual effects that they offer.
Almost every strategy computer game was based on the idea of an "electronic board game", a modern brother to the classic, "physical" board games such as chess, checkers, backgammon, hexxagon and more. An interesting issue is the fact that both the classic board games and the modern strategy computer games are sharing many of the key elements that make the players think and act strategically and tactically, according to the development of the game. This issue is the basis for the project, and discussed further in the next pages.
It is common to divide strategy games into two main types: "Abstract strategy", where there is "perfect information" regard to the game's state. An example for an "Abstract strategy" is Chess. The other type is "Concrete strategy" where there is "incomplete information" regard to the game's state. This characteristic makes the game more interesting and surprising. An example for such a game is "Stratego"1.
This project aims to serve as an open source code framework, written under Microsoft .NET, for easy creation and expansion of "abstract strategy" games by providing operational artificial intelligence algorithms and well-defined class libraries based on concepts taken from "the game theory" for decision making aspects.
The creation of a comprehensive strategy games framework is a process which involves large scale of disciplines to research and develop, and hundreds (if not thousands .) of total human labor years. Generally, in every computer game company we usually find a large group of people that give a hand in creating a reliable commercial product. Among those people we find back-end and front-end programmers, game designers, story builders, QA testers, 3D modeling experts, directors and more.
As this project was written as an "internal project" in my B.Sc. degree studies (Computer Science in Tel-Hai Academic College) and I'm only a single person, I had to make a significant cutoff and focus on specific goals I want to achieve on a limiting work time. I didn't focus on writing the code itself, but otherwise deeply explored the principals of creating modern strategy computer game framework. The current version of the project's document covers three topics out of the totality subjects:
1. Describing the fundamentals of classic and modern strategy computer games.
2. Understanding chosen artificial intelligence algorithms based on "the game theory" and techniques that take part in strategy computer games. As AI algorithms for classic strategy games are widely described and implemented in many ways and plenty of information can be found, this project will otherwise try to cover aspects of AI algorithms that used by modern strategy games.
3. Well designed, multi-threaded .NET Class Libraries that can be later used for development a complete strategy game, also involving Microsoft's XNA. Thus, the game will be written in a complete managed code end to end.
Tel-Hai Academic College, Israel
Searching for a fitted programming language to use, I eventually found the Microsoft .NET framework (C# specifically) as the best one because of its strong, flexible and somewhat easy to use characteristics. I also kept in mind the fact that this project should be later enhanced and extended using Microsoft's new XNA technology, which is a set of tools with a managed runtime environment that facilitates computer game development and management. XNA attempts to free game designers from writing "repetitive boilerplate code" and bring different aspects of game production into a single system.
All the classes were written in the Visual Studio 2008 IDE, in so called "managed code", and could be used in both Microsoft and Linux operating systems (by using "Mono"). The .NET framework version is 3.5 and can be freely downloaded from Microsoft's website.
I couldn't find any specific book that covers all what I wanted to show in this project, so I had to read and collect information from many different sources, books, online materials and even user guides of game I managed to reach. I found that there is an available series of books publish by Delmar Cengage Learning and titled "Game
Development Essentials" (2007) which is a true game development encyclopedia and covers any possible information —from game project management to game artificial intelligence. Anyway I wanted to dig into the materia by myself and attack this subject from the pure game theory aspect, which is not a common methodology by the book writers.
Here is a list of the key sources I used in this project. The complete list of sources appears in the bibliography section, at the end of this document:
- "Artificial Intelligence: A Modern Approach" (Prentice Hall, second edition, 2002) by Stuart Russell and Peter Norvig. A comprehensive book for theoretic and general AI algorithms and concepts.
- "An Introduction to Game Theory" (Oxford University Press, 2003) by Martin J. Osborne. Presents the main principles of game theory and shows how they can be used to understand economic, social, political, and biological phenomena.
- "Artificial Intelligence for Games" (Morgan Kaufmann, 2006) by Ian Millington. Explains algorithms rigorously while also discussing appropriate implementation details such as scheduling AI over time and using the right data structures.
- "AI for Game Developers" (O'Reilly, 2004) by David M. Bourg and Glenn Seemann. Introduces to techniques such as finite state machines, fuzzy logic, neural networks, and many others.
- "Command & Conquer: Red Alert walkthrough — strategy guide" by Roger Wong, 1997 ( htt p ://www.the-s p oiler.com/STRATEGY/Westwood/red.alert.2.html) . The purpose of this online RTS guide is to aid the public with strategies and tactics for use in the game Command and Conquer: Red AlertTM, by Westwood Studios Inc.
- "Civilizations IV: FACl/Walkthrough by Warfreak" , 2007
(htt o :// www.gamefacis.com/com o uter/doswin/file/919352/47887).
- The purpose of this online TBS guide is to aid the public with strategies and tactics for use in the game Civilizations IVTM, by Fraxis Games.
There are several running open source projects for specific strategy games, which doesn't intentionally designed for general purpose, and many others that are no more under development. Source code repository sites such as sourcefourge.net and codeplex.com are hosting some strategy games code examples, currently in various development stages. I observed two projects which still running:
- "Bos Wars" (www.boswars.org): a grounded, multi-platform futuristic real time strategy game (RTS) with popular game elements, such as economy management and army building. It involves AI algorithms as well as graphics and sound handling. The source code is written in C++.
- "Battle for Wesnoth" (www.wesnoth.org): a grounded, multi-platform turn-based strategy game (TBS) with a fantasy theme. Has a reach inventory of unit types and races. The source code is written in C++.
Turn-based strategy games, often abbreviated as "TBS", are an old genre of entertaining instrument with a long history of development and changes. Although chess (at least the so called "Western" chess variation) is the most famous and considered a historic representation for TBS game, we can find much older sources — back to 3100 BC (Predynastic Egypt period), such as the "Senet" game evolved by the ancient Egyptians2.
Maybe the main reason that TBS games were developed especially in nationalistic and militant cultures is that TBS games force you to "think twice" before you order your warriors to do the next step. You always keep in mind that if you lose, the "assets" you're holding will be lost, and thereupon be remembered eternally in disgrace .
illustration not visible in this excerpt
Figure 1: Ancient Egyptians Playing "Senet"
A very important keynote that will help you survive and eventually win the game is the fact you can always see the current state of the game. That is, where is yours and your opponent pawns are placed, how many pawns you and your opponents left, what are the risks that each of yours and your opponents pawns face with, what are the legal moves you and your opponent can do next, be aware to the size of the "battlefield" and its restrictions (which is not being modified during the entire game) and so on. This type of knowledge is known in the world of artificial intelligence (Al) as "perfect information", where you have a complete picture regard the current state of all parameters of the game.
This privilege of knowing the entire details of the current state (a.k.a. "Abstract strategy pattern") is something that distorts the truth, since in the real world you know some of yours and your enemy's abilities. Even if you have the most powerful intelligence forces, it helps you know most of the information, but not everything. Also, you don't always have a complete data regard the manpower quota you keep, naturally not that of your enemy. You also don't know what the final borders of the battlefield are. In spite of that, for those old days these restrictions weren't an actual factor and it was a highlight game for the players of that era.
Specifically in TBS games3, each player makes his move in his turn while the opponent only observes it. That is, the progress of the game is done synchronously, making the state change be done only by a single player. This behavior is what making the game "turn-based". We should notice that a "move" can be interpreted as zero or more pawns changing of place, and not only a single step as we use to think. We should also notice that an "opponent" can be interpreted as one or more players, and not just a single one.
When we face with the task of designing an abstract TBS game, we need to take in account the following elements which construct game rules:
The mission of the game, players, board attributes, pawn types and some other restrictions:
A classic TBS game has a well defined board state when the goal of the game is achieved. That is, as much number of players participating the game, there's only a single player who wins the game. Moreover, although the board state for symbolizing a goal is well defined, it is quite possible that there will be plenty of winning board states combinations, and yet the total number of winning boards states is finite (determined by the board size).
Several games, such as checkers and backgammon, have no "dead-end" board states. I.e., situations in which there are no more legal moves that can lead to a winning board state (and therefore the game is referred as "stuck"). Although dead-end states avoidance is not a must when designing new TBS games, it should be specified and get a proper treatment to keep the flow of the game. In AI terms, an algorithm with a "completeness" trait means it can always find a pathway for a state which not leads to dead-ends ("no solution").
The board's starting state has severe implications of the continuity of the game. A game begins with a board where the pawns are arranged in specific, pre-defined places. In chess there is a meaning for the arrangement of the pawns: two first lines fill with various types of pawns. In checkers however, all pawns has the same practice so it doesn't matter where to place them, as long as they are put in a preliminary X placement style.
Games being played individually, when no opponents are taking part (such as Solitaire), have no strategy aspects. A strategy game must involve two or more players playing head to head so that strategic decisions making can be performed. Logically, each player should own a private set of pawns to play with against the other players, and when more than two players are attending the game, it is admissible for alliances to exist.
"Alliance", sometimes defined as "Coalition", is a type of strategic model in which a group of players consciously cooperate in order to spur, optimize and markdown the total cost of achieving the goal, when ultimately sharing the booty4. Standard chess for instance involves only two players so alliances are irrelevant. "Multi chess" games however, enabling this to be possible because of the exclusive design of the board.
The "battlefield" in classic TBS games is represented as a fixed-size 2D surface. In the real world, when a soldier is ordered to move to a specific location he is generally receive a geographic coordinate to go to. A "coordinate" in our terms is condensed into a single geometric shape (a.k.a. "tile") that reticulates the surface equivalently. That is, a pawn can be moved step by step only by the restrictions of the outlining shapes. Also, the pawn is not permitted to move outside of the borders of the surface. A multi-directional surface, such as the Chinese chess layout, designed in a way which multiple players can simultaneously play the game. These various co binations of surface attributes gives each game a tailored "game board".
illustration not visible in this excerpt
Figure 3: 8x8 "Western Chess" Boar
illustration not visible in this excerpt
Figure 4: Chinese checker
illustration not visible in this excerpt
Figure 2: Hexxagon Board Layout with Hexagon Tiles
In order to fulfill our strategic decisions, the weapons we're fitted up with are the pawns. A pawn represents a single type of weapon which has a well defined movement abilities and "eating" potent ial, so pawn characteristics diversity is vast. Som e of the classic TBS games, such as backgam mon, has only a single type of pawn, while othe r games such as chess has several types of p wns. Checkers has a special feature of "upgradi ng" a pawn in the course of the game, wh n a "primitive" pawn transforms into a "king" aft er touching down on a first-line enemy t ile. Some pawns can move on a single direction (only-forward for example) while other can move in a multidirectional manner. Another issue to take into account is the lifetime of a pawn. For instance in checkers, when a pawn is being eaten by an opponent pawn, the eaten pawn stops from living and wiped out off the board eternally. On the other hand we have the backgammon in which the pawns aren't "killed" when being eaten but otherwise halted ("taken captive") until some board state fulfills (non captured pips in the opponent's side).
Last important thing that should be mentioned regard movements is that we can find in classic TBS games two movement feasibilities: pawn-type based movement, and dice based movement. This first attitude is found in chess-alike games, where each pawn perform specific move according to his type, and that is a deterministic decision for the player. The second attitude is found in backgammon-alike games, where each pawn performs an exact number of steps according to a random number produced by dice throwing, and thus it is a non-deterministic decision constrain for the player.
When designing a TBS game, it should be taken into account whether each player turn is time-limited or not. It is important point, mainly because we may want to limit the strategy decision making period, as theoretically it may take an almost-infinite time to inference the next best move, and we want to avoid this phenomenon. This kind of problem may exist between two human opponents (usually between two grand masters who make long and complicated strategy decisions) but at most when a computer is involved. That is, human against a computer or even worst, when computer plays against another computer.
So what, for example, is involved in chess programming? Essentially the sequences of possible moves form a tree data structure: The first player has a choice of 20 different moves (most of which are not very good), after each of which the second player has a choice of many responses, and so on. Chess computer games work by traversing this tree finding what the possible consequences would be of each different move.
The tree of moves is not very deep: a typical chess game might last 40 moves, and it is rare for one to reach 200 moves. Since each move involves a step by each player, there are at most 400 positions involved in most games. If we traversed the tree of chess positions only to that depth, we would only need enough memory to store the 400 positions on a single path at a time. This much memory is easily available on the today's smallest computers that are commonly in use.
Perfect chess playing is a problem in what we call "PSPACE"5, which is a term to define problems that can be solved using a reasonable amount of memory (formally defined as a polynomial in the input size) without regard to how much time the solution takes. Actually one must be more careful in definitions. There are only a finite number of positions in chess, so in principle it could be write down the solution in constant time, but that constant would be very large. Generalized versions of chess on larger boards are definitely in PSPACE.
illustration not visible in this excerpt
Figure 5: International Grand Master Gary Kasparov Plays Against IBM's "Deep Blue" Chess Super Computer
The reason this deep game-tree search method can't be used in practice is that the tree of moves is very bushy, so that even though it is not deep it has an enormous number of nodes. We won't run out of space if we try to traverse it, but we will run out of time before we get even a small fraction of the way through. Some pruning methods, notably "alpha-beta search"6 can help reduce the portion of the tree that needs to be examined, but not enough to solve this difficulty. For this reason, actual chess computer games instead only search a much smaller depth (such as up to 7 moves), at which point they don't have enough information to evaluate the true consequences of the moves and are forced to guess by using heuristic "evaluation functions" that measure simple quantities such as the total number of pawns left. More about decision making algorithms is in the next chapter.
End of a turn and movement policies: What exactly symbolizing the end of a turn and what are the policies of a pawn's movement, is up to the designer of the TBS game. An "end of a turn" situation can be indicated "manually", by which the player is formally declaring he has finished his turn, or be indicated "automatically" by which the player moves any of his pawns from one tile to another. Movement policies defined as whether the player is permitted or not to withdraw his moving decision after performing a move (yet didn't declare an "end of turn").
Next we'll see how today's strategy computer games takes most of the principles founded by the classic strategy games much forward and adds new features to enhance the game experience.
In the last 20 years we were witness to a tremendous evolution of home computers. New technological achievements, mainly in the miniaturization of electronic component, opened a new world of software development opportunities. The ongoing progress of cheapening home computers prices has lead to a reality where almost every family in the western world holds at least one modern PC. New generations of computers appear on a monthly basis and offer much faster processors, RAM, graphic cards and hard drive capacities. This international revolution and new market opportunities motivated the game companies to develop new genres of computer games which introduce exciting graphics and "almost-real" artificial intelligent while keeping the game run smoothly. Strategy games is a genre which naturally demands high system requirements because of the calculation complexity made by the Al decision making engine, not speaking about the large resources needed to properly display and handle lots of well animated maps, pawns and battles at a single point of time.
When we face with a standard classic TBS game we can easily find hard restrictions which accompany it. Let's take western chess as an example for a complex TBS game: We have a limited size of board with rough tile shapes giving the ability for rough moves, only six pawn types, no more and no less than two players and a single game objective. Well, although this is undoubtedly a high-class game considering the strategic challenge it offers, it is somewhat lack of gracefulness, taking in account all of its other factual parameters. Obviously the restrictions are a result of physical size limitations, memory limitations and cost of production, three core aspects which almost doesn't exist when we think about computer software.
So it was natural to take the foundations that classic TBS games inherited and extend them far beyond their original purposes using the power of software. Thus, a new exclusive brother for the TBS game has burn and given the name of "Real-Time Strategy", generally abbreviated to "RTS". This is a revolutionary improvement over the classic TBS as it is no longer turn-based, but otherwise an asynchronous environment, letting unlimited number of players to play all at the same time. RTS games actually changing the entire perception of strategy games as we knew it, since the state of the game is rapidly changing, involving a lot of new parameters to be calculated by the decision making engine. Among the pioneering RTS computer games we can find the "Dune TM" series by Virgin (1990 till 2001) and later the "Command & Conquer TM" series by Westwood and EA Studios (1995 up to these days).
Although the RTS game genre is a true evolution of the classic TBS game, we can discern that there is an intermediary matter in between and that is the modern TBS game. This type of strategy game still lives in the world of turn-based games, but yet offers many new features and abilities that a classic TBS game unable to implement. Among the pioneering modern TBS computer game we can find the "Civilization TM" series by Fraxis — Sid Meier (1991 up to these days) and "Heroes of Might and Magic TM" series by Ubisoft — New World Computing (1995 till 2007). Next we'll discuss some of the key features in those modern strategy games, including the map — an evolution of the classic board, evolvement of the "pawn" idea, hierarchical game objectives, diverse playing modes, missions, enhanced graphical representation and more.
1 (Strategies: Webster's Quotations, Facts and Phrases, 2006) — Page 416
2 (In Search of the Meaning of Senet, 1980)
3 (Andrew Rollings and Ernest Adams on Game Design, 2003) — Page 416
4 (Cooperative Strategy: Managing Alliances, Networks, and Joint Ventures (second edition), 2005) — Chapter 1
5 (Automata, Computability and Complexity: Theory and Applications , 2008) — Appendix N
6 (Artificial Intelligence: A Modern Approach (2nd Edition), 2002) — Chapter 6
Master's Thesis, 100 Pages
Diploma Thesis, 78 Pages
Master's Thesis, 116 Pages
Bachelor Thesis, 57 Pages
Scientific Essay, 29 Pages
Bachelor Thesis, 48 Pages
Diploma Thesis, 140 Pages
Diploma Thesis, 137 Pages
Internship Report, 16 Pages
Research paper, 26 Pages
Diploma Thesis, 99 Pages
Diploma Thesis, 129 Pages
Diploma Thesis, 96 Pages
Diploma Thesis, 103 Pages
Bachelor Thesis, 48 Pages
Diploma Thesis, 140 Pages
GRIN Publishing, located in Munich, Germany, has specialized since its foundation in 1998 in the publication of academic ebooks and books. The publishing website GRIN.com offer students, graduates and university professors the ideal platform for the presentation of scientific papers, such as research projects, theses, dissertations, and academic essays to a wide audience.
Free Publication of your term paper, essay, interpretation, bachelor's thesis, master's thesis, dissertation or textbook - upload now!