3

I'm actually working on a board game which is a variant of the TIC-TAC-TOE game. The specifics of the game are the followings :

1. The game is played on a nxn board, with n variable.

2. A player wins if he succeeds in placing k alignments the first, k is variable.

3. An alignment is constituted of l marks (X or O) in a horizontal, vertical or diagonal. l is fixed.

4. If the nxn grid is full (no player can add a mark either X or O) and no player succeeded in placing k alignments so the game is drawn.

I'm using an minmax with alpha-beta prunning algorithm. This is my first program with artificial intelligence and I don't know exactly how to create the evaluation function to be used by the algorithm. I saw some examples on the net which use a material weighting to evaluate a position but I can't apply that in my case. Actually, I'm using a radom evaluation function which returns a value between -100 and 100.

    float Conf_eval(Configuration c)
       {
         return (rand()%201)-100;
       }

Any idea on how can I evaluate a given board configuration ?

4

1 回答 1

1

这在《人工智能 - 一种现代方法》一书中进行了深入讨论

基于本书系列，还有一些优秀的实现（这是java，还有python ，你可以谷歌更多）。包括井字游戏（和 alpha-beta 修剪剂）。

如果您使用带有alpha-beta 修剪的min-max 算法，除了启发式函数之外，您还可以使用排序的“Actions”列表来执行更好的操作（一个简单的实用程序函数会将 1 分配给胜利，0 分配给平局和 -1 损失 - 这些都是最小-最大扩展树的叶节点）。

例如，要对动作进行排序，您可以选择将符号（X，O）添加到通向胜利路径的动作。这最终应该会导致更好的修剪。

于 2014-01-01T19:30:08.387 回答