In software development there are many goals that we aim for in designing our software, some of which compete against each other. Two such goals are flexibility and speed. While they may not always be in competition, I’ve found in the past that they quite often are, and particularly so when it comes to game development. What exactly do I mean by these two terms? Flexibility can mean anything from allowing multiple development languages to cross-platform support. When I talk about speed I’m talking about actual run-time performance of your application. Today I’m going to speak specifically about my time adding both GameMonkey (GM) for scripting support and minimax for AI.

The Mini-Game

As part of a mini-game for CIC I wanted players to be able to play a chess-like game allowing one of the 4 or 5 players per ship to conduct ‘Electronic Warfare’ against other ships they were battling with. I needed to do a lot of prototyping of the game rules testing different types of units, different board sizes etc. For the greatest flexibility in prototyping I decided to implement the entire game logic in script files allowing rule changes on the fly. After investigating the different options for scripting languages, I chose to go with GM Script. It also gave me the added benefit of trying out GM Script on a small sized project to help decide if I should use it for the high-level AI in the rest of CIC.

During the creation of the board game engine I first created chess and checkers, using script files only, to make sure I had enough features for a full chess-like game. I then created a separate script file with the rules and unit types for my ‘Electronic Warfare’ game. It shows just how flexible scripting languages can be, with a simple change in script file completely changing the game.

Game Monkey Script

GM Script is “a simple, small, game / application extension language for C++ coders”. It’s similar to Lua, but designed with C/C++ game programmers in mind. Using a C style language it allows script (.gm) files to be loaded and executed at run-time. The script files allow many useful features from configurable variables to complex functions. I found it easy to use, simple to integrate with my own code, and generally a great benefit to the project. I highly recommend anyone to check out GM script for any scripting solutions they need in the future, and feel free to contact me for any more detailed info or questions.

MiniMax (with alpha-beta pruning)

Thinking back to my AI subjects at university I remembered that minimax tree traversal was one of the best forms of AI for chess-like games. After some investigation I decided I’d implement minimax for my chess game, and after a few hours of coding had simplistic tree generation and traversal implemented. The basic concept of minimax tree traversal requires you to generate a tree of possible moves from the current board layout (and all moves from each of those moves etc). Each set of moves is a new level in the tree, and the children for each node are all the possible moves from that board configuration. The number of nodes in the tree quickly blows out with only looking ahead a small number of moves (currently I look forward 3 or 4 moves). To allow looking forward this far I needed the game to run a lot faster. I added my own memory pool, I compressed my board and unit class sizes as far as I could and ran AMD’s optimizer (CodeAnalyst) over my game to find any bottlenecks. After squeezing as much performance as I could out of the code I ended up running into a brick wall, I couldn’t have both the flexibility of a scripting language and still have the speed to run the minimax algorithm properly.

Script vs. AI

As a lot of the core gameplay was implemented as functions within GM script, every time I called them I had a major run-time hit which wasn’t a problem during regular play, but when generating thousands of possible moves it soon grinds to a halt. Don’t get me wrong, I’m not saying you shouldn’t use scripting in your games; it’s just that you have to choose where you use it wisely. One area of the GM script that allows your app to still have excellent run-time performance is configuration variables. By loading all of the definitions in at once (at load time) and storing them in regular C++ structs/class you can then access them at full speed while still having the flexibility of originally loading them in from script. There is no native support for binding GM config files to C++ struct/classes however it’s a simple task to create this yourself. Using configuration variables I’ve managed to get around the problem for now, however it means I can’t have any of the extra features (like special moves such as castling in chess) working with the AI.

The main performance problem will occur if you use script in a time critical part of the game loop. Scripting languages when compiled to non-native byte code will be 10-100 times slower than native code.

Conclusion

So in summary, GM script could be a great addition to your game, in moderation, and minimax is an excellent algorithm to use in any chess-like game. Minimax has fairly limited uses outside of that scope, however it was fun to implement and only took a few hours to get up and running, with a few extra hours optimizing it. I now have the fun task of making the AI smarter through the ‘score’ it gives to a particular board configuration, the better the algorithm, the smarter the AI will be. Once I’m happy with the AI I’ll look to start integrating it within CIC and see how it plays with the rest of the game. Then it’s on to implementing all of the fancy features I’ve come up with over the past few months of design. I’d like to thank Shauno for working on the art for my ‘Electronic Warfare’ game, it goes to show again just how much better a game looks when a real artist has spent even a few hours on it.