Create AI for Your Own Board Game From Scratch — Preparation — Part 1
Based on my little project about a board game that I come up with, EvoPawness (Temporary Name)
Hello everyone! This is my second article in medium about Artificial Intelligence (AI). I want to share to everyone about how the progress of my little project that I do on my free time. It is a board game that I come up with. EvoPawness (Temporary Name) is inspired from a chess game. It is a simple game. However, my aim in this series of articles is not primary to tell step on how to develop, designing a game effectively. Instead, it will be focused on how to create an environment for the input of AI algorithm. I won’t use game engine such as Unity or Unreal Engine. But, I hope that my code can help you design your board game with powerful AI whether you use Game Engine or not.
NOTE: This part don’t use deep learning yet, but it will cover fundamental basic AI on how to create AI environment that is used for adversarial search. This part will be focused on designing the game’s class. If you only want to see Artificial Intelligence in action, skip this part.
I’m sorry that I can’t cover the Deep Learning part yet. I’m afraid It will make my article very long and not interesting to read. I want to share my knowledge step by step. So I’ll write it on the later part.
This article is targeted for the one who is interested in AI and designing a game. If you are not one of them, of course you can still see this article (who tells you that you cant 😆). I hope that my writing skill will increase by publishing this article and the content benefits you 😄.
Introduction
Who doesn’t love gaming? It is a activity that someone do to release boredom. Game is fun and can train our brain to think how to solve a problem, especially board games. Board game is a game of strategy played by moving pieces on the board. There are several board games such as checkers, chess, and monopoly that need two players or more to play. It requires a good strategy to beat your opponent. It takes time to formulate a good strategy on beating your opponent.
Nowadays, board game is played on the computer. It usually has an AI agent to let player practice the game. The AI has a strategy that will search the best move. Of course, the smarter the AI it is, the more enjoyment we feel on beating the AI. So, how about we make a powerful AI on our game that learn the good strategy itself. It will make the AI powerful enough to make the human enjoy the game or make him/her frustrated 😆. It has a nice feeling if your AI creation on your own game idea is enjoyed by people.
This article will be focused on how I create my own original board game idea the EvoPawness (Temporary Name). I haven’t checked whether my game is already exists or not. I think it hasn’t. The code will be focused on designing the basic class for the game ready to be an input of AI algorithm. Because I like Python, I will write it in Python language. Of course you can write it in your preferred game engine. If you want to implement it, you should understand on the flow on how to create the game described in this article. The environment is based on Peter Norvig’s Artificial Intelligence book.
Let’s go, let’s create the game!
Outline
This article will be written in the following order:
- Technology
- Game’s Description and Rule
- Term Definition
- Our pipeline or steps
- Define our game
- Implementation
- Conclusion
- Afterwords
Technology
In the project of this article, we will be using these:
- Python 3.6.5
- PyCharm IDE or preferred text editor such as Atom or Sublime (Optional).
No other library is needed at the moment. Later, in the upcoming article, we will use TensorFlow (or maybe PyTorch) to develop AI agent.
Game Description and Rule
EvoPawness (Temporary Name) is a board game that I come up with. It’s a turn based game that is played by two players. The board has 9 x 9 tiles. Each players has 6 pawns on his/her side with different color (Black and White). Every players has 5 soldier pawns chess and 1 king. The objective of this game is to destroy the opponent’s king or all of enemy’s pawns.
Every pawn has attributes called HP (Health Point), ATK (Attack Point) and step. The HP indicates their ability to function or alive. ATK is an attributes to reduce the enemy by the set amount of ATK point. Step point indicates how many step can a pawn move based on their unique movement. There is also a pawn status which tell whether the pawn has been activated or not. If it’s not activated, it cannot move, attack, or evolve.
The soldier pawn can evolve into higher rank pawn. Soldier pawn can evolve into knight, rook, and bishop. Knight and Bishop can evolve into Queen. They will have different abilities. Here are the ability of each pawns:
Soldier
Movement : Soldier can only move forward. The number of steps depend on step point. Can bypass opponent’s pawn.
HP, ATK, STEP : Default 3, 1, 1
Attack target and range : Same like the movement It can only attack forward depend on step point. The pawn won’t move from the original position.
Evolve : Can evolve into Knight, Rook, and Bishop
Note : Can move, evolve, and attack if the pawn has been activated
Knight
Movement : L shaped in every direction (like in chess version). The number of steps is fixed to 1 (ignore step points). Can bypass opponent’s pawn
HP, ATK, STEP : Point attributes (if HP, it will be current HP not the max HP) before evolving into knight is added with these points (0,4,0)
Attack target and range : Same like the movement. The pawn won’t move from the original position.
Evolve : Cannot evolve
Rook
Movement : can move forward, backward, left, right (like in chess). The number of steps is based on the step points. Can bypass opponent’s pawn
HP, ATK, STEP : Point attributes (if HP, it will be current HP not the max HP) before evolving into knight is added with these points (2,2,0)
Attack target and range : Same like the movement. The pawn won’t move from the original position.
Evolve : Evolve into Queen
Bishop
Movement : Diagonal move in every direction (like in chess). The number of steps is based on the step points. Can bypass opponent’s pawn
HP, ATK, STEP : Point attributes (if HP, it will be current HP not the max HP) before evolving into knight is added with these points (2,1,1)
Attack target and range : Same like the movement. The pawn won’t move from the original position.
Evolve : Evolve into Queen
Queen
Movement : Diagonal move in every direction and can move forward, backward, left and right (like in chess). The number of steps is based on the step points. Can bypass opponent’s pawn
HP, ATK, STEP : Point attributes before (if HP, it will be current HP not the max HP) evolving into knight is added with these points (2,2,0)
Attack range : Same like the movement. The pawn won’t move from the original position.
Evolve : Cannot move
King
Movement : Cannot move
HP, ATK, STEP : Default (15,4,1)
Attack range and target: Attack like Queen with one range. The pawn won’t move from the original position.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Every players has a special power which requires “mana” to do it. “mana” is generated each turn by one (max 10). In the first turn, they will have 5 manas. It will be generated each turn by one. Here are the special power:
- Activate a soldier pawn : Need 3 manas
- Evolve a soldier pawn : Need 5 manas
- Evolve a rook and bishop : Need 10 manas
And last, there is two ‘runes’ that spawn each one randomly. It will spawn randomly near each player’s zone. If the rune is approached by a pawn. The pawn can gain a bonus on one of their attributes (random). The bonuses are:
- Increase HP by 2
- Increase Step by 1
- Increase ATK by 2
The rune can spawn on a pawn’s location. If it spawns on the pawn’s location, it will gain the bonus immediately. This rule will make the game non-deterministic. If we use algorithm that needs the game to be deterministic game, we will change this rule.
Each players can only choose one action every turn. They must choose to move the pawn or activate special power. If there are no action that can be done. The player must skip the turn.
Black Player will always move first. So in the first turn, it’s Black Player’s turn followed by White Player’s turn. They will take turn alternatively.
These rules can change depending on the AI algorithm that we use on the next part. I will tell you later if we need to change a particular part. I haven’t tested the game balance yet. So, don’t expect that the game will be balance. There might be a strategy that is overpowered (OP). We won’t discuss about the balance of the game. But if you think that this game is really unbalance, just tell me. I will change the game’s rule according to your statement.
That’s all of the rule of EvoPawness (Temporary Name). If you are wondering about the name, The “(Temporary Name)” is also the part of the name. I haven’t decided on the name of the game so it will be the temporary name.
Term Definition
Initial State
Specifies how the game is set up at the start.
Actions. input = (state)
Return a set of legal moves in a state
Result Function. input = (state,action)
A transition model, which will define the result of an action given a state.
Terminal Test. input = (state)
Check the terminal status of the game. Return true if the game has ended, false otherwise
Utility Function. input = (state, player)
Defines the final numeric value for a game when it’s in the terminal state for a player. The numeric value formula is defined by us.
Evaluation Function. input = (state, player)
Defines an estimate of the expected utility numeric value from a given state for a player. This function is called when the game hasn’t ended.
Our pipeline or steps
Here’s our steps:
We have stated the description and rule of the game. We still need to define the game’s state, initial state, players, possible actions, result functions, terminal test, utility function, and evaluation function. Then we need to define our game’s elements or objects. Then we design the class diagram and implement it. Oh, I’ve skipped the action function. We will define it after initial state.
In this article, we will skip the utility function and evaluation function. We will define them in the next article.
Define Our Game
In this section, we will define all the elements of the game that we must define. As written above, It’s based on Peter Norvig’s book. So let’s follow it:
State Representation
We should define how we will represent the game’s state. Before we do that, we should decide what information should we save in the state. In this game, there are:
Format : Game’s object (attributes)
- Turn Counter
- Players (mana, color)
- Pawns (hp, atk, position, active status, color player, step, dead)
- Kings (hp, atk, position, color player, step, dead)
- Runes (bonuses, position)
Okay, I think that’s all. Let’s think on how to represent them.
We will need a 2D list or array of pawns to keep the coordinate’s pawn and king’s position information of the game. It can make us easier to check the position of pawn. So we will write the position of our Pawns and Kings into a 2D list or array of pawns and kings.
We also need a list of players, pawns, runes and kings to keep track on each objects. It’s exhausting to loop our 2D array only to check the position of each objects.
Finally there is a turn counter. It will help us to decide which turn it is now. If the counter is divisible by 2, it’s white player turn, black player otherwise.
There might be a better representation than this. But I think this will be enough to represent our game.
Initial State (state)
Here is our initial state based on how we represent our state:
Where the List of pawns is the same with our 2D array board of pawns. All of the pawn status is inactive (status boolean is false)
Players (Function (state) -> player_index)
There are two players, white player and black player. The player’s turn is decided by:
If turn is even number, it’s white player turn. But if turn is odd number, it’s black player turn.
Actions (Function (state) -> list of action)
There are the action that can be done with each actors:
Players
If a player has 5 manas , he/she can evolve a soldier pawn into higher pawn (except queen and knight).
If a player has 3 manas, he/she can activate a soldier pawn.
If a player has 10 manas, he/she can evolve a rook or bishop pawn into queen.
Pawns
If possible, the pawns can move into the direction based on the type of pawns.
If the enemy pawns is in the range of attack, the pawns can attack the enemy’s pawn.
Kings
If the enemy pawns is in the range of attack, the ally’s king can attack the enemy’s pawn.
Pass
If there are no actions available, pass the turn.
All of the possible action will be appended into a list that will be returned by the function.
Result Functions ( Function (state, action) -> new state)
There are the results of our action
There are 3 actors that we must see:
- Players
Player can evolve pawn by the cost of manas. It will change the pawn into higher type pawn. It will add the attributes
Player can activate pawn with the cost of manas. It will change status of pawn to active.
- Pawns
Pawns can move based on the type. It will change the pawn’s position in our board array. If the pawn hit a rune, it will increase its attribute randomly (only one).
Pawns can attack the opponents pawn by reducing the HP based on the ATK point of the attacker.
- Kings
Pawns can attack the opponents pawn by reducing the HP based on the ATK point of the attacker
- Pass
Pass the turn.
After doing one of the above action, the turn is increased by one. If the turn is divisible by 5, it will spawn 2 random runes.
Terminal Test (Function (state) -> boolean true or false)
It checks whether the game end or not.
We will check each king’s dead attribute. If it’s true, then the function will return true. If not, we will check each player’s pawns.
If a player doesn’t have alive pawn, the function will return true, false otherwise.
Utility and Evaluation Function (Function (state, player) -> integer)
We won’t formulate our evaluation or utility function here. It’s not needed in the current article.
Implementation
Before we code, we need to design our class to make our code become more structured. We will need to design the relationship. We will do it in Model View Controller (MVC) Design Pattern.
All type of pawns will inherit Pawn abstract class. The state will have Rune, Player, and Pawn class. These are our model. The element that we’ve defined is in the game controller.
That’s it, the state will contains Runes, Players, and Pawns. Game Controller will be a bridge between View and State. The controller will generate all of our defined elements above. The State is our model that will be processed by GameController class.
The source code will be uploaded into my GitHub repository. We won’t discuss all of the code here. We will discuss on how to code based on our defined elements.
State Representation
Here are the example on how I code the state:
It has all of the attributes that we have defined above.
Initial State
Here’s the example how to define the initial state
Players
Here’s the code to decide whose player is taking the turn.
class State:
def get_player_turn(self):
return self.turn % 2class GameController:
def player(self, state):
return state.get_player_turn()
Action
Here’s the code to decide the possible action. I will show you the example on how to generate possible action.
It will return the player’s possible action. There are also the code of pawn’s possible action. But, I won’t show it here because it’s very long. The possible action will be returned via dict format where it contains pawn’s information and the player’s information. It will contain all the information about the action.
Here’s an example of using the possible action. It’s one of the player possible action (remember, player has two possible actions, promote and activate) :
'p1a4’: {‘action’: ‘activate’,
‘pawn_atk’: 1,
‘pawn_hp’: 3,
‘pawn_index’: 4,
‘pawn_step’: 1,
‘pawn_x’: 8,
‘pawn_y’: 1,
‘player_index’: 1}}where ‘p1a4’ is an unique key to give identification to an unique action.
The controller will call that function.
class GameController:
def get_possible_action(self,state):
all_possible_action = self.combine_action(self.state.get_possible_action() + self.state._get_possible_action_pawn() + self.state._get_possible_action_king())
if len(all_possible_action.keys()) == 0:
return [{'action': {'skip' : {'action': 'skip'}}}]
return all_possible_actionResult Functions
Here’s the example of the result function
It will receive action input and the current state. For example, we want to activate a pawn of index 1, the function will receive this input:
{‘action’: ‘activate’,
‘pawn_atk’: 1,
‘pawn_hp’: 3,
‘pawn_index’: 4,
‘pawn_step’: 1,
‘pawn_x’: 8,
‘pawn_y’: 1,
‘player_index’: 1}It will activate a pawn and return the new state. Be careful, we must be sure to copy our state first to avoid object reference (using deepcopy library).
The function will response to the method called by our controller.
Terminal Functions
Here’s the example how to check if the game has ended or not
The function will check the dead status of pawn and the king. It doesn’t tell us who the winner is. It will only check the terminal status of the game.
Test the game
I haven’t created the GUI version yet. Currently, We can only play in the terminal or command prompt. It’s not comfortable to play in the terminal. Here’s the screenshot of how I play the game:
The state, possible actions will be the input of our view.
The code of our view will be placed in the GitHub repository.
Conclusion
We have created a new game from scratch. We’ve defined some of the elements ready to be an input for AI algorithm. We have defined the representation of the state, initial state, players function, result function, and terminal functions and write it with Python Programming Language.
I haven’t tested if the code works perfectly though. So, If anyone find bug, you can send notes here.
Afterwords
Thank you for reading my second article about Artificial Intelligence. I need some constructive feedback to make me better on writing and Artificial Intelligence. Go easy on me please 😆!
I just want to share my knowledge to the reader. It’s good to share knowledge as it can be helpful to someone in needs. I’m in the process of learning this field and want to share what I’ve learnt. It’s nice if someone tell me if there’s something wrong with this article.
The GitHub repository will be created tomorrow. I need to document the function first.
EDIT: Here’s the GitHub link
I hope that the GUI will be finished in the next article. It’s really uncomfortable to play in the terminal. If anyone want to contribute to create the GUI, I appreciate it 😃.
Forgive me for my inefficient code, I’ve tried to make the code readable, high cohesion and low coupling as possible. So any feedback is welcomed to fix the mess of my code.
If you want another article from me like this one, please clap this article 👏 👏p. It will boost my spirit to write my next article. I promise to make a better article about AI .
In the next article I will share a traditional algorithm about adversarial search. After that, we will move into creating the agent with Deep Neural Network.
See you on the next article!
Series of Articles
Part 1 : Create AI for Your Own Board Game From Scratch — Preparation — Part 1
Part 2 : Create AI for Your Own Board Game From Scratch — Minimax — Part 2
Part 3 : Create AI for your Own Board Game From Scratch — AlphaZero-Part 3
Sources
Russell, Stuart J., and Peter Norvig. Artificial Intelligence: a Modern Approach. Prentice-Hall, 2010.
