黑白棋代码

AI = {};

function(){

n= pattern;

04.// 定义了 8 个偏移量

05.// 可以简单通过加法得到任一点周围 8 个点的坐标

06.// -11 -10 -9

07.// -1 x 1

08.// 9 10 11

09.// 如左上角的坐标为 x + (-11)

directions=[-11,-10,-9,-1,1,9,10,11];

on pattern()

12.{

13. // 把整个棋盘填满 0

14. for(var i=0;i<100;i++)this[i]=0;

15. // 中间的 4 个格子，先放上两黑两白的棋子

16. this[54]=this[45]=1;this[55]=this[44]=2;

17. // 黑净胜外围子数目（黑减去白），估值时用。

18. ence=0;

19. // 当前可走棋方为黑棋

20. =1;

21. // 已经走了几步棋

22. =0;

23. // 稳定原型

24. // 0 是空白，1 是黑棋，2 是白棋，3 是边界

25. // 把 8 * 8 的棋盘扩展成 10 * 10，是一种技巧

26. // 可以简化坐标有效性的判断

27. var stableProto = [

28. 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,

29. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

30. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

31. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

32. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

33. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

34. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

35. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

36. 3, 0, 0, 0, 0, 0, 0, 0, 0, 3,

37. 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

38. ]

39. // 从一个 8 * 8 的棋盘载入状态

40. =function(arr)

41. {

42. for(var y=1;y<=8;y++)

43. {

44. for(var x=1;x<=8;x++)

45. {

46. this[y*10+x]=arr[y-1][x-1];

47. }

48. }

49. }

50. // 判断能不能 pass

51. // 如果能，则当前可走棋方变更

52. =function()

53. {

54. for(var y=1;y<=8;y++)

55. {

56. for(var x=1;x<=8;x++)

57. {

58. if(this[y*10+x]==0)

59. {

60. // 有任何一步棋可走，都不可以 Pass

61. if((x,y,))

62. {

63. return false;

64. }

65. }

66. }

67. }

68. //alert("pass");

69. // 这是一个技巧，因为 的值域是 {1, 2}

70. // 所以当 color 是 1 时，执行完下一语句后就是 2

71. // 当 color 是 2 时，执行完下一语句后就是 1

72. = 3 - ;

73. return true;

74. }

75. =function()

76. {

77. function pattern(){}

78. ype=this;

79. return new pattern();

80. }

81. ng=function()

82. {

83. var icon=[" ","*","o"]

84. var r="";

85. for(var y=1;y<=8;y++)

86. {

87. for(var x=1;x<=8;x++)

88. {

89. r+=icon[this[y*10+x]]+" ";

90. //r+=stableDiscs[y*10+x]+" ";

91. }

92. r+="n";

93. }

94. return r+();

95. }

96.

97. // 净胜子数

98. =function()

99. {

100. // 这里是一个技巧， r[0] 是不使用的，r[1] r[2] 对应黑白棋子的个数

101. var r=[0,0,0];

102. for(var y=1;y<=8;y++)

103. {

104. for(var x=1;x<=8;x++)

105. {

106. r[this[y*10+x]]++; // 数目加一

107. }

108. }

109. // 当前颜的数量为 0，输了，返回负极值

110. if(r[]==0) return -64;

111. // 敌对颜的数量为 0，赢了，返回极值

112. if(r[]==0) return 64;

113. // 返回当前走棋方比对方多的数量

114. return r[]-r[];

115. }

116. // 对棋盘的估值

117. ate=function()

118. {

119. // 基本估值方法：

120. // 1、能占棋盘四角是很有价值的

121. // 2、邻近棋盘四角的位子是很差的

122. // 3、稳定子

123. // 4、外围子净胜数

124. var r=[0,0,0];

125. var r=ence;

126. // 如果左上角有棋子，自己的，就+30分，敌方的，-30 分

127. if(this[11]) r+=((this[11]==)?1:-1)*30;

128. // 次左上角，分值是 -15

129. else if(this[22]==)r-=15;

130. // 右上角，分值 30

131. if(this[18])r+=((this[18]==)?1:-1)*30;

132. // 次右上角，分值 -15

133. else if(this[27]==)r-=15;

134. // 左下角，分值 30

135. if(this[81])r+=((this[81]==)?1:-1)*30;

136. // 次左下角，分值 -15

137. else if(this[72]==)r-=15;

138. // 右下角，分值 30

139. if(this[88]){r+=((this[88]==)?1:-1)*30;}

140. // 次右下角，分值 -15

141. else if(this[77]==)r-=15;

142. // 查稳定子，

143. // 稳定子就是挨着 4 个角点并且周边的棋子要么是同，要么是边界

144. //var color = ;

145. var stableDiscs=();

146.

147. var queue = [];

148. if(this[11]!=0) ([11,this[11]]);

149. if(this[18]!=0) ([18,this[18]]);

150. if(this[81]!=0) ([81,this[81]]);

151. if(this[88]!=0) ([88,this[88]]);

152. while()

153. {

154. var position = queue[0][0];

155. var c = queue[0][1];

156. // 不懂 JS 的数组的内存管理算法，不过感觉从头上删除肯定是比较慢

的，

157. // 我感觉从后面删除会更好，或者使用标记不删除的方法性能会更好

158. ();

159. //if(stableDiscs[position]==0 || stableDiscs[position]==3)

continue;

160. stableDiscs[position] = c;

161. if( (stableDiscs[position-10]==3 || stableDiscs[position+10]==3

|| stableDiscs[position-10] == c || stableDiscs[position+10] == c) &&

162. (stableDiscs[position-1]==3 || stableDiscs[position+1]==3 ||

stableDiscs[position-1] == c || stableDiscs[position+1] == c) &&

163. (stableDiscs[position-11]==3 || stableDiscs[position+11]==3

|| stableDiscs[position-11] == c || stableDiscs[position+11] == c) &&

164. (stableDiscs[position-9]==3 || stableDiscs[position+9]==3 ||

stableDiscs[position-9] == c || stableDiscs[position+9] == c) )

165. {

166. stableDiscs[position]=c;

167. // 稳定子的分值为 7

168. r += ((c==)?1:-1)*7;

169. // 进一步扩展，查稳定子

170. for(var i = 0;i < ; i++)

171. if(stableDiscs[directions[i]+position]==0 &&

this[directions[i]+position]==c)

172. ([directions[i]+position,c]);

173. }

174. }

175.

176. // 返回估值

177. return r;

178. }

179. lString=function(depth)

180. {

181. var r="";

182. if(!depth)depth=0;

183.

184. for(var y=1;y<=8;y++)

185. {

186. for(var x=1;x<=8;x++)

187. {

188. if(this[y*10+x]!=0)r+=(this[y*10+x]==1?"*":"o")+" ";

189. else

190. {

191. var tmp=(x,y,);

192. if(tmp)

193. {

194. var tmp2=-(-Infinity,Infinity,depth);

195. if(tmp2<0||tmp2>9)r+=tmp2;

196. else r+=" "+tmp2;

197. }

198. else r+="X ";

199. }

200. }

201. r+="n";

202. }

203. return r+();

204. }

205. // 计算机去一步可走的棋步

206. // 这里 AI 部分的入口

207. er=function(depth,exactDepth){

208. if(!depth)depth=0;

209. if(!exactDepth)exactDepth=depth;

210. var r=[];

211. var max=-Infinity;

212. for(var y=1;y<=8;y++)

213. {

214. for(var x=1;x<=8;x++)

215. {

216. if(this[y*10+x])continue;

217. // 到一个空白格子

218. else

219. {

220. // 尝试走这个格子

221. var tmp=(x,y,);

222. // 不成功，非法

223. if(!tmp)continue;

224. // 已走步数+已搜索深度 >= 有 60 步

225. // 这时使用精确搜索得到更精确的结果

226. if(+exactDepth>=60)

227. {

228. var v=-earch(-Infinity,Infinity);

229. //alert([x,y]+":"+v);

230. }

231. // 离四个角最近的那 3 * 4 个格子，则多搜索一层

232. // 因为对手可能在下一手下在角上，会出现大翻盘。

233. else if( (x==2||x==7) && (y==2||y==7) )

234. var v=-(-Infinity,Infinity,depth+1);

235. else

236. var v=-(-Infinity,Infinity,depth);

237. // 还不如之前的棋步

238. if(v

239. // 比之前的棋步好

240. if(v>max){

241. // 保存起来

242. r=[[x,y]];max=v;

243. }

244. // 另一个可选的棋步

245. else ([x,y]);

246. }

247. }

248. }

249. // 在所有可选的棋步中，随机选择一个，让玩家觉得比较多变化，不那么单调。

250. var tmp=(()*);

251. return r[tmp];

252. }

253. // 搜索算法

254. // 使用负极大值形式的 Alpha-Beta 剪枝搜索算法

255. =function(alpha,beta,depth,pass){

256. // 叶子节点，返回估值

257. if(depth==0)return ate();

258. var canmove=false;

259. for(var y=1;y<=8;y++)

260. {

261. for(var x=1;x<=8;x++)

262. {

263. if(this[y*10+x]!=0)r+=(this[y*10+x]==1?"*":"o")+" ";

264. else

265. {

266. var tmp=(x,y,);

267. if(!tmp)continue;

268. canmove=true;

269. // 往更深搜索

270. var r=-(-beta,-alpha,depth-1);

271. //if(depth==4)(r);

272. // 收窗窗口

273. if(r>=alpha)alpha=r;

274. // 胜着

275. if(alpha>beta)return Infinity;

276. }

277. }

278. }

279. // 返回当前局面的最佳着法估值

280. if(canmove)return alpha;

281. // 双方都没有可下子之处，返回净胜子数

282. if(pass) return ();

283. // pass 一次，往深搜索

284. =;

285. return -(-beta,-alpha,depth-1,true);

286. }

287. // 精确搜索，这段的算法原理跟 search 是一样的

288. earch=function(alpha,beta,pass){

289. // 已经走了 60 步了，返回净胜子数

290. if(==60)return ();

291. var canmove=false;

292. for(var y=1;y<=8;y++)

293. {

294. for(var x=1;x<=8;x++)

295. {

296. if(this[y*10+x]!=0);//r+=(this[y*10+x]==1?"*":"o")+" ";

297. else

298. {

299. var tmp=(x,y,);

300. if(!tmp)continue;

301. canmove=true;

302. var r=-earch(-beta,-alpha);

303. if(r>=alpha)alpha=r;

304. if(alpha>beta)return Infinity;

305. }

306. }

307. }

308. if(canmove)return alpha;

309. if(pass)return ();

310. =;

311. return -earch(-beta,-alpha,true);

312. }

313. // 尝试在 x, y 放下 颜的棋子，成功返回下一棋盘状态，否则返回

null

314. =function(x,y)

315. {

316. // 复制当前状态

317. var pattern=();

318. =;

319. // 注意这个负号

320. ence=-ence;

321. // move 数++

322. ++;

323. var canmove;

324. canmove=false;

325. // 放在函数入口处，可以优化性能

326. // 把 10*y+x 放入临时变量可优化性能

327. if(pattern[10*y+x]!=0)return null;

328. // 8 方向判断

329. for(var i=0;i<8;i++)

330. {

331. // 转换为一维索引

332. var p=10*y+x+directions[i];

333. // 邻近的格子上棋子不同

334. if(pattern[p]==)

335. while(pattern[p]!=0)

336. {

337. // 往同方向搜索

338. p+=directions[i];

339. // 另一端还有一个自己的棋子，则是一个可走的点。

340. if(pattern[p]==)

341. {

342. canmove=true;

343. // 把中间的棋子翻过来

344. while((p+=-directions[i])!=10*y+x)

345. {

346. pattern[p]=;

347. //alert(p);

348. for(var d=0;d<8;d++)

349. {

350. // 非空

351. if(!pattern[p+directions[d]]

352. // 非边界

353.

&&p+directions[d]>10

354.

&&p+directions[d]<89

355.

&&(p+directions[d])%10!=0

356.

&&(p+directions[d])!=9)

357. // 外围净胜子数增加

358. ence++;

359. }

360. }

361. break;

362. }

363. }

364. }

365. // 返回新的棋盘状态

366. if(canmove){pattern[10*y+x]=;return pattern;}

367. else return null;

368. }

369.}

370.//ype = emptyboard;

371.//(new

pattern().move(5,6).move(6,4).move(4,3).move(3,4).toLocalString(3));

372.//(new pattern().move(5,6).search(-Infinity,Infinity,2));

373.}()

本文来自CSDN博客，转载请标明出处

/lanphaday/archive/2010/11/22/

：