博弈树

蓝冰大侠

中秋在家,和闺女下棋,连续输棋,遂决定作弊,写个程序求下最优解.

棋是立体的一字棋,七列,六行,交替落子,每个棋子可以选择任一列放置,自动落到本列最低的空位上.

只要某一方的四个棋子连成横竖斜一条直线,即胜.

1.使用二维数组记录棋盘状态$board,使用R/G记录棋手$oper
2.function process($board, $oper, $path)  计算此状态下,指定棋手的最优结果
3.function judge($board, $oper, $x, $y) 判断指定棋手如果落子在(x,y)处,是否获胜


细节略,都是数据结构上的内容.

去处过程中,进行了剪枝.

原计算规模:  共42个棋子,每次落子可以选择七列中的任一列(只要未满),  也就是说:计算规模等同于7的42次方.

写完程序,运行了十几分钟,发现,计算规模过大,算法不现实.

打算有时间进行A*优化.