# How to make more difficult AI for a board game

## Recommended Posts

Plusekwal    102
I'm making a board game and have reached to the point where I need to program the AI. And I did it - it was easier and took less time than I have expected. The problem is that the AI is trivial and too easy to beat - I tried to do everything I could think of, algorithms work as expected, but it's still quite easy.
The rules of the board game are rather simple: there is only one type of unit or piece or pawn or whatever. Pieces can only move to the 4 neighbour squares and can also create other pieces under certain conditions. Players take turns to move 3 times any of their pieces(i.e. 3 pieces once, or one piece three times or 1 piece once and another one twice)

The AI first compares the number of its pieces against the total number of all other pieces. Then, depending on the ratio, it uses four different algorithms to react to the situation. These algorithms include checks for undefended enemy pieces, creation of new pieces, defending of its own pieces, etc. I can post the exact algorithm if necessery.

So how do I make the AI more difficult?

##### Share on other sites
alvaro    21246
Maybe you should tell us a little more about your game: How big is the board? How many pieces does a player typically have? What are the winning conditions? The type of games that allow multiple moves per player are often hard for computers (see [url="http://en.wikipedia.org/wiki/Arimaa"]Arimaa[/url], whose move mechanics are similar to yours).

There are roughly speaking four approaches to making board-game AI implementations (I am improvising here, so don't be surprised if I missed something):
* A set of hand-crafted rules: It's what you have now and it can be made fun for some games, but it typically results in brittle AI that makes stupid moves in many situations.
* Minimax: It worked great for games like chess and checkers.
* MCTS (Monte Carlo Tree Search): It's all the rage in computer go these days, and it can even be used for non-deterministic games and games with more than two players!
* ML (Machine Learning): It has worked well for some games like backgammon, but it might require learning a lot about a difficult field, and it's unclear how generally applicable it is.

If you can write a decent evaluation function for your game (a function that takes a position and returns a number that gives you an idea of who's ahead), try minimax. If this is not possible, you might be able to use MCTS instead. Neither of these things is very easy to learn, but there is a lot of good info on the web about them.

##### Share on other sites
Plusekwal    102
[quote name='alvaro' timestamp='1310648668' post='4835232']
Maybe you should tell us a little more about your game: How big is the board? How many pieces does a player typically have? What are the winning conditions? The type of games that allow multiple moves per player are often hard for computers (see [url="http://en.wikipedia.org/wiki/Arimaa"]Arimaa[/url], whose move mechanics are similar to yours).

There are roughly speaking four approaches to making board-game AI implementations (I am improvising here, so don't be surprised if I missed something):
* A set of hand-crafted rules: It's what you have now and it can be made fun for some games, but it typically results in brittle AI that makes stupid moves in many situations.
* Minimax: It worked great for games like chess and checkers.
* MCTS (Monte Carlo Tree Search): It's all the rage in computer go these days, and it can even be used for non-deterministic games and games with more than two players!
* ML (Machine Learning): It has worked well for some games like backgammon, but it might require learning a lot about a difficult field, and it's unclear how generally applicable it is.

If you can write a decent evaluation function for your game (a function that takes a position and returns a number that gives you an idea of who's ahead), try minimax. If this is not possible, you might be able to use MCTS instead. Neither of these things is very easy to learn, but there is a lot of good info on the web about them.
[/quote]
1. The board is 9*6 squares big.
2. All players start with 1 piece and can hardly have more than 15 to 18, simply because the board is not big enough. I'd say a typical number of pieces in midgame is 10.
3. A player wins when there are no more enemy pieces on the board.
Anyway, I got a question about the minimax formula: is it a good idea to based on the consequences from the AI's moves only?

##### Share on other sites
alvaro    21246
[quote name='Plusekwal' timestamp='1310809089' post='4835934']
Anyway, I got a question about the minimax formula: is it a good idea to based on the consequences from the AI's moves only?
[/quote]

I'm sorry, but I don't understand your question. I can't even parse it.

##### Share on other sites
[quote name='Plusekwal' timestamp='1310809089' post='4835934']
Anyway, I got a question about the minimax formula: is it a good idea to based on the consequences from the AI's moves only?
[/quote]
Minmax, by definition, needs to iterate through the potential game spaces. Since the other player is likely changing the game state along the way, you pretty much can't derive a realistic result from Minmax unless you are taking the other player's moves into account.

##### Share on other sites
Emergent    982
It sounds like you just don't understand the idea of minimax yet.

Just think of it as propagating numbers up a tree to begin with. They start at the leaf nodes, and work their way to the top. Once you have all the numbers, [i]then[/i] think about the actions that they imply.

Play with the Java applet at the bottom of [url="http://www.ocf.berkeley.edu/%7Eyosenl/extras/alphabeta/alphabeta.html"]this page[/url] for a bit; you'll see how it works.

##### Share on other sites
Plusekwal    102
[quote]
I'm sorry, but I don't understand your question. I can't even parse it.[/quote] I was asking if minimax can use only the results from one turn ahead.
[quote] It sounds like you just don't understand the idea of minimax yet.

Just think of it as propagating numbers up a tree to begin with. They start at the leaf nodes, and work their way to the top. Once you have all the numbers, [i]then[/i] think about the actions that they imply.

Play with the Java applet at the bottom of [url="http://www.ocf.berkeley.edu/%7Eyosenl/extras/alphabeta/alphabeta.html"]this page[/url] for a bit; you'll see how it works. [/quote]
[quote name='Plusekwal' timestamp='1310809089' post='4835934']
Anyway, I got a question about the minimax formula: is it a good idea to based on the consequences from the AI's moves only?
[/quote]
Minmax, by definition, needs to iterate through the potential game spaces. Since the other player is likely changing the game state along the way, you pretty much can't derive a realistic result from Minmax unless you are taking the other player's moves into account.
[/quote]
Analysing the potential moves by even only one turn after the AI will take way too much computing time. It looks like I'll have to use MCTS

##### Share on other sites
[quote name='Plusekwal' timestamp='1310884380' post='4836264']
Analysing the potential moves by even only one turn after the AI will take way too much computing time. It looks like I'll have to use MCTS
[/quote]

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.

##### Share on other sites
Emergent    982
[quote name='Plusekwal' timestamp='1310884380' post='4836264']
I was asking if minimax can use only the results from one turn ahead.
[/quote]

Oh, ok, gotcha.

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.
[/quote]

I'm not sure about that. The board is small, but each turn is 3 moves long. Naively, he'd have to search 6 plys just to see a full turn ahead -- not so much "min-max" as "min-min-min-max-max-max." Naively, this gives a min-max branching factor of (4*10)^3 , which is huge.* So it's not trivial.

That said, many of these turn sequences result, after 3 moves, in identical gamestates, so I don't think the "true" branching factor needs to be so high. It could be kept down e.g. by hashing visited states, or perhaps by thinking carefully about what states are reachable.

*(I'm assuming 10 pieces, each of which can move in one of 4 directions.)

##### Share on other sites
ApochPiQ    22999
I don't see how the search space is any more complex than, say, chess.

Per piece, you compute a list of potentially reachable spaces on the board (do I move this guy 1, 2, or 3 times?). Then you prune conflicts (i.e. two pieces land on the same square). Then you prune the number of valid combinations using a simple allowance metric (i.e. only 3 moves are allowed per turn). This gives you a finite, bounded set of moves which is not substantially larger than the set of potential moves in an average chess game, if my napkin mathematics does not betray me.

##### Share on other sites
alvaro    21246
The enormous branching factor that results from compound moves is a serious obstacle to the success of minimax in certain games, as I mentioned in my first response. So MCTS seems promising. You can consider each separate piece moving as a proper move, since MCTS doesn't require turns to alternate, the way minimax does. If the nature of the game is such that random moves will progress towards the end of the game, you might be able to set something up without too much effort. If not, you either need to implement a biased playout policy that will make progress towards the end of the game, or you may have to combine an evaluation function with MCTS, so after a few moves from each side you'll use the evaluation function as reward.

Please, let us know if you are making any progress. Also, it would be cool if you could post a full description of the rules.

##### Share on other sites
Emergent    982
[quote name='ApochPiQ' timestamp='1310950886' post='4836567']
Per piece, you compute a list of potentially reachable spaces on the board (do I move this guy 1, 2, or 3 times?). Then you prune conflicts (i.e. two pieces land on the same square). Then you prune the number of valid combinations using a simple allowance metric (i.e. only 3 moves are allowed per turn). This gives you a finite, bounded set of moves which is not substantially larger than the set of potential moves in an average chess game, if my napkin mathematics does not betray me.
[/quote]

Yeah, that was my thought too, and it might work, but there are some situations that confuse me. E.g.,
[code]
XXXX XXXX XXXX XXXX
XX X XX X XX X XX1X
X 2X -> X2 X -> X21X -> X2 X
XX1X XX1X XX X XX X
XXXX XXXX XXXX XXXX
[/code]

(1, 2, and X denote pieces; spaces denote empty space; this is a three-move sequence where the order of 1 and 2's moves matter.)

[Aside: The code tags do weird things, adding and removing spaces; getting ASCII art to look right is a pain...]

I'm not saying that there isn't an efficient way to resolve this so that you keep the attractive properties of just considering what squares are reachable (in which case you just get something like 3k moves), but how to do it doesn't jump out at me.

##### Share on other sites
Plusekwal    102
[quote name='Plusekwal' timestamp='1310884380' post='4836264']
Analysing the potential moves by even only one turn after the AI will take way too much computing time. It looks like I'll have to use MCTS
[/quote]

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.
[/quote]
Well, three moves per turn can have many possiblities and as far as I understood from that website, minimax needs at least three to four turns to compute. Also, there's some pretty complicated math involved when creating new pieces.

[quote name='Emergent' timestamp='1310950298' post='4836559']
[quote name='Plusekwal' timestamp='1310884380' post='4836264']
I was asking if minimax can use only the results from one turn ahead.
[/quote]

Oh, ok, gotcha.

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.
[/quote]

I'm not sure about that. The board is small, but each turn is 3 moves long. Naively, he'd have to search 6 plys just to see a full turn ahead -- not so much "min-max" as "min-min-min-max-max-max." Naively, this gives a min-max branching factor of (4*10)^3 , which is huge.* So it's not trivial.

That said, many of these turn sequences result, after 3 moves, in identical gamestates, so I don't think the "true" branching factor needs to be so high. It could be kept down e.g. by hashing visited states, or perhaps by thinking carefully about what states are reachable.

*(I'm assuming 10 pieces, each of which can move in one of 4 directions.)
[/quote]
I was actually considering maximum three moves per piece to be considered - one for eliminating maximum number of enemy pieces, one for colouring(see below) and one for escaping/defending own pieces.

[quote name='alvaro' timestamp='1310954897' post='4836596']
The enormous branching factor that results from compound moves is a serious obstacle to the success of minimax in certain games, as I mentioned in my first response. So MCTS seems promising. You can consider each separate piece moving as a proper move, since MCTS doesn't require turns to alternate, the way minimax does. If the nature of the game is such that random moves will progress towards the end of the game, you might be able to set something up without too much effort. If not, you either need to implement a biased playout policy that will make progress towards the end of the game, or you may have to combine an evaluation function with MCTS, so after a few moves from each side you'll use the evaluation function as reward.

Please, let us know if you are making any progress. Also, it would be cool if you could post a full description of the rules.
[/quote]
I'm still wondering if switching to MTCS will be worth it. I dont know if MCTS will be applieble to this game. Also, computing time might not be that big after all. As for the rules:
-the board is 9x6 squares big
-the game ends when there are pieces of only one player left
-every player starts with one piece only
-one piece can do five actions - moving in the four directions and colouring the square which it is currently on in the colour of the player
-upon colouring if the new coloured square makes a row, a column or a diagonal of three colourd squares in the colour of the player, new pieces are spawned at the empty places

[quote name='Emergent' timestamp='1310955092' post='4836600']
[quote name='ApochPiQ' timestamp='1310950886' post='4836567']
Per piece, you compute a list of potentially reachable spaces on the board (do I move this guy 1, 2, or 3 times?). Then you prune conflicts (i.e. two pieces land on the same square). Then you prune the number of valid combinations using a simple allowance metric (i.e. only 3 moves are allowed per turn). This gives you a finite, bounded set of moves which is not substantially larger than the set of potential moves in an average chess game, if my napkin mathematics does not betray me.
[/quote]

Yeah, that was my thought too, and it might work, but there are some situations that confuse me. E.g.,
[code]
XXXX XXXX XXXX XXXX
XX X XX X XX X XX1X
X 2X -> X2 X -> X21X -> X2 X
XX1X XX1X XX X XX X
XXXX XXXX XXXX XXXX
[/code]

(1, 2, and X denote pieces; spaces denote empty space; this is a three-move sequence where the order of 1 and 2's moves matter.)

[Aside: The code tags do weird things, adding and removing spaces; getting ASCII art to look right is a pain...]

I'm not saying that there isn't an efficient way to resolve this so that you keep the attractive properties of just considering what squares are reachable (in which case you just get something like 3k moves), but how to do it doesn't jump out at me.
[/quote]As for this situation, piece 2 can move upwards an piece 1 upwards and then leftwards - there is no difference. Besides, due to the nature of the game the board will never get that crowded.

##### Share on other sites
alvaro    21246
How do you lose pieces? Also, after a new piece is spawned, the coloring of the squares involved goes away?

##### Share on other sites
Plusekwal    102
[quote name='alvaro' timestamp='1311010800' post='4836898']
How do you lose pieces? Also, after a new piece is spawned, the coloring of the squares involved goes away?
[/quote]

You just move onto enemy pieces to destroy them. And the colour doesnt go away, so this is a kind of limit for the number of possible pieces. However, the enemy player can always change the squares in your colour into his colour.