廣工人工智能實(shí)驗(yàn)報(bào)告

1、.專業(yè)整理 .實(shí)驗(yàn)課程名稱 ：_人工智能實(shí)驗(yàn)項(xiàng)目名稱井子棋 AIalpha-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 的第 ro

2、w 行，第 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ì)算了。.學(xué)習(xí)幫手 .專業(yè)整理 .最后 m

3、in 電腦經(jīng)過steps.length種走法對(duì)比之后，選擇 w 值最小的一種走法，把棋盤回退一步，并返回棋盤估值和下棋位置。max 走法類似 ，人類會(huì)選擇w 值最大的走法下棋，所以 max 函數(shù)和 min 函數(shù)分別代表人和AI下棋 ，互相遞歸調(diào)用 ，直到遞歸到步數(shù)為0 時(shí)返回 N 步之后的估值 。.學(xué)習(xí)幫手 .專業(yè)整理 .三、實(shí)驗(yàn)代碼及數(shù)據(jù)記錄1. 代碼/* Matrix矩陣 * param type arr 矩陣二維數(shù)組 */var Matrix = function(arr) this.data = arr;this.row = arr.length;this.column = arr.l

4、ength ? arr0.length : 0;/* multiply矩陣乘法轉(zhuǎn)換 * paramtype matrix 轉(zhuǎn)換矩陣 * return typedescription*/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.data

5、in * matrix.datanj);arri j = sum;return new Matrix(arr);/* Chessboard棋盤 * param type rowdescription* param type column description*/var Chessboard = function(row, column) this.data = ;this.row = row;.學(xué)習(xí)幫手 .專業(yè)整理 .this.column = column;for (var i = 0; i row; i+) this.datai = ;for (var j = 0; j column;

6、j+) this.datai j = Chessboard.NONE;this.stack = ;this.is_ended = false;/* toString 輸出棋盤信息 * return type description*/return data.toString();).join(n);/* put下棋 * paramtype row行* paramtype column 列 * paramtype type人還是 AI 下棋* return typedescription*/if (this.datarowcolumn = Chessboard.NONE) this.dataro

7、wcolumn = type;row: row,column: column,type: type);this.is_ended = true;return this;/* rollback悔棋 * paramtype n 后退 n 步* return typedescription.學(xué)習(xí)幫手 .專業(yè)整理 .*/n = n | 1;for (var i = 0; i n; i+) if (step) this.datastep.rowstep.column = Chessboard.NONE;this.is_ended = false;return this;/* reset 重置棋盤 * r

8、eturn type description*/for (var i = 0, n = this.row; i n; i+) for (var j = 0, m = this.column; j m; j+) this.datai j = Chessboard.NONE;this.stack = ;this.is_ended = false;/* availableSteps獲取可走的位置 * return type description*/var availableSteps = ;for (var i = 0, n = this.row; i n; i+) for (var j = 0,

9、 m = this.column; j m; j+) if (this.dataij = Chessboard.NONE) availableSteps.push(row: i,column: j);return availableSteps;/*.學(xué)習(xí)幫手 .專業(yè)整理 .* rotate 把棋盤旋轉(zhuǎn) 90 度 * return type description*/var board = new Chessboard(this.row, this.column),dx = Math.floor(this.column / 2),dy = Math.floor(this.row / 2);for

10、 (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);

11、var res = matrix.multiply(translateMatrix1).multiply(rotateMatrix).multiply(translateMatrix2); board.put(res.data00, res.data01, type);return board;/* hash 給棋盤一個(gè)編碼 * paramtype sourceRadix 來源進(jìn)制 * paramtype targetRadix 目的進(jìn)制 * return typedescription*/return arr.join();).join();.學(xué)習(xí)幫手 .專業(yè)整理 .return parse

12、Int(str, sourceRadix).toString(targetRadix);/* evaluate 計(jì)算當(dāng)前棋盤的估值 * return type description*/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.d

13、ataij;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+;/ 縱向計(jì)算for (var i = 0;

14、 i this.column; i+) .學(xué)習(xí)幫手 .專業(yè)整理 ./ 當(dāng)前這一列 ，max 連棋數(shù)， min 連棋數(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) r

15、eturn -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.dataii;if (type = Chessboard.MAX) maxCount+; else if (type = Chessboard.MIN) minCount+;/ 如果連

16、成 3 子.學(xué)習(xí)幫手 .專業(yè)整理 .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+;/ 左斜下方向計(jì)算maxCount = minCount = 0;for (var i = 0; i this.column; i+) var type = this.dat

17、aithis.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+;.學(xué)習(xí)

18、幫手 .專業(yè)整理 ./ 返回雙方實(shí)力差return maxW - minW;/* isMaxWin 人是否贏了 * return Boolean description*/var w = this.evaluate();return w = Infinity ? true : false;/* isMinWin AI是否贏了 * return Boolean description*/var w = this.evaluate();return w = -Infinity ? true : false;/* end 結(jié)束游戲 * return type description*/this.is

19、_ended = true;return this;/* isEnded 游戲是否結(jié)束 * return Boolean description*/return this.is_ended;/* max max下棋 * paramtype currentChessboard 當(dāng)前棋盤 * paramtype depth考慮深度 * return typedescription*/var max = function(currentChessboard, depth, beta) / 記錄優(yōu)勢(shì)值 ，應(yīng)該下棋的位置var row, column, alpha = -Infinity;/ 什么都不下

20、 ，直接返回當(dāng)前棋盤評(píng)估值.學(xué)習(xí)幫手 .專業(yè)整理 .if (depth = 0) alpha = currentChessboard.evaluate();return w: alpha; else / 獲取每一步可以走的方案var steps = currentChessboard.availableSteps();/ console.log(搜索 MAX + steps.length + 個(gè)棋局 );if (steps.length) / 對(duì)于每一種走法for (var i = 0, l = steps.length; i alpha) / 選擇最大優(yōu)勢(shì)的走法alpha = res.w;r

21、ow = step.row;column = step.column;/ 如果人可以獲得更好的走法，則 AI 必然不會(huì)選擇這一步走法，所以不用再考慮人的其他走法if (alpha = beta) / console.log(MAX節(jié)點(diǎn) + l + 個(gè)棋局，剪掉了 + (l - 1 - i) + 個(gè) MIN 棋局 );break;.學(xué)習(xí)幫手 .專業(yè)整理 .return w: alpha,row: row,column: column;/* min min下棋 * paramtype currentChessboard 當(dāng)前棋盤 * paramtype depth考慮深度 * return typ

22、e權(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ì)于每一種走法for (var i = 0, l = steps.length; i l; i+) var step = stepsi;/ 下棋currentChessboard.put(step.row, st