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?

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 Arimaa, 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.

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 Arimaa, 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.

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?

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?

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

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?

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.

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, then think about the actions that they imply.

Play with the Java applet at the bottom of this page for a bit; you'll see how it works.

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.

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, then think about the actions that they imply.

Play with the Java applet at the bottom of this page 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?

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

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

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.

I was asking if minimax can use only the results from one turn ahead.

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.

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.)

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.