Best AI approach for Game Draught (Chekers)

Question

Currently I am implementing a draught online game server in Eralang.(a mobile game). I am having a problem about the AI approach. (whether it will minmax approach ,genetic algorithm or any other). Also having a problem in defining a proper heuristic function. Basically what I need is an idea how to start an implementation while considering the language , the limited number of resources and server response time (TIME OUT) since this is a online mobile game.

Need some ideas about the algorithm and the heuristic function.

Answer 1

As my Artificial Intelligence professor was used to say: in game AI, the main difference in program performance is given by the details and not by the used algorithm. Algorithms used for this board games are usually 20-30 lines long, what makes an Artificial Intelligence engine strong or weak is the developer ability to reduce the search space through game details exploitation. This can be done effectively only with a good knowledge of the specific game.

Checkers has a medium search space (and in fact it has been already completely solved) but it is a good starting point to start with board game ai programming. For this reason I suggest you to start with a classical alpha-beta pruning algorithm.

But, as I previously said, choose the algorithm is just 10% of the work. Details are much more important, so let's look at them:

• Heuristic Function: This is a crucial point. An heuristic function must be: fast and easy to compute and describe well the value of a given state. Usually an heuristic function is just a weighted sum of a set of features. In this article you can find a simple heuristic function (plus a genetic way to tune it) that use features such as the number of pieces, the number of kings and the mobility value (the number of legal move for each player). Another hint: heuristic functions should return integer values: it is dumb to prefer a branch only for a 0.0003 difference, so it is better to round the heuristic to integer values.

• Exploiting Symmetry: If you can find a symmetry in the board position you must take it into account! In checkers there are not too much symmetry but I think you can still do something.

• Precompute: That's the way the checkers has been solved. :) But obviously you don't have to store everything. Chess AIs usually have a library of openings and a library of end game. These are precomputed actions (or rule-based actions) that allow your software to avoid a lot of computations in the starting and ending phase.

• Explore the relaxed (cheated) problem: This is an huge tips that greatly helps me. For instance you can assume that you can do two move in a row while your opponent does nothing. If you cannot reach a good position cheating, then you can not reach a good position in the normal game (with the opponent that tries to counter you) and you can simply discard that path.

This are just some little advice that I can give to you for this problem. I cannot be complete because it is a really big field but I hope you have got the point. You will find new and better ideas through experience. :)

For the time related question: AI engines that are time limited use an iterative deepening version of the alpha-beta pruning algorithm (in this article there are detailed information and further material). This approach has two main advantages: you can stop the computation at any time and you can use the previous iterations to improve the search heuristic in the next ones. Also if you have to restart the search several times, this definitely outperform the traditional alpha-beta pruning algorithm.

I hope you can find this useful.