广工人工智能试验报告材料

1、实用文档实验课程名称： 人工智能实验项目名称井子棋 AI alpha-beta 剪枝算法实验成绩实验者叶海恒 专业班级 计科 8 班学号3114006156实验日期2016.11一、实验内容设计具有 AI 的井子棋游戏（采用 js ）AI 采用 - 剪枝算法二、实验设计（原理分析及流程）min 电脑 AI 下棋时，如果考虑步数为 0，则代表直接返回当前棋盘估值 w（值越大代表对 max 越有优势，越小则代表对 min 越有优势， w=maxW-minW）。如果考虑步数为 N，先获取 min 电脑可以下棋的位置 steps 。 对于可以下棋的一步 step ，电脑 AI 下棋到 step 的第

2、row 行，第 column 列。如果这时候 min 电脑已经赢了，则把棋盘回退一步，返回棋盘估值和下棋位置，不用再考虑其 他走法了。否则， min 需要在每一种走法里面，选择一种走法，令max 人类走 N-1 步之后，自己的优势保持最大（即 w 值最小）。什么是 alpha-beta 剪枝呢？就是如果 max 人类当前一种走法 1 至少可以获取 alpha 优势，而 另一种走法 2，min 电脑的一步棋则可能让人类获取比alpha 更小的优势，那么 max 人类肯定不会选择走法 2，所以计算在计算 min 电脑的走法时， min 电脑的其他走法就不用再计算了。 最后 min 电脑经过 ste

3、ps.length 种走法对比之后，选择 w 值最小的一种走法，把棋盘回退一 步，并返回棋盘估值和下棋位置。max走法类似， 人类会选择 w 值最大的走法下棋， 所以 max函数和 min 函数分别代表人和 AI 下 棋，互相递归调用，直到递归到步数为0 时返回 N 步之后的估值。实用文档三、实验代码及数据记录1. 代码/* Matrix 矩阵 矩阵二维数组 * param type arr */var Matrix = function(arr) this.data = arr;this.row = arr.length;this.column = arr.length ? arr0.len

4、gth : 0; ;/* multiply 矩阵乘法转换 * param type matrix 转换矩阵 * return typedescription*/Mtotype.multiply = function(matrix) if (this.column = matrix.row) var row = this.row,column = matrix.column, arr = ;for (var i = 0; i row; i+) arri = ;for (var j = 0; j column; j+) var sum = 0;for (var n = 0; n

5、this.column; n+) sum += (this.datain * matrix.datanj); arrij = sum; return new Matrix(arr); ; /* Chessboard 棋盘 * param type row description* param type column description*/var Chessboard = function(row, column) this.data = ; this.row = row;this.column = column;实用文档for (var i = 0; i row; i+) this.dat

6、ai = ;for (var j = 0; j column; j+) this.dataij = Chessboard.NONE;this.stack = ;this.is_ended = false;/* toString 输出棋盘信息 * return type description*/Ctotype.toString = function() return this.data.map(function(data) return data.toString();).join(n);/* put 下棋 列 人还是 AI 下棋 param type row par

7、am type column param type type * return type description*/Ctotype.put = function(row, column, type) if (this.datarowcolumn = Chessboard.NONE) this.datarowcolumn = type;this.stack.push(row: row,column: column,type: type);if (this.stack.length = this.row * this.column) this.is_ended = tru

8、e;return this;/* rollback悔棋 * param type n 后退 n 步 return type description */实用文档Ctotype.rollback = function(n) n = n | 1;for (var i = 0; i n; i+) var step = this.stack.pop(); if (step) this.datastep.rowstep.column = Chessboard.NONE; this.is_ended = false; return this;/* reset 重置棋盘 * ret

9、urn type description*/Ctotype.reset = function() for (var i = 0, n = this.row; i n; i+) for (var j = 0, m = this.column; j m; j+) this.dataij = Chessboard.NONE;this.stack = ;this.is_ended = false;/* availableSteps 获取可走的位置 * return type description*/Ctotype.availableSteps =

10、function() var availableSteps = ;for (var i = 0, n = this.row; i n; i+) for (var j = 0, m = this.column; j m; j+) if (this.dataij = Chessboard.NONE) availableSteps.push(row: i, column: j);return availableSteps;/* rotate 把棋盘旋转 90 度 实用文档* return type description*/Ctotype.rotate = function

11、() var board = new Chessboard(this.row, this.column), dx = Math.floor(this.column / 2), dy = Math.floor(this.row / 2);for (var i = 0; i this.row; i+) for (var j = 0; j this.column; j+) var type = this.dataij; var matrix = new Matrix(i, j, 1);var translateMatrix1 = new Matrix(1, 0, 0,0, 1, 0,-dx, -dy

12、, 1);var translateMatrix2 = new Matrix(1, 0, 0,0, 1, 0,dx, dy, 1);var rotateMatrix = new Matrix(0, -1, 0,1, 0, 0,0, 0, 1);var res = matrix.multiply(translateMatrix1).multiply(rotateMatrix).multiply(translateMatrix2); board.put(res.data00, res.data01, type);return board;/* hash 给棋盘一个编码 * param type s

13、ourceRadix 来源进制 * param type targetRadix 目的进制 * return type description*/Ctotype.hash = function(sourceRadix, targetRadix) var str = this.data.map(function(arr) return arr.join();).join();return parseInt(str, sourceRadix).toString(targetRadix);实用文档;/* evaluate 计算当前棋盘的估值 * return type de

14、scription*/Ctotype.evaluate = function() /max ，min 权重， max 连棋数， min 连棋数 var maxW = minW = 0,maxCount, minCount;/ 横向计算for (var i = 0; i this.row; i+) / 当前这一行， max 连棋数， min 连棋数 maxCount = minCount = 0;for (var j = 0; j this.column; j+) var type = this.dataij;if (type = Chessboard.MAX) max

15、Count+; else if (type = Chessboard.MIN) minCount+;/ 如果连成 3 子 if (maxCount = 3) return Infinity; else if (minCount = 3) return -Infinity; else / 如果没有 max的棋子，则 min 可能连成 3 子 if (!maxCount) minW+;/ 如果没有 min 的棋子，则 max可能连成 3 子 if (!minCount) maxW+;/ 纵向计算for (var i = 0; i this.column; i+) / 当前这一列， max 连棋数，

16、 min 连棋数实用文档maxCount = minCount = 0;for (var j = 0; j this.row; j+) var type = this.dataji; if (type = Chessboard.MAX) maxCount+; else if (type = Chessboard.MIN) minCount+; / 如果连成 3 子 if (maxCount = this.row) return Infinity; else if (minCount = this.row) return -Infinity; else / 如果没有 max的棋子，则 min 可

17、能连成 3 子 if (!maxCount) minW+;/ 如果没有 min 的棋子，则 max可能连成 3 子 if (!minCount) maxW+;/ 右斜下方向计算 maxCount = minCount = 0;for (var i = 0; i this.column; i+) var type = this.dataii;if (type = Chessboard.MAX) maxCount+; else if (type = Chessboard.MIN) minCount+; / 如果连成 3 子if (maxCount = this.row) 实用文档return In

18、finity; else if (minCount = this.row) return -Infinity; else / 如果没有 max 的棋子，则 min 可能连成 3 子 if (!maxCount) minW+;/ 如果没有 min 的棋子，则 max 可能连成 3 子 if (!minCount) maxW+;/ 左斜下方向计算 maxCount = minCount = 0;for (var i = 0; i this.column; i+) var type = this.dataithis.column - i - 1;if (type = Chessboard.MAX)

19、maxCount+; else if (type = Chessboard.MIN) minCount+;if (maxCount = this.row) return Infinity; else if (minCount = this.row) return -Infinity; else / 如果没有 max 的棋子，则 min 可能连成 3 子 if (!maxCount) minW+;/ 如果没有 min 的棋子，则 max 可能连成 3 子 if (!minCount) maxW+;/ 返回双方实力差实用文档return maxW - minW;/* * isMaxWin 人是否赢

20、了 * return Boolean description */Ctotype.isMaxWin = function() var w = this.evaluate();return w = Infinity ? true : false;/* * isMinWin AI 是否赢了 * return Boolean description */Ctotype.isMinWin = function() var w = this.evaluate();return w = -Infinity ? true : false;/* * end

21、结束游戏 * return type description */Ctotype.end = function() this.is_ended = true;return this;/* * isEnded 游戏是否结束 * return Boolean description */Ctotype.isEnded = function() return this.is_ended;/*当前棋盘 考虑深度 * max max 下棋 * param type currentChessboard * param type depth * retur

22、n typedescription*/ var max = function(currentChessboard, depth, beta) / 记录优势值，应该下棋的位置var row, column, alpha = -Infinity;/ 什么都不下，直接返回当前棋盘评估值if (depth = 0) 实用文档alpha = currentChessboard.evaluate();return w: alpha; else / 获取每一步可以走的方案var steps = currentChessboard.availableSteps();/ console.log(搜索 MAX +

23、 steps.length + 个棋局 );if (steps.length) / 对于每一种走法for (var i = 0, l = steps.length; i alpha) / 选择最大优势的走法alpha = res.w;row = step.row;column = step.column;/ 如果人可以获得更好的走法，则 AI 必然不会选择这一步走法，所以不用再考虑人的其他走法if (alpha = beta) / console.log(MAX节点 + l + 个棋局，剪掉了 + (l - 1 - i) + 个 MIN 棋局 );break;return 实用文档w: alp

24、ha, row: row, column: column; ; /* min min 下棋 * param type currentChessboard 当前棋盘 * param type depth 考虑深度 * return type 权重和当前推荐下棋的位置 */var min = function(currentChessboard, depth, alpha) var row, column, beta = Infinity;if (depth = 0) beta = currentChessboard.evaluate();return w: beta; else / 获取每一步可以走的方案var steps = currentChessboard.availableSteps();/ console.log(搜索 MIN + steps.length + 个棋局 );if (steps.length) / 对于每一种