[ create a new paste ] login | about

Link: http://codepad.org/WGeiZWKg    [ raw code | fork ]

C, pasted on Oct 10:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
#include <stdio.h>
#include "misc.h"

inline UCHAR GmGetBoardEx(UCHAR *lpBoard, ULONG x, ULONG y)
{
	if (x <= CELL_COUNT && x >= 0 && y <= CELL_COUNT && y >= 0 ) {
		return lpBoard[x * (CELL_COUNT + 1) + y];
	}
	return CHESS_BAD;
}

inline VOID GmSetBoardEx(UCHAR *lpBoard, ULONG x, ULONG y, UCHAR ucData)
{
	if (x <= CELL_COUNT && y <= CELL_COUNT) {
		lpBoard[x * (CELL_COUNT + 1) + y] = ucData;
	}
	return;
}

UCHAR AiGetInverseChess(UCHAR ucChess)
{
	UCHAR ucReturn;
	if (ucChess == CHESS_BLACK) {
		ucReturn = CHESS_WHITE;
	} else if (ucChess == CHESS_WHITE) {
		ucReturn = CHESS_BLACK;
	} else {
		ucReturn = CHESS_BAD;
	}
	return ucReturn;
}

POS AiGetPosByDirection(POS tPosBase, CHAR cDir)
{
	POS tPos;
	tPos.x = tPosBase.x; tPos.y = tPosBase.y; 
	switch (cDir) {
		case DIR_UP_COLUMN:
			tPos.y--;
			break;
		case DIR_DOWN_COLUMN:
			tPos.y++;
			break;
		case DIR_UP_ROW:
			tPos.x--;
			break;
		case DIR_DOWN_ROW:
			tPos.x++;
			break;
		case DIR_UP_LEFT_DIAGONAL:
			tPos.x--;
			tPos.y--;
			break;
		case DIR_DOWN_LEFT_DIAGONAL:
			tPos.x++;
			tPos.y++;
			break;
		case DIR_UP_RIGHT_DIAGONAL:
			tPos.x++;
			tPos.y--;
			break;
		case DIR_DOWN_RIGHT_DIAGONAL:
			tPos.x--;
			tPos.y++;
			break;
	}
	return tPos;
}

CHAR AiGetInverseDirection(CHAR cDir)
{
	return (-cDir);
}

//
// 取得任意方向连珠数
ULONG AiCountColumnLoop(UCHAR *lpBoard, POS tPos, UCHAR cDir, UCHAR ucChess, BOOLEAN *lpbIsActive, BOOLEAN *lpbIsInterrupt)
{
	UCHAR ucData;
	CHAR cDirInverse = AiGetInverseDirection(cDir);
	UCHAR ucInverse = AiGetInverseChess(ucChess);
	BOOLEAN bIsGap = FALSE;
	*lpbIsActive = TRUE;
	while (1) {
		tPos = AiGetPosByDirection(tPos, cDir);
		ucData = GmGetBoardEx(lpBoard, tPos.x, tPos.y);
		if (ucData != ucChess) {
			POS tPosNext = AiGetPosByDirection(tPos, cDir);
			if (ucData == CHESS_NONE && GmGetBoard(tPosNext.x, tPosNext.y) == ucChess) {
				if (bIsGap) {
					tPos = AiGetPosByDirection(tPos, cDirInverse);
					break;
				} else {
					bIsGap = TRUE;
				}
			} else {
				if (ucData == ucInverse) {
					*lpbIsActive = FALSE;
				}
				tPos = AiGetPosByDirection(tPos, cDirInverse);
				break;
			}
		}
	}

	bIsGap = FALSE;
	*lpbIsInterrupt = FALSE;
	ULONG ulLoop = 1;
	while (1) {
		tPos = AiGetPosByDirection(tPos, cDirInverse);
		ucData = GmGetBoardEx(lpBoard, tPos.x, tPos.y);
		if (ucData != ucChess) {
			POS tPosNext = AiGetPosByDirection(tPos, cDirInverse);
			if (ucData == CHESS_NONE && GmGetBoard(tPosNext.x, tPosNext.y) == ucChess) {
				if (bIsGap) {
					tPos = AiGetPosByDirection(tPos, cDir);
					break;
				} else {
					bIsGap = TRUE;
					*lpbIsInterrupt = TRUE;
				}
			} else {
				if (ucData == ucInverse) {
					*lpbIsActive = FALSE;
				}
				tPos = AiGetPosByDirection(tPos, cDir);
				break;
			}
		} else {
			ulLoop++;
		}
	}

	return ulLoop;
}

BOOLEAN AiIsColumnLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
	BOOLEAN bTemp;
	BOOLEAN bIsInterrupt;
	ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_COLUMN, ucChess, &bTemp, &bIsInterrupt);
	return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}

BOOLEAN AiIsRowLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
	BOOLEAN bTemp;
	BOOLEAN bIsInterrupt;
	ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_ROW, ucChess, &bTemp, &bIsInterrupt);
	return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}

BOOLEAN AiIsDiagonalLeftLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
	BOOLEAN bTemp;
	BOOLEAN bIsInterrupt;
	ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_LEFT_DIAGONAL, ucChess, &bTemp, &bIsInterrupt);
	return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}

BOOLEAN AiIsDiagonalRightLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
	BOOLEAN bTemp;
	BOOLEAN bIsInterrupt;
	ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_RIGHT_DIAGONAL, ucChess, &bTemp, &bIsInterrupt);
	return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}
// ============
//


BOOLEAN AiIsPlayerWin(UCHAR *lpBoard, POS tPos, UCHAR ucChess)
{
	BOOLEAN bIsInterrupt;
	BOOLEAN bLine = AiIsColumnLoop(lpBoard, tPos, ucChess, 5);
	BOOLEAN bRow = AiIsRowLoop(lpBoard, tPos, ucChess, 5);
	BOOLEAN bDiagonalLeft = AiIsDiagonalLeftLoop(lpBoard, tPos, ucChess, 5);
	BOOLEAN bDiagonalRight = AiIsDiagonalRightLoop(lpBoard, tPos, ucChess, 5);
	return ((bLine || bRow || bDiagonalLeft || bDiagonalRight)? TRUE: FALSE); 
}

//
// 取得一个点周围N个有效点,0 <= N <= (ulRange * ulRange - 1)
ULONG AiGetValidPosAroundOneChess(PUCHAR lpBoard, POS tBasePos, PPOS lpValidPos, ULONG ulCount, ULONG lRange)
{
	if (lRange < 1 || lRange > CELL_COUNT * 2) {
		return 0;
	}
	
	lRange /= 2;
	
	BOOLEAN bIsAdded;
	for (LONG i = tBasePos.x - lRange; i < tBasePos.x + lRange; i++) {
		for (LONG j = tBasePos.y - lRange; j < tBasePos.y + lRange; j++) {
			if (GmGetBoardEx(lpBoard, i, j) == CHESS_NONE) {
				bIsAdded = FALSE;
				for (LONG k = ulCount; k >= 0; k--) {
					if (lpValidPos[k].x == i && lpValidPos[k].y == j) {
						bIsAdded = TRUE;
						break;
					}
				}
				if (!bIsAdded) {
					lpValidPos[ulCount].x = i;
					lpValidPos[ulCount].y = j;
					ulCount++;
				}
			}
		}
	}

	return ulCount;
}

// 取得整个棋盘的所有有效点
ULONG AiGetValidPosComplete(PUCHAR lpBoard, PPOS lpValidPos)
{
	ULONG ulCount = 0;
	for (ULONG i = 0; i < CELL_COUNT; i++) {
		for (ULONG j = 0; j < CELL_COUNT; j++) {
			if (GmGetBoardEx(lpBoard, i, j) == CHESS_NONE) {
				lpValidPos[ulCount].x = i;
				lpValidPos[ulCount].y = j;
				ulCount++;
			}
		}
	}
	return ulCount;
}

// 取得所有落子周围的有效点
ULONG AiGetValidPosAround(PUCHAR lpBoard, PPOS lpValidPos)
{
	ULONG ulCount = 0;
	POS tPos;
	for (ULONG i = 0; i < CELL_COUNT; i++) {
		for (ULONG j = 0; j < CELL_COUNT; j++) {
			if (GmGetBoardEx(lpBoard, i, j) != CHESS_NONE) {
				tPos.x = i; tPos.y = j;
				ulCount = AiGetValidPosAroundOneChess(lpBoard, tPos, lpValidPos, ulCount, 4);
			}
		}
	}
	return ++ulCount;
}
// ============
//

//
LONG AiGetTotalScore(UCHAR *lpBoard, POS tPos, UCHAR ucChess)
{
	BOOLEAN bIsActive;
	BOOLEAN bIsInterrupt;
	LONG ulCurrentScore;
	LONG ulTotalScore = 0;
	
	// 横
	for (ULONG i = 0; i < 4; i++) {
		switch (i) {
			case 0:
				// 列连珠
				ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_COLUMN, ucChess, &bIsActive, &bIsInterrupt);
				break;
			case 1:
				// 行连珠
				ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_ROW, ucChess, &bIsActive, &bIsInterrupt);
				break;
			case 2:
				// 左对角线连珠
				ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_LEFT_DIAGONAL, ucChess, &bIsActive, &bIsInterrupt);
				break;
			case 3:
				// 右对角线连珠
				ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_RIGHT_DIAGONAL, ucChess, &bIsActive, &bIsInterrupt);
		}

		if (ulCurrentScore == 1) {   // 如果是一个单独棋子,设为0分
			ulCurrentScore--;
		}
		if (ulCurrentScore == 4) {   // 四连珠
			ulCurrentScore *= 2;
		}
		if (bIsActive) {   // 是否为活连珠
			if (ulCurrentScore == 3) {   // 活三
				ulCurrentScore *= 3;
			} else if (ulCurrentScore == 8) {   // 活四
				ulCurrentScore *= 5;
			}
			ulCurrentScore *= ulCurrentScore;
		}
		if (!bIsInterrupt) {   // 连珠是否有隔断(比如***和* **是不同的)
			ulCurrentScore *= 3;   // 没有隔断权值更高
		} else {
			ulCurrentScore *= 2;
		}

		ulTotalScore += ulCurrentScore;
	}
	return ulTotalScore;
}

// 计算一个点的基本权值
ULONG AiCalculateBaseScore(UCHAR *lpBoard, POS tPos, UCHAR ucChess)
{
	LONG k;   // 代表黑棋或白棋
	if (ucChess == CHESS_WHITE) {
		k = 1;
	} else if (ucChess == CHESS_BLACK) {
		k = -1;
	}

	// 如果形成五连珠(则必胜)
	LONG lScore = k * SCORE_5 * (AiIsPlayerWin(lpBoard, tPos, ucChess));
	if (!lScore) {   // 如果没有分出胜负
		lScore = k * AiGetTotalScore(lpBoard, tPos, ucChess);   // 根据连珠数获取权值
	}

	return lScore;
}

VOID AiGetRandomPos(UCHAR *lpBoard, PPOS lpPos)
{
	UCHAR ucData = 0;
	while (1) {
		randomize();
		lpPos->x = random(CELL_COUNT + 1);
		lpPos->y = random(CELL_COUNT + 1);
		ucData = GmGetBoardEx(lpBoard, lpPos->x, lpPos->y);
		if (ucData == CHESS_NONE) {
			break;
		}
	}
}

/* 
   关键函数:AiGetBestPos
   功能:取得一个一个棋盘上黑子或白子的最佳落子点。采用深度优先搜索。
   可以优化的地方:
    1.采用启发式搜索
    2.采用广度优先搜索
    3.使用多线程
   参数:
	IN - lpBoard - 用于演算的棋盘
	IN - ucChess - 演算棋子(黑棋或白棋,分数值正负不同)
	OUT - lpMaxScore - 最大分
	IN - ulNode - 演算深度(> 1时会进行递归)
   返回值:
	最佳落子点的坐标,以struct _POS形式返回
*/
POS AiGetBestPos(UCHAR *lpBoard, UCHAR ucChess, PLONG lpMaxScore, ULONG ulNode)
{
	POS tPossiblePos[225];
	ULONG ulValidPos = AiGetValidPosAround(lpBoard, tPossiblePos);   // 找到所有比较合理的落子点

	// 先根据棋子颜色把MaxScore设为最低分,以便后面估值
	LONG ulPosBaseScore;
	LONG ulMaxBaseScore = (ucChess == CHESS_BLACK? 65535: -65535);
	LONG ulPosExtraScore;
	LONG ulMaxExtraScore = (ucChess == CHESS_BLACK? 65535: -65535);
	POS tPos;
	for (ULONG i = 0; i < ulValidPos; i++) {
		// 先取得基本分(根据连珠数)
		UCHAR *lpNewBoard = (PUCHAR)malloc((CELL_COUNT + 1) * (CELL_COUNT + 1));
		memcpy(lpNewBoard, lpBoard, (CELL_COUNT + 1) * (CELL_COUNT + 1));
		GmSetBoardEx(lpNewBoard, tPossiblePos[i].x, tPossiblePos[i].y, ucChess);
		ulPosBaseScore = AiCalculateBaseScore(lpNewBoard, tPossiblePos[i], ucChess);
		free(lpNewBoard);
		if (ulNode == 0) {   // 如果已演算到最后一层,则只根据基本分来估值
			//if (ulPosBaseScore != 0) {
				if (((ulPosBaseScore < ulMaxBaseScore) && ucChess == CHESS_BLACK) || ((ulPosBaseScore > ulMaxBaseScore) && ucChess == CHESS_WHITE)) {
					ulMaxBaseScore = ulPosBaseScore;
					tPos.x = tPossiblePos[i].x;
					tPos.y = tPossiblePos[i].y;
				}
			//}
		} else {   // 否则还要演算下一步
			// 递归,取得对手的最佳落子点分数
			UCHAR *lpNewBoard = (PUCHAR)malloc((CELL_COUNT + 1) * (CELL_COUNT + 1));
			memcpy(lpNewBoard, lpBoard, (CELL_COUNT + 1) * (CELL_COUNT + 1));
			GmSetBoardEx(lpNewBoard, tPossiblePos[i].x, tPossiblePos[i].y, ucChess);
			AiGetBestPos(lpNewBoard, AiGetInverseChess(ucChess), &ulPosExtraScore, ulNode - 1);
			free(lpNewBoard);
			
			ulPosExtraScore += ulPosBaseScore;   // 对手的最佳落子点分值加上该点基本分才是该点的最终分(一正一负相加)
			//if (ulPosExtraScore != 0) {
				if (((ulPosExtraScore < ulMaxExtraScore) && ucChess == CHESS_BLACK) || ((ulPosExtraScore > ulMaxExtraScore) && ucChess == CHESS_WHITE)) {
					ulMaxExtraScore = ulPosExtraScore;
					tPos.x = tPossiblePos[i].x;
					tPos.y = tPossiblePos[i].y;
				}
			//}
		}
	}
	if (ulNode == 0) {
		*lpMaxScore = ulMaxBaseScore;
	} else {
		*lpMaxScore = ulMaxExtraScore;
		if (ulMaxExtraScore == (ucChess == CHESS_BLACK? 65535: -65535)) {   // 如果最大分仍是初始化时设置的最低分
			AiGetRandomPos(lpBoard, &tPos);   // 那么就是出错了,随机选择一个落子点(正常情况不会走到这一步)
		}
	}

	return tPos;   // 返回最佳落子点
}


Create a new paste based on this one


Comments: