广工人工智能实验报告.doc

实验课程名称：_人工智能 实验项目名称井子棋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的第row行，第column列。如果这时候min电脑已经赢了，则把棋盘回退一步，返回棋盘估值和下棋位置，不用再考虑其他走法了。否则，min需要在每一种走法里面，选择一种走法，令max人类走N-1步之后，自己的优势保持最大（即w值最小）。什么是alpha-beta剪枝呢？就是如果max人类当前一种走法1至少可以获取alpha优势，而另一种走法2，min电脑的一步棋则可能让人类获取比alpha更小的优势，那么max人类肯定不会选择走法2，所以计算在计算min电脑的走法时，min电脑的其他走法就不用再计算了。最后min电脑经过steps.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.length : 0;/* * multiply 矩阵乘法转换 * param type matrix 转换矩阵 * return type description */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 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.datai = ; 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 下棋 * param type row 行 * param type column 列 * param type type 人还是AI下棋 * 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 = true; 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 重置棋盘 * return 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 = 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() 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, 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 sourceRadix 来源进制 * 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 description */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) maxCount+; 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连棋数，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可能连成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 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.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子 if (!minCount) maxW+; /返回双方实力差 return maxW - minW;/* * isMaxWin 人是否赢了 * 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 结束游戏 * 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 考虑深度 * return type description */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 + 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: 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 (steps.length) /对于每一