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

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

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

3、走法类似，人类会选择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 ? arrOength : 0;/* multiply矩阵乘法转换* param type matrix 转换矩阵* return type description*/Mat

4、totype.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 this.column; n+) sum += (this.datain * matrix.datanj);arrij = sum;return new Matrix(arr

5、);/* 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.datai=;for (var j = 0; j column; j+) this.dataij = Chessboard.NONE;this.stack =;this.is_ended = false;

6、/* toString 输出棋盘信息* return type description*/Ctotype.toString = function。return this.data.map(function(data) return data.toString();)join(n);/* put 下棋param type row 列人还是Al下棋param type column param type type * return type description*/Ctotype.put = function(row, column, type

7、) if (this.datarowcolumn = Chessboard.NONE) this.datarowcolumn = type;this.stack.push(row: row,column: column,type: type);if (this.stackength = this.row * this.column) this.is_ended = true;return this;/* rollback 悔棋* param type n 后退 n 步return type description*/Ctotype.rollback = functio

8、n(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重置棋盘* return type description*/Ctotype.reset = function() for (var i = 0, n = this.row; i n; i+) for (var j = 0, m = thi

9、s.column; j m; j+) this.dataij = Chessboard.NONE;this.stack =;this.is_ended = false;/* availableSteps 获取可走的位置* return type description*/Ctotype.availableSteps = 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.data

10、ij = Chessboard.NONE) availableSteps.push(row: i,column: j);return availableSteps;/* rotate把棋盘旋转 90度* return type description*/Ctotype.rotate = function。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 thi

11、s.row; i+) for (var j = 0; j this.column; j+) var type = this.dataij;var matrix = new Matrix(i, j, 1);var tran slateMatrix1 = new Matrix(1, 0, 0,0, 1, 0,-dx, -dy, 1);var tran slateMatrix2 = 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

12、.multiply(translateMatrix1).multiply(rotateMatrix).multiply(translateMatrix2); board.put(res.data00, res.data01, type);return board;/* hash给棋盘一个编码* param type sourceRadix 来源进制* param type targetRadix 目的进制* return typedescription*/Ctotype.hash = function(sourceRadix, targetRadix) var str

13、 = this.data.map(function(arr) return arr.join();).join();return parseInt(str, sourceRadix).toString(targetRadix);/* evaluate计算当前棋盘的估值* return type description*/Ctotype.evaluate = function。/max , min权重，max连棋数，min连棋数var maxW = minW = 0,maxCount, minCount;/横向计算for (var i = 0; i this.row;

14、i+) / 当前这一行，max连棋数，min连棋数maxCount = minCount = 0;for (var j = 0; j this.column; j+) var type = this.dataij;if (type = Chessboard.MAX) maxCount+; else if (type = Chessboard.MIN) minCount+;/ 如果连成3子if (maxCo unt = 3) return Infin ity; else if (minCount = 3) retur n -Infini ty; else /如果没有max的棋子，则 min可能连

15、成3子if (!maxCount) min W+;/如果没有min的棋子，则 max可能连成3子if (!mi nCou nt) maxW+;/纵向计算for (var i = 0; i this.colum n; i+) / 当前这一列，max连棋数，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+;/ 如果

16、连成3子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+;/ 右斜下方向计算maxCount = minCount = 0;for (var i = 0; i this.column; i+) var type = this.dataii;if (type = Chessboard.

17、MAX) maxCount+; else if (type = Chessboard.MIN) minCount+;if (maxCount = this.row) / 如果连成3子实用文档return Infinity; 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;

18、i this.column; i+) var type = this.dataithis.column - i - 1;if (type = Chessboard.MAX) 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子

19、if (!minCount) maxW+;/ 返回双方实力差实用文档return maxW - minW;/* isMaxWin人是否赢了 * return Boolean description */Ctotype.isMaxWin = function。var w = this.evaluate();return w = Infinity ? true : false;/* * isMinWin Al 是否赢了 * return Boolean description */Ctotype.isMinWin = function() var

20、 w = this.evaluate();return w = -Infinity ? true : false;/* end结束游戏* 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 下棋当前棋盘考虑深度*

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

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

23、1 - i) + 个 MIN棋局);break;return /退回上一步下棋w: alpha,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 (stepsength) /对