中秋在家,和闺女下棋,连续输棋,遂决定作弊,写个程序求下最优解.
棋是立体的一字棋,七列,六行,交替落子,每个棋子可以选择任一列放置,自动落到本列最低的空位上.
只要某一方的四个棋子连成横竖斜一条直线,即胜.
1.使用二维数组记录棋盘状态$board,使用R/G记录棋手$oper
2.function process($board, $oper, $path) 计算此状态下,指定棋手的最优结果
3.function judge($board, $oper, $x, $y) 判断指定棋手如果落子在(x,y)处,是否获胜
细节略,都是数据结构上的内容.
去处过程中,进行了剪枝.
原计算规模: 共42个棋子,每次落子可以选择七列中的任一列(只要未满), 也就是说:计算规模等同于7的42次方.
写完程序,运行了十几分钟,发现,计算规模过大,算法不现实.
打算有时间进行A*优化.
阅读(642) | 评论(0) | 转发(0) |
