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

-实验课程名称：_人工智能 实验工程名称井子棋AI alpha-beta剪枝算法实验成绩实 验 者专业班级学 号实验日期一、实验容设计具有AI的井子棋游戏采用jsAI采用-剪枝算法二、实验设计原理分析及流程min电脑AI下棋时，如果考虑步数为0，则代表直接返回当前棋盘估值w值越大代表对ma*越有优势，越小则代表对min越有优势，w=ma*W-minW。如果考虑步数为N，先获取min电脑可以下棋的位置steps。对于可以下棋的一步step，电脑AI下棋到step的第row行，第column列。如果这时候min电脑已经赢了，则把棋盘回退一步，返回棋盘估值和下棋位置，不用再考虑其他走法了。否则，min需要在每一种走法里面，选择一种走法，令ma*人类走N-1步之后，自己的优势保持最大即w值最小。什么是alpha-beta剪枝呢？就是如果ma*人类当前一种走法1至少可以获取alpha优势，而另一种走法2，min电脑的一步棋则可能让人类获取比alpha更小的优势，则ma*人类肯定不会选择走法2，所以计算在计算min电脑的走法时，min电脑的其他走法就不用再计算了。最后min电脑经过steps.length种走法比照之后，选择w值最小的一种走法，把棋盘回退一步，并返回棋盘估值和下棋位置。ma*走法类似，人类会选择w值最大的走法下棋，所以ma*函数和min函数分别代表人和AI下棋，互相递归调用，直到递归到步数为0时返回N步之后的估值。三、实验代码及数据记录1.代码 /* * Matri* 矩阵 * param type arr 矩阵二维数组 */var Matri* = function(arr) this.data = arr; this.row = arr.length; this.column = arr.length " arr0.length : 0;/* * multiply 矩阵乘法转换 * param type matri* 转换矩阵 * return type description */Matri*.prototype.multiply = function(matri*) if (this.column = matri*.row) var row = this.row, column = matri*.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 * matri*.datanj); arrij = sum; return new Matri*(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 */Chessboard.prototype.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 */Chessboard.prototype.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 */Chessboard.prototype.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 */Chessboard.prototype.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 */Chessboard.prototype.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 */Chessboard.prototype.rotate = function() var board = new Chessboard(this.row, this.column), d* = 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 matri* = new Matri*( i, j, 1 ); var translateMatri*1 = new Matri*( 1, 0, 0, 0, 1, 0, -d*, -dy, 1 ); var translateMatri*2 = new Matri*( 1, 0, 0, 0, 1, 0, d*, dy, 1 ); var rotateMatri* = new Matri*( 0, -1, 0, 1, 0, 0, 0, 0, 1 ); var res = matri*.multiply(translateMatri*1).multiply(rotateMatri*).multiply(translateMatri*2); board.put(res.data00, res.data01, type); return board;/* * hash 给棋盘一个编码 * param type sourceRadi* 来源进制 * param type targetRadi* 目的进制 * return type description */Chessboard.prototype.hash = function(sourceRadi*, targetRadi*) var str = this.data.map(function(arr) return arr.join(''); ).join(''); return parseInt(str, sourceRadi*).toString(targetRadi*);/* * evaluate 计算当前棋盘的估值 * return type description */Chessboard.prototype.evaluate = function() /ma*，min权重，ma*连棋数，min连棋数 var ma*W = minW = 0, ma*Count, minCount; /横向计算 for (var i = 0; i < this.row; i+) /当前这一行，ma*连棋数，min连棋数 ma*Count = minCount = 0; for (var j = 0; j < this.column; j+) var type = this.dataij; if (type = Chessboard.MA*) ma*Count+; else if (type = Chessboard.MIN) minCount+; /如果连成3子 if (ma*Count = 3) return Infinity; else if (minCount = 3) return -Infinity; else /如果没有ma*的棋子，则min可能连成3子 if (!ma*Count) minW+; /如果没有min的棋子，则ma*可能连成3子 if (!minCount) ma*W+; /纵向计算 for (var i = 0; i < this.column; i+) /当前这一列，ma*连棋数，min连棋数 ma*Count = minCount = 0; for (var j = 0; j < this.row; j+) var type = this.dataji; if (type = Chessboard.MA*) ma*Count+; else if (type = Chessboard.MIN) minCount+; /如果连成3子 if (ma*Count = this.row) return Infinity; else if (minCount = this.row) return -Infinity; else /如果没有ma*的棋子，则min可能连成3子 if (!ma*Count) minW+; /如果没有min的棋子，则ma*可能连成3子 if (!minCount) ma*W+; /右斜下方向计算 ma*Count = minCount = 0; for (var i = 0; i < this.column; i+) var type = this.dataii; if (type = Chessboard.MA*) ma*Count+; else if (type = Chessboard.MIN) minCount+; /如果连成3子 if (ma*Count = this.row) return Infinity; else if (minCount = this.row) return -Infinity; else /如果没有ma*的棋子，则min可能连成3子 if (!ma*Count) minW+; /如果没有min的棋子，则ma*可能连成3子 if (!minCount) ma*W+; /左斜下方向计算 ma*Count = minCount = 0; for (var i = 0; i < this.column; i+) var type = this.dataithis.column - i - 1; if (type = Chessboard.MA*) ma*Count+; else if (type = Chessboard.MIN) minCount+; if (ma*Count = this.row) return Infinity; else if (minCount = this.row) return -Infinity; else /如果没有ma*的棋子，则min可能连成3子 if (!ma*Count) minW+; /如果没有min的棋子，则ma*可能连成3子 if (!minCount) ma*W+; /返回双方实力差 return ma*W - minW;/* * isMa*Win 人是否赢了 * return Boolean description */Chessboard.prototype.isMa*Win = function() var w = this.evaluate(); return w = Infinity " true : false;/* * isMinWin AI是否赢了 * return Boolean description */Chessboard.prototype.isMinWin = function() var w = this.evaluate(); return w = -Infinity " true : false;/* * end 完毕游戏 * return type description */Chessboard.prototype.end = function() this.is_ended = true; return this;/* * isEnded 游戏是否完毕 * return Boolean description */Chessboard.prototype.isEnded = function() return this.is_ended;/* * ma* ma*下棋 * param type currentChessboard 当前棋盘 * param type depth 考虑深度 * return type description */var ma* = 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('搜索MA*' + steps.length + '个棋局'); if (steps.length) /对于每一种走法 for (var i = 0, l = steps.length; i < l; i+) var step = stepsi; /下棋 currentChessboard.put(step.row, step.column, Chessboard.MA*); /如果已经赢了，则直接下棋，不再考虑对方下棋 if (currentChessboard.isMa*Win() alpha = Infinity; row = step.row; column = step.column; /退回上一步下棋 currentChessboard.rollback(); break; else /考虑对方depth-1步下棋之后的优势值，如果对方没棋可下了，则返回当前棋盘估值 var res = min(currentChessboard, depth - 1) | w: currentChessboard.evaluate() ; /退回上一步下棋 currentChessboard.rollback(); if (res.w > alpha) /选择最大优势的走法 alpha = res.w; row = step.row; column = step.column; /如果人可以获得更好的走法，则AI必然不会选择这一步走法，所以不用再考虑人的其他走法 if (alpha >= beta) / console.log('MA*节点' + 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) /对于每一种走法 for (var i = 0, l = steps.length; i < l; i+) var step = stepsi; /下棋 currentChessboard.put(step.row, step.column, Chessboard.MIN); /如果已经赢了，则直接下棋，不再考虑对方下棋 if (currentChessboard.isMinWin() beta = -Infinity; row = step.row; column = step.column; /退回上一步下棋 currentChessboard.rollback(); break; else /考虑对方depth-1步下棋之后的优势值，如果对方没棋可下了，则返回当前棋盘估值 var res = ma*(currentChessboard, depth - 1, beta) | w: currentChessboard.evaluate() ; /退回上一步下棋 currentChessboard.rollback(); if (res.w < beta) /选择最大优势的走法 beta = res.w; row = step.row; column = step.column; /如果AI可以获得更好的走法，则人必然不会选择这一步走法，所以不用再考虑AI的其他走法 if (beta <= alpha) / console.log('MIN节点' + l + '个棋局，剪掉了' + (l - 1 - i) + '个MA*棋局'); break; return w: beta, row: row, column: column ; ;/没有棋子Chessboard.NONE = 0;/玩家棋子Chessboard.MA* = 1;/AI棋子Chessboard.MIN = 2;2.结果截图黑方人类 白方AI. z.