• # Simple Board Game AI

Artificial Intelligence

Anyone new to the Artificial Intelligence field with an interest in gaming should attempt to create a simple board game program with an AI opponent. The best part about board games are the simple rules - this means less time implementing the game, more time on the AI. This essay will detail some of the techniques that you can apply to simple board games (this does not include chess, Go, Go-moku and the likes).

## Priority Board

A technique often used is something I call a priority board, an identically sized board that the AI agent uses to store values in. Each value corresponds to the place on the board; the higher the value, the more likely the agent will move there. For example, let us take the overly-simple game of tictactoe, for this board:

[x][ ][ ]
[ ][O][ ]
[x][O][ ]


With the computer playing X and X to move, the priority board could look something like:

[0][5][0]
[9][0][0]
[0][0][0]


The program would obviously move to (2,1) and win the game. Notice that if that opportunity wasn't their for the computer, then it would move to (1,2) and block the opponent from winning the game. Now, for a small board like tictactoe, a priority board is not necessary, but for larger games (like Pente, which is on a 19x19 board - 361 positions!) priority boards can be very useful to assess the large number of places. So, how do you assess the positions?

## Heuristics

Heuristics is basically a fancy name for rules, and it is these heuristics that will make or break the game. Firstly, you should narrow down your board game rules to a couple of heuristics that you can implement as code. For example, the rules of Pente dictate that you win if you place 5 pieces in a row, or get 5 captures. Therefore, some possible heuristics are as follows:

• Check for 4-pieces in a row
• Check for 3-pieces in a row
• Check for 2-pieces in a row
• Check for captures

Now, obviously, the first 3 can be reduced further, "Check for x-pieces in a row" which narrows our heuristic down to two! Thing is, so far we have only an offensive agent. In the worst case scenario, we'd want a purely defensive agent - purely offensive agents will be easily beaten! So, we will add an additional 2 heuristics to our program:

• Check for opponent potentially getting x-pieces in a row
• Check for opponent potentially making a capture

We now have 4 heuristics that can be applied to the game in both defensive and offensive styles. I have found the best place to proceed from here is by applying a two step evaluation. Firstly, you assign a number to the priority board place in your heuristic routine. For example, in our "Check x-pieces in a row" heuristic we could assign the number of pieces to the priority board. For example, given a simple Pente board:

[ ][ ][ ][ ][x]
[ ][ ][ ][x][ ]
[ ][ ][ ][ ][ ]
[ ][x][ ][ ][ ]
[ ][ ][ ][ ][ ]


Our initial priority board after the first heuristic would look something like this:

[1][2][2][2][0]
[1][1][1][0][2]
[1][1][3][1][2]
[1][0][1][2][1]
[3][1][1][1][1]


Note that the diagonal has the highest values since there are 3 pieces in the 5-line, therefore (3,3) and (5,1) get the highest values assigned to them. With experience, I've found it useful to multiply each heuristic by a certain bias. I've also found it useful to assign a slightly higher value to defensive heuristics (for example, I use a bias of 1.2 as opposed to 1.0 (which is no bias) in PenteAI).

Hopefully, you will find with the right heuristics and biases, you will get a certain amount of emergent behaviour - behaviour you had not planned, but comes from all the heuristics interacting with each other. For example, when I first ran my recent PenteAI program, I found the AI spaced out its moves. I had not planned this at all, indeed I wanted quite the opposite! After playing with this for a while, I realized it was an excellent way of limiting your opponents moves 3 or 4 moves ahead - and it is a technique that I myself have now adopted when playing the game!

## Beyond This...

For board games this simple, there aren't that many additional simple techniques. It all depends on your game and the complexity of the game itself. For more complex games, you start to look a certain number of moves ahead to keep in front of your opponent. You can also employ more advanced AI techniques to simple board games with some interesting results - genetic algorithms to evolve biases and weights (although this is time consuming) can generate a very formidable opponent. Using neural networks to recognize patterns in the players behaviour can also be very challenging for the player.

Report Article

## User Feedback

There are no comments to display.

## Create an account

Register a new account

• ### GameDev.net and Intel Contest

GameDev.net and Intel® have partnered up to bring GameDev.net members a gamedev contest running until December 21, 2018 - Submit your game for Intel® Certification and you could win big!

• 0
• 22
• 0
• 1
• 0

• 9
• 11
• 11
• 23
• 12
• ### Similar Content

• I'm writing a little game for visual deficient people, but I'm having a hard time getting the mouse position. Let me explain :
I need to know where in the table the mouse cursor is, without having a click, and then I want to play a sound. That sound would be different for every position. Any thoughts? Thanks, in advance!
e.g., when the mouse is on the 1st box would be played the audio "a1", when it's on the 2nd box, "a2", and so on.
I tried with:
mouse_x, mouse_y = get_Position() if mouse_x and mouse_y == map[x][y] then if map[x][y] == 0.1 then Audio:play() But it makes a loop and the sound keeps playing forever!
• By Alin N.
Hello there,

Let's say I am looking into designing a game similar to Guitar hero for mobile.
If a player plays niche songs from obscure bands, what is the best way to register his highscore on a global server?
I'm interested in resource efficiency and response times.

Thanks!

• Hi guys,
I've got a little problem which is irritating me as there must be a simple solution but Google isn't necessarily being my friend right now.
In my new game, I've got a set of projectiles for which I need to check for collisions with typically rectangular shapes (but which aren't axis aligned). My general approach is to create an axis aligned bounding box for both the projectile's movement and the target object. If there's a match on the broad phase, then I want to check whether the projectile collides with any of the edges of the collision and then report the first collision (i.e. if the projectile would have gone through multiple lines then I want to know the first collision so I can display the explosion animation in the right place).
I represent my shapes as a series of line segments (there's a future question about colliding with semi-circles and circles, but that's later). Can anyone 'refresh my memory' on being able to test for the interaction of line segments?
Thanks
Steve
• By congard
Hello! When I implemented SSR I encountered the problem of artifacts.
Screenshots here
Code:
#version 330 core uniform sampler2D normalMap; // in world space uniform sampler2D colorMap; uniform sampler2D reflectionStrengthMap; uniform sampler2D positionMap; // in world space uniform mat4 projection, view; uniform vec3 cameraPosition; in vec2 texCoord; layout (location = 0) out vec4 fragColor; void main() { mat4 vp = projection * view; vec3 position = texture(positionMap, texCoord).xyz; vec3 normal = texture(normalMap, texCoord).xyz; vec4 coords; vec3 viewDir = normalize(position - cameraPosition); vec3 reflected = reflect(viewDir, normal); float L = 0.5; vec3 newPos; for (int i = 0; i < 10; i++) { newPos = position + reflected * L; coords = vp * vec4(newPos, 1.0); coords.xy = 0.5 + 0.5 * coords.xy / coords.w; newPos = texture(positionMap, coords.xy).xyz; L = length(position - newPos); } float fresnel = 0.0 + 2.8 * pow(1 + dot(viewDir, normal), 4); L = clamp(L * 0.1, 0, 1); float error = (1 - L); vec3 color = texture(colorMap, coords.xy).xyz; fragColor = mix(texture(colorMap, texCoord), vec4(color, 1.0), texture(reflectionStrengthMap, texCoord).r); } I will be grateful for help!
×