廣工人工智能試驗(yàn)報(bào)告材料

1、實(shí)用文檔實(shí)驗(yàn)課程名稱： 人工智能實(shí)驗(yàn)項(xiàng)目名稱井子棋 AI alpha-beta 剪枝算法實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)者葉海恒 專業(yè)班級(jí) 計(jì)科 8 班學(xué)號(hào)3114006156實(shí)驗(yàn)日期2016.11一、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)具有 AI 的井子棋游戲（采用 js ）AI 采用 - 剪枝算法二、實(shí)驗(yàn)設(shè)計(jì)（原理分析及流程）min 電腦 AI 下棋時(shí)，如果考慮步數(shù)為 0，則代表直接返回當(dāng)前棋盤估值 w（值越大代表對(duì) max 越有優(yōu)勢(shì)，越小則代表對(duì) min 越有優(yōu)勢(shì)， w=maxW-minW）。如果考慮步數(shù)為 N，先獲取 min 電腦可以下棋的位置 steps 。 對(duì)于可以下棋的一步 step ，電腦 AI 下棋到 step 的第

2、row 行，第 column 列。如果這時(shí)候 min 電腦已經(jīng)贏了，則把棋盤回退一步，返回棋盤估值和下棋位置，不用再考慮其 他走法了。否則， min 需要在每一種走法里面，選擇一種走法，令max 人類走 N-1 步之后，自己的優(yōu)勢(shì)保持最大（即 w 值最小）。什么是 alpha-beta 剪枝呢？就是如果 max 人類當(dāng)前一種走法 1 至少可以獲取 alpha 優(yōu)勢(shì)，而 另一種走法 2，min 電腦的一步棋則可能讓人類獲取比alpha 更小的優(yōu)勢(shì)，那么 max 人類肯定不會(huì)選擇走法 2，所以計(jì)算在計(jì)算 min 電腦的走法時(shí)， min 電腦的其他走法就不用再計(jì)算了。 最后 min 電腦經(jīng)過 ste

3、ps.length 種走法對(duì)比之后，選擇 w 值最小的一種走法，把棋盤回退一 步，并返回棋盤估值和下棋位置。max走法類似， 人類會(huì)選擇 w 值最大的走法下棋， 所以 max函數(shù)和 min 函數(shù)分別代表人和 AI 下 棋，互相遞歸調(diào)用，直到遞歸到步數(shù)為0 時(shí)返回 N 步之后的估值。實(shí)用文檔三、實(shí)驗(yàn)代碼及數(shù)據(jù)記錄1. 代碼/* Matrix 矩陣 矩陣二維數(shù)組 * param type arr */var Matrix = function(arr) this.data = arr;this.row = arr.length;this.column = arr.length ? arr0.len

4、gth : 0; ;/* multiply 矩陣乘法轉(zhuǎn)換 * param type matrix 轉(zhuǎn)換矩陣 * 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;實(shí)用文檔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 */實(shí)用文檔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 把棋盤旋轉(zhuǎn) 90 度 實(shí)用文檔* 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 給棋盤一個(gè)編碼 * param type s

13、ourceRadix 來源進(jìn)制 * param type targetRadix 目的進(jìn)制 * 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);實(shí)用文檔;/* evaluate 計(jì)算當(dāng)前棋盤的估值 * return type de

14、scription*/Ctotype.evaluate = function() /max ，min 權(quán)重， max 連棋數(shù)， min 連棋數(shù) var maxW = minW = 0,maxCount, minCount;/ 橫向計(jì)算for (var i = 0; i this.row; i+) / 當(dāng)前這一行， max 連棋數(shù)， min 連棋數(shù) 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+;/ 縱向計(jì)算for (var i = 0; i this.column; i+) / 當(dāng)前這一列， max 連棋數(shù)，

16、 min 連棋數(shù)實(shí)用文檔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+;/ 右斜下方向計(jì)算 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) 實(shí)用文檔return In

18、finity; else if (minCount = this.row) return -Infinity; else / 如果沒有 max 的棋子，則 min 可能連成 3 子 if (!maxCount) minW+;/ 如果沒有 min 的棋子，則 max 可能連成 3 子 if (!minCount) maxW+;/ 左斜下方向計(jì)算 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+;/ 返回雙方實(shí)力差實(shí)用文檔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、結(jié)束游戲 * return type description */Ctotype.end = function() this.is_ended = true;return this;/* * isEnded 游戲是否結(jié)束 * return Boolean description */Ctotype.isEnded = function() return this.is_ended;/*當(dāng)前棋盤 考慮深度 * max max 下棋 * param type currentChessboard * param type depth * retur

22、n typedescription*/ var max = function(currentChessboard, depth, beta) / 記錄優(yōu)勢(shì)值，應(yīng)該下棋的位置var row, column, alpha = -Infinity;/ 什么都不下，直接返回當(dāng)前棋盤評(píng)估值if (depth = 0) 實(shí)用文檔alpha = currentChessboard.evaluate();return w: alpha; else / 獲取每一步可以走的方案var steps = currentChessboard.availableSteps();/ console.log(搜索 MAX +

23、 steps.length + 個(gè)棋局 );if (steps.length) / 對(duì)于每一種走法for (var i = 0, l = steps.length; i alpha) / 選擇最大優(yōu)勢(shì)的走法alpha = res.w;row = step.row;column = step.column;/ 如果人可以獲得更好的走法，則 AI 必然不會(huì)選擇這一步走法，所以不用再考慮人的其他走法if (alpha = beta) / console.log(MAX節(jié)點(diǎn) + l + 個(gè)棋局，剪掉了 + (l - 1 - i) + 個(gè) MIN 棋局 );break;return 實(shí)用文檔w: alp

24、ha, row: row, column: column; ; /* min min 下棋 * param type currentChessboard 當(dāng)前棋盤 * param type depth 考慮深度 * return type 權(quán)重和當(dāng)前推薦下棋的位置 */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 + 個(gè)棋局 );if (steps.length) / 對(duì)于每一種