views:

269

answers:

1

I read about Gomoku that it can be implemented using Minimax and Alpha-Beta Pruning algorithms. So, i read these algorithms and now understand how the game will be solved. But when i sat to down to code, I am facing problem how to approach it.

As in ,

  • How to design the prototype functions like getNextMove or Max(Move) ?
  • How will the next move searched?
  • Till when should i apply the minimax algorithm.
  • I know i can find the code online, but i want to do it myself.

Can anyone please point me in the right direction?

+1  A: 

the minimax algorithm presented in the textbook is usually applied on simple games, e.g. tic-tac-tou, where the final states are reachable within only several turns between min player and max player. However, for Gomoku, it is impossible to reach all final states. Why do we need to reach final states? We need an evaluation for a move, i.e. whether a move is good or not.

So your first step is to design an evaluation function of a move, which tells you how much value you will properly gain if you do one move. e.g. you have a 3 in a row, the move along that row to make a 4 will be very valuable.

Suppose that you have a very clever evaluation function, then you can find an optimal move each time without any search. So before you do any min-max, alpha-beta, you'd probably design a good evaluation function. A good example is Emacs' gomoku source code, which has a good AI player without using any search.

Next you move to min-max and alpha-beta.

It seems that I didn't answer your questions. Actually I don't need. I assume that you know the details of min-max or even alpha-beta search for tic-tac-tao. By designing the evaluation function, you will have a better understanding of gomoku and you design search algorithm for it just as you can do for tic-tac-tou now.

Yin Zhu