中国象棋

总体介绍

概述
前期准备
完成情况

源代码

1. 总体介绍

概述

这个程序是在学校的时候无聊写的,后面好多优化算法也都没有加上,想看逻辑部分的同学可以直接在网页上看,运行源代码需要安装Qt,下面有编译好的文件的链接。

运行效果

前期准备

完成情况

实现了的算法

  • 阿尔法贝塔剪枝

  • 置换表剪枝算法

未实现的算法

  • 时间控制策略算法
  • 杀手启发算法
  • 历史表启发算法
  • 克服水平线效应算法
  • 走法库算法

搜索深度

  • 四层深度可以立即完成

  • 六层深度可以在一分钟内完成

  • 奇数搜索深度可能会出问题(雾

2. 源代码(逻辑部分)

头文件

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
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
#pragma once
#define MAXDEPTH 4
#define SCORENAN 99999
#define _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS

#include <QDebug>
#include <hash_map>
#include <random>
#include <time.h>

/*
红方: 帅 仕 仕 相 相 马 马 车 车 炮 炮 兵
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
*/

//走棋结构体(每一个位置用一个数字表示)
typedef struct {
short from, to;
//被吃棋子(在搜索过程中生成)
int capture;
}move;

//置换表结构体
typedef struct{
int score;
int depth;
}station;

class Board {
protected:
#pragma region 数据定义
//棋盘表示
int board[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,//48
0,0,0,39,37,35,33,32,34,36,38,40,0,0,0,0,//64
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,41,0,0,0,0,0,42,0,0,0,0,0,
0,0,0,43,0,44,0,45,0,46,0,47,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,27,0,28,0,29,0,30,0,31,0,0,0,0,
0,0,0,0,25,0,0,0,0,0,26,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,23,21,19,17,16,18,20,22,24,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};
const int LegalPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

//棋方标志 0=>红色 1=>黑色
int side = 0;
bool Defeat = false;
bool Victory = false;

//走法数组(为搜索准备多个走法组)
move MoveArray[MAXDEPTH][128];
int MoveNum[MAXDEPTH];
int Depth = 0;

//走法生成辅助数组(空间换取时间)
const int KnightDir[8] = { 0x0e, -0x12, -0x21, -0x1f, -0x0e, 0x12, 0x21, 0x1f };
const int KnightCheck[8] = { -0x01, -0x01, -0x10, -0x10, 0x01, 0x01, 0x10, 0x10 };
const int KnightAttackCheck[8] = { 0x0f, -0x11, -0x11, -0x0f, -0x0f, 0x11, 0x11, 0x0f };
const int KnightPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

const int BishopDir[4] = { 0x22, 0x1e, -0x22, -0x1e };
const int BishopCheck[4] = { 0x11, 0x0f, -0x11, -0x0f };
const int BishopPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

const int KingDir[4] = { 0x01, 0x10, - 0x01, -0x10 };
const int KingPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,//48
0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,//51
0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,//67
0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,//83
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,//99
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,//115
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,//131
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,//147
0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,//163
0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,//179
0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,//195
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

const int AdvisorDir[4] = { 0x11, 0x0f, -0x11, -0x0f };
const int AdvisorPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

const int RookDir[4] = { 0x01, 0x10, -0x01, -0x10 };
const int RookPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

const int CannonDir[4] = { 0x01, 0x10, -0x01, -0x10 };
const int CannonPosition[256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,//160
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

const int SoldierDir[2][3] = { 0x01,-0x10,-0x01,0x01,0x10,-0x01 };
const int SoldierPostion[2][256] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,
0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,
0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

short pieces[48] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
199,198,200,197,201,196,202,195,203,164,170,147,149,151,153,155,
55,54,56,53,57,52,58,51,59,84,90,99,101,103,105,107,
};

//局面评估辅助数组
const int Locate[48] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,2,2,3,3,4,4,5,5,6,6,6,6,6,
0,1,1,2,2,3,3,4,4,5,5,6,6,6,6,6,
};
const short PieceToValue[2][7][256] = {
//红方
{
{//帅
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1005,1005,1005,0,0,0,0,0,0,0,
0,0,0,0,0,0,1010,1010,1010,0,0,0,0,0,0,0,
0,0,0,0,0,0,1015,1020,1015,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//仕
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//相
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,25,0,0,0,25,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,20,0,0,0,35,0,0,0,20,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,30,0,0,0,30,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//马
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,70,80,90,80,70,80,90,80,70,0,0,0,0,
0,0,0,80,110,125,90,70,90,125,110,80,0,0,0,0,
0,0,0,90,100,120,125,120,125,120,100,90,0,0,0,0,
0,0,0,90,100,120,130,110,130,120,100,90,0,0,0,0,
0,0,0,90,110,110,120,100,120,110,110,90,0,0,0,0,
0,0,0,90,100,100,110,100,110,100,100,90,0,0,0,0,
0,0,0,80,90,100,100,90,100,100,90,80,0,0,0,0,
0,0,0,80,80,90,90,80,90,90,80,80,0,0,0,0,
0,0,0,70,75,75,70,50,70,75,70,60,0,0,0,0,
0,0,0,60,70,75,70,60,75,75,70,60,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//车
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,160,170,160,150,150,150,160,170,160,0,0,0,0,
0,0,0,170,180,170,190,250,190,170,180,170,0,0,0,0,
0,0,0,170,190,200,220,240,220,200,190,170,0,0,0,0,
0,0,0,180,220,210,240,250,240,210,220,180,0,0,0,0,
0,0,0,180,220,210,240,250,240,210,220,180,0,0,0,0,
0,0,0,180,220,210,240,250,240,210,220,180,0,0,0,0,
0,0,0,170,190,180,220,240,220,200,190,170,0,0,0,0,
0,0,0,170,180,170,170,160,170,170,180,170,0,0,0,0,
0,0,0,160,170,160,160,150,160,160,170,160,0,0,0,0,
0,0,0,150,160,150,160,150,160,150,160,150,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//炮
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,125,130,100,70,60,70,100,130,125,0,0,0,0,
0,0,0,110,125,100,70,60,70,100,125,110,0,0,0,0,
0,0,0,100,120,90,80,80,80,90,120,100,0,0,0,0,
0,0,0,90,110,90,110,130,110,90,110,90,0,0,0,0,
0,0,0,90,110,90,110,130,110,90,110,90,0,0,0,0,
0,0,0,90,100,90,110,130,110,90,100,90,0,0,0,0,
0,0,0,90,100,90,90,110,90,90,100,90,0,0,0,0,
0,0,0,90,100,80,80,70,80,80,100,90,0,0,0,0,
0,0,0,80,90,80,70,65,70,80,90,80,0,0,0,0,
0,0,0,80,90,80,70,60,70,80,90,80,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//兵
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,10,10,10,20,25,20,10,10,10,0,0,0,0,
0,0,0,25,30,40,50,60,50,40,30,25,0,0,0,0,
0,0,0,25,30,30,40,40,40,30,30,25,0,0,0,
0,0,0,20,25,25,30,30,30,25,25,20,0,0,0,0,
0,0,0,15,20,20,20,20,20,20,20,15,0,0,0,0,
0,0,0,10,0,15,0,15,0,15,0,10,0,0,0,0,
0,0,0,10,0,10,0,15,0,10,0,10,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
},
//黑方
{
{//将
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1015,1020,1015,0,0,0,0,0,0,0,
0,0,0,0,0,0,1010,1010,1010,0,0,0,0,0,0,0,
0,0,0,0,0,0,1005,1005,1005,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//士
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//象
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,30,0,0,0,30,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,20,0,0,0,35,0,0,0,20,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,25,0,0,0,25,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//马
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,60,70,75,70,60,75,75,70,60,0,0,0,0,
0,0,0,70,75,75,70,50,70,75,70,60,0,0,0,0,
0,0,0,80,80,90,90,80,90,90,80,80,0,0,0,0,
0,0,0,80,90,100,100,90,100,100,90,80,0,0,0,0,
0,0,0,90,100,100,110,100,110,100,100,90,0,0,0,0,
0,0,0,90,110,110,120,100,120,110,110,90,0,0,0,0,
0,0,0,90,100,120,130,110,130,120,100,90,0,0,0,0,
0,0,0,90,100,120,125,120,125,120,100,90,0,0,0,0,
0,0,0,80,110,125,90,70,90,125,110,80,0,0,0,0,
0,0,0,70,80,90,80,70,80,90,80,70,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//车
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,150,160,150,160,150,160,150,160,150,0,0,0,0,
0,0,0,160,170,160,160,150,160,160,170,160,0,0,0,0,
0,0,0,170,180,170,170,160,170,170,180,170,0,0,0,0,
0,0,0,170,190,180,220,240,220,200,190,170,0,0,0,0,
0,0,0,180,220,210,240,250,240,210,220,180,0,0,0,0,
0,0,0,180,220,210,240,250,240,210,220,180,0,0,0,0,
0,0,0,180,220,210,240,250,240,210,220,180,0,0,0,0,
0,0,0,170,190,200,220,240,220,200,190,170,0,0,0,0,
0,0,0,170,180,170,190,250,190,170,180,170,0,0,0,0,
0,0,0,160,170,160,150,150,150,160,170,160,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//炮
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,80,90,80,70,60,70,80,90,80,0,0,0,0,
0,0,0,80,90,80,70,65,70,80,90,80,0,0,0,0,
0,0,0,90,100,80,80,70,80,80,100,90,0,0,0,0,
0,0,0,90,100,90,90,110,90,90,100,90,0,0,0,0,
0,0,0,90,110,90,110,130,110,90,110,90,0,0,0,0,
0,0,0,90,110,90,110,130,110,90,110,90,0,0,0,0,
0,0,0,90,100,90,110,130,110,90,100,90,0,0,0,0,
0,0,0,100,120,90,80,80,80,90,120,100,0,0,0,0,
0,0,0,110,125,100,70,60,70,100,125,110,0,0,0,0,
0,0,0,125,130,100,70,60,70,100,130,125,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
{//卒
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,10,0,10,0,15,0,10,0,10,0,0,0,0,
0,0,0,10,0,15,0,15,0,15,0,10,0,0,0,0,
0,0,0,15,20,20,20,20,20,20,20,15,0,0,0,0,
0,0,0,20,25,25,30,30,30,25,25,20,0,0,0,0,
0,0,0,25,30,30,40,40,40,30,30,25,0,0,0,
0,0,0,25,30,40,50,60,50,40,30,25,0,0,0,0,
0,0,0,10,10,10,20,25,20,10,10,10,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
},
}

};

//走法栈(在搜索的时候可能会用到,最大深度与最大搜索深度一致)
move MoveStack[48];
int StackTop = 0;
move BestMove;
const int MaxValue = 9000;

//为了最大化剪枝算法的效果,用于更改走法生成顺序的辅助数组
/* 0 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
*/
int GenOrder[16] = {7,8,5,6,9,10,3,4,1,2,0,11,12,13,14,15};

//置换表map,全局局面变量,局面随机数,棋子随机数
std::hash_map<long int,station> HashTable;
long int PresentStation;
long int BoardNum[256];
long int PieceNum[48];
long int SideNum;

#pragma endregion


#pragma region 其他函数
public:
Board() {
//初始化置换表相关数据
srand(time(NULL));
for(int i=0;i<256;i++){
BoardNum[i] = rand()^((long)rand()<<15)^((long)rand()<<30);
}
for(int i=0;i<48;i++){
PieceNum[i] = rand()^((long)rand()<<15)^((long)rand()<<30);
}
\
PresentStation = rand()^((long)rand()<<15)^((long)rand()<<30);

SideNum = rand()^((long)rand()<<15)^((long)rand()<<30);
}
protected:
void ChangeSide() { side = 1 - side; }
#pragma endregion


#pragma region 走法生成

//走法生成
void GenAllMove();
void InitGen();
void SaveMove( int from, int to);

//具体棋子走法生成
void KnightMove( int p);
void BishopMove( int p);
void KingMove( int p);
void AdvisorMove( int p);
void RookMove( int p);
void CannonMove( int p);
void SoldierMove( int p);

//将军检测(传入被检测方的标志)
int check(int ISide);
#pragma endregion


#pragma region 局面评估
//基本价值评估 => 带棋子数组评估 => 多重棋子价值数组
// => 位置分数 => 灵活性分数
//传入当前
short Eval();
#pragma endregion


#pragma region 走法搜索
//最大最小值搜索 => alpha-beta剪枝搜索 => 缓存/优化/算杀搜索
//负极大值搜索与最大最小值效果相近
bool MakeMove(move m);
void UnMakeMove();
public:
int BoardSearch(int depth);

private:
//树搜索算法
int MaxSearch(int depth);
int MinSearch(int depth);

//阿尔法贝塔剪枝算法
int AlphaBetaSearch(int depth,int alpha, int beta);
int AlphaSearch(int depth,int alpha, int beta);
int BetaSearch(int depth, int alpha, int beta);

#pragma endregion


#pragma region 哈希表优化
//搜索前初始化
void ClearZobrist(){
HashTable.clear();
}
int ReadHashTable(); //读取哈希值
void SaveHashTable(int value); //保存局面的分数



#pragma endregion


public:
//人类棋手下棋
move H_Player(int from_x,int from_y,int to_x,int to_y){
move HMove;
HMove.from = from_x + 3 + (from_y + 3) * 16;
HMove.to = to_x + 3 + (to_y + 3) * 16;
HMove.capture = board[HMove.to];
MakeMove(HMove);
StackTop--;

return C_Player();
}

private:
//电脑下棋
move C_Player(){

int score = BoardSearch(MAXDEPTH);
MakeMove(BestMove);
StackTop--;

if(score<-8000){
qDebug("defeat,score is %d", score);
Defeat = true;
}
if(!pieces[side*16+16]){
qDebug("victory,score is %d", score);
Victory = true;
}

qDebug("the move is %d, %d", BestMove.from, BestMove.to);

return BestMove;
}
};


cpp文件

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
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
#include "board.h"
#include <QtDebug>

//马的走法生成
void Board::KnightMove( int p){
int SideTag = 16 + side * 16;
int NextPosition;

for (int i = 0; i < 8; i++) {
NextPosition = p + KnightDir[i];

//下一位置合法(且马脚没有被蹩)
if (KnightPosition[NextPosition] && !board[p + KnightCheck[i]]) {

//目标位置无己方子
if (!(board[NextPosition] & SideTag))
SaveMove(p, NextPosition);
}
}
}

//象相的走法生成
void Board::BishopMove(int p){
int SideTag = 16 + side * 16;
int NextPosition;

for (int i = 0; i < 4; i++) {
NextPosition = p + BishopDir[i];

//下一位置合法(且象眼没有被赌)
if (BishopPosition[NextPosition] && !board[p + BishopCheck[i]]) {

//目标位置无己方子
if (!(board[NextPosition] & SideTag))
SaveMove(p, NextPosition);
}
}
}

//帅将的走法生成s
void Board::KingMove(int p){
int SideTag = 16 + side * 16;
int NextPosition;

for (int i = 0; i < 4; i++) {
NextPosition = p + KingDir[i];

//下一个位置合法
if (KingPosition[NextPosition]) {
//目标位置无己方子
if (!(board[NextPosition] & SideTag))
SaveMove(p, NextPosition);
}
}

}

//仕士的走法生成
void Board::AdvisorMove( int p){
int SideTag = 16 + side * 16;
int NextPosition;

for (int i = 0; i < 4; i++) {
NextPosition = p + AdvisorDir[i];

//下一个位置合法
if (AdvisorPosition[NextPosition]) {
//目标位置无己方子
if (!(board[NextPosition] & SideTag))
SaveMove(p, NextPosition);
}
}
}

//车的走法生成
void Board::RookMove( int p){
int SideTag = 16 + side * 16;
int NextPosition;

//遍历四个方向
for (int i = 0; i < 4; i++) {
NextPosition = p;

for (int j = 0; j < 9; j++) {
NextPosition = NextPosition + RookDir[i];

//下一位置是否合法
if (!RookPosition[NextPosition])
break;

//下一位置是否有子
if (!board[NextPosition]) {
//不吃子走法
SaveMove(p,NextPosition);
continue;
}
else {
//下一位置是自己方的子
if (board[NextPosition] & SideTag) {
break;
}
else {
//吃子走法
SaveMove(p, NextPosition);
break;
}
}
}

}
}

//炮的走法生成
void Board::CannonMove( int p){
int SideTag = 16 + side * 16;
int OverTag = 0;
int NextPosition;


//遍历四个方向
for (int i = 0; i < 4; i++) {
NextPosition = p;
OverTag = 0;

for (int j = 0; j < 9; j++) {
NextPosition = NextPosition + RookDir[i];

//下一位置是否合法
if (!CannonPosition[NextPosition])
break;

//下一位置无子
if (!board[NextPosition]) {

//未翻山
if (!OverTag) {
//不吃子走法
SaveMove(p, NextPosition);
continue;
}

}
//下一位置有子(若已翻山则处理完后推出循环)
else {
//未翻山
if (!OverTag) {
OverTag = 1;
}
else {
//下一位置是对面的子
if (!(board[NextPosition] & SideTag)) {
//吃子走法
SaveMove(p, NextPosition);
}
break;
}

}
}

}
}

//兵卒的走法生成(处理时使用不同方式)
void Board::SoldierMove( int p){
//side同时作为走法数组下标 0=>红棋 1=>黑棋
int SideTag = 16 + side * 16;
int NextPosition;

//遍历三个方向
for (int i = 0; i < 3; i++) {
NextPosition = p + SoldierDir[side][i];

//下一位置合法
if (SoldierPostion[side][NextPosition]) {
if (!(board[NextPosition] & SideTag))
SaveMove(p,NextPosition);
}
}
}


//生成走法
void Board::GenAllMove(){
int Position;
int sideTag = 16 + 16 * side;
int piece;
InitGen();

for (int i = 0; i < 16; i++) {
piece = sideTag + i;
//piece = sideTag + GenOrder[i];
Position = pieces[piece];

if (Position == 0) {
continue;
}


switch (i){
//switch (GenOrder[i]){
case 0: //帅
KingMove(Position);
break;
case 1: //仕
case 2:
AdvisorMove(Position);
break;
case 3: //相
case 4:
BishopMove(Position);
break;
case 5: //马
case 6:
KnightMove(Position);
break;
case 7: //车
case 8:
RookMove(Position);
break;
case 9: //炮
case 10:
CannonMove(Position);
break;
case 11: //兵
case 12:
case 13:
case 14:
case 15:
SoldierMove(Position);
break;
}

}

}
void Board::InitGen() {
MoveNum[Depth] = 0;
}
void Board::SaveMove( int from, int to){

int temp[2];
temp[0] = board[from];
temp[1] = board[to];

//假设执行
board[to] = board[from];
board[from] = 0;
pieces[temp[0]] = to;
pieces[temp[1]] = 0;

if (!check(side)) {
MoveArray[Depth][MoveNum[Depth]].from = from;
MoveArray[Depth][MoveNum[Depth]].to = to;
MoveArray[Depth][MoveNum[Depth]].capture = temp[1];
MoveNum[Depth]++;
}

//撤销假设
board[from] = temp[0];
board[to] = temp[1];
pieces[temp[0]] = from;
pieces[temp[1]] = to;

}

//将军检测 (ISide为被检测方)
int Board::check(int ISide){

//不灵敏的子
//炮 车 兵
//灵敏的子
//马
//更正的子
//车 炮 兵

//将帅位置
int RedKing = pieces[16];
int BlackKing = pieces[32];
int PosAdd;
bool result = false;
int SideTag = 32 - 16 * ISide; //对面方的标志

//这个沙雕判定会导致不去吃对面的将
//胜负已定
//if (!RedKing || !BlackKing)
// return true;
//到底要不要加上这个判定......
//试了试感觉不加上也可以,可以正确判定

//检测将帅是否照面
//双方将帅在同一列
if ((BlackKing % 16) == (RedKing % 16)) {

//假设双方直接照面
result = true;
//依次检测每一行是否有子
for (int i = RedKing - 16; i != BlackKing; i -= 16) {
if (board[i]) {
//没有直接照面 将result置为0
result = false;
break;
}
}
//双方将帅照面
if(result)
return true;
}

//获取被检测将位置
int Position = pieces[16 + 16 * ISide];

//马检测
{
//敌对方马(角色值)
int dangerous[2] = {SideTag + 5, SideTag + 6};

//检测有威胁的位置是否有马
for (int i = 0; i < 8; i++) {
if ((board[Position + KnightDir[i]] == dangerous[0]) || (board[Position + KnightDir[i]] == dangerous[1])) {
//马脚没有被蹩
if (!board[Position + KnightAttackCheck[i]])
return true;
}
}
}

//车检测
{
//敌对方车(位置值)
int dangerous[2] = { pieces[SideTag + 7], pieces[SideTag + 8] };

//对两个车进行将军检测(行检测和列检测)
for (int j = 0; j < 2; j++) {

//车被吃掉则跳过(woc原来错在这儿,失掉一个子之后另一个子的判定会失效)
if (!dangerous[j])
continue;
//break;

//列检测
if ((Position % 16) == (dangerous[j] % 16)) {
result = true;

PosAdd = (dangerous[j]>Position) ? 16 : -16;
for (int i = Position + PosAdd; i != dangerous[j]; i += PosAdd) {

//车和将之间有子隔着
if (board[i]) {
result = false;
break;
}

}
if (result)
return true;
}

//行检测
if ((Position / 16) == (dangerous[j] / 16)) {
result = true;

PosAdd = (dangerous[j] > Position) ? 1 : -1;
for (int i = Position + PosAdd; i != dangerous[j]; i += PosAdd) {
if (board[i]) {
result = false;
break;
}
}
if (result)
return true;
}
}

}

//炮检测
{
//敌对方炮(位置值)
int dangerous[2] = { pieces[SideTag + 9], pieces[SideTag + 10] };
int OverFlag = 0;
for (int j = 0; j < 2; j++) {

//炮被吃掉则跳过(woc原来错在这儿,失掉一个子之后另一个子的判定会失效)
if (!dangerous[j])
continue;
//break;

//列检测
if ((Position % 16) == (dangerous[j] % 16)) {
OverFlag = 0;
PosAdd = (dangerous[j] > Position) ? 16 : -16;
for (int i = Position + PosAdd; i != dangerous[j]; i += PosAdd) {
if (board[i]) {
OverFlag++;
}
}
if (OverFlag==1)
return true;
}

//行检测
if ((Position / 16) == (dangerous[j] / 16)) {
OverFlag = 0;
PosAdd = (dangerous[j] > Position) ? 1 : -1;
for (int i = Position + PosAdd; i != dangerous[j]; i += PosAdd) {
if (board[i]) {
OverFlag++;
}
}
if (OverFlag==1)
return true;
}
}
}

//卒检测
{
//敌对方卒(位置值)
int dangerous[5] = { pieces[SideTag + 11],pieces[SideTag + 12],
pieces[SideTag + 13], pieces[SideTag + 14],
pieces[SideTag + 15] };
for (int j = 0; j < 5; j++) {
//(woc原来错在这儿,失掉一个子之后另一个子的判定会失效)
if (!dangerous[j])
continue;
//break;

for (int i = 0; i < 3; i++) {
if (Position == dangerous[j] + SoldierDir[ISide][i])
return true;
}
}

}

return false;
}
/*
* 事先估计没有实现
*/

//局面评价函数
short Board::Eval() {
//双方分数
short BlackValue = 0;
short RedValue = 0;

//红色方分数统计
for (int i = 16; i < 32; i++) {
if (pieces[i] >= 0)
RedValue += PieceToValue[0][Locate[i]][pieces[i]];
}

//黑色方分数统计
for (int i = 32; i < 48; i++) {
if (pieces[i] >= 0)
BlackValue += PieceToValue[1][Locate[i]][pieces[i]];
}

//默认为电脑方为黑棋,后期改进的时候需要考虑电脑方为红棋的情况
//适用于搜索树和分离式剪枝算法的返回值
return BlackValue - RedValue;
//return RedValue - BlackValue;
//适用于剪枝算法的评价返回值
//return side?(RedValue - BlackValue):(BlackValue - RedValue);
}


/*
* 多重棋子价值、灵活性分数未实现
*/


//走法执行函数
bool Board::MakeMove(move m) {
int captrue = board[m.to];

//设置置换表参数
PresentStation = PresentStation ^ (PieceNum[board[m.from]]&BoardNum[m.from]);
PresentStation = PresentStation ^ (PieceNum[board[m.from]]&BoardNum[m.to]);
if(captrue){
PresentStation = PresentStation ^ (PieceNum[captrue]&BoardNum[m.to]);
}
PresentStation = PresentStation ^ SideNum;


//设置走法栈
MoveStack[StackTop].from = m.from;
MoveStack[StackTop].to = m.to;
MoveStack[StackTop].capture = board[m.to];
StackTop++;

//设置棋子数组
if (captrue > 0)
pieces[captrue] = 0;
pieces[board[m.from]] = m.to;

//设置棋盘数组
board[m.to] = board[m.from];
board[m.from] = 0;

ChangeSide();
return captrue == (side ? 32 : 16);
}

void Board::UnMakeMove(){

StackTop--;
int from = MoveStack[StackTop].from;
int dest = MoveStack[StackTop].to;
int capture = MoveStack[StackTop].capture;


//设置置换表参数
PresentStation = PresentStation ^ (PieceNum[board[dest]]&BoardNum[from]);
PresentStation = PresentStation ^ (PieceNum[board[dest]]&BoardNum[dest]);
if(capture){
PresentStation = PresentStation ^ (PieceNum[capture]&BoardNum[dest]);
}
PresentStation = PresentStation ^ SideNum;


//设置棋盘数组
board[from] = board[dest];
board[dest] = capture;

//设置棋子数组
if (capture > 0)
pieces[capture] = dest;
pieces[board[from]] = from;
ChangeSide();
}

//搜索算法入口
int Board::BoardSearch(int depth){
//改为吃子后清空置换表
//ClearZobrist();

//执行树搜索
//return MaxSearch(depth);

//执行阿尔法贝塔剪枝搜索
int score = AlphaBetaSearch(depth, -MaxValue, MaxValue);
if(BestMove.capture)
ClearZobrist();
return score;

//执行分离形式阿尔法贝塔剪枝搜索
//return AlphaSearch(depth, -MaxValue, MaxValue);
}


//树搜索算法
int Board::MaxSearch(int depth) {

if (depth == 0) {
return Eval();
}

int best = -MaxValue;
move mv;
int value = 0;

//在当前层生成所有走法
GenAllMove();
int Num = MoveNum[Depth];

for (int i = 0; i < Num; i++) {
mv = MoveArray[Depth][i];

//切换到下一搜索层
Depth++;

MakeMove(mv);
value = MinSearch(depth - 1);
UnMakeMove();

//返回到上一搜索层
Depth--;

if (value > best) {
best = value;
//如果当前层是第一层,则生成直接最佳走法
if (depth == MAXDEPTH) {
BestMove = mv;
}
}
}

return best;
}

int Board::MinSearch(int depth){
if (depth == 0) {
return Eval();
}

int best = MaxValue;
move mv;
int value = 0;

//在当前层生成所有走法
GenAllMove();
int Num = MoveNum[Depth];

for (int i = 0; i < Num; i++) {
mv = MoveArray[Depth][i];

//切换到下一搜索层
Depth++;

MakeMove(mv);
value = MaxSearch(depth - 1);
UnMakeMove();

//返回到上一搜索层
Depth--;

if (value < best) {
best = value;
//如果当前层是第一层,则生成直接最佳走法
if (depth == MAXDEPTH) {
BestMove = mv;
}
}
}

return best;
}


//阿尔法贝塔剪枝算法(已加入置换表)
int Board::AlphaBetaSearch(int depth, int alpha, int beta){
if (depth == 0) {
return Eval();
}

move mv;
int value = ReadHashTable();
if(value != SCORENAN){
return value;
}

//在当前层生成所有走法
GenAllMove();
int Num = MoveNum[Depth];

for (int i = 0; i < Num; i++) {
mv = MoveArray[Depth][i];

//切换到下一搜索层
Depth++;

MakeMove(mv);
value = -AlphaBetaSearch(depth-1,-beta,-alpha);
UnMakeMove();

//返回到上一搜索层
Depth--;

if(value>=beta){
SaveHashTable(beta);
return beta;
}

if(value>alpha){
alpha = value;
SaveHashTable(alpha);
if(depth==MAXDEPTH)
BestMove = mv;
}
}

return alpha;
}

//分离形式的阿尔法贝塔剪枝
//寻找当前层最大值
int Board::AlphaSearch(int depth, int alpha, int beta){
if (depth == 0) {
return Eval();
}

move mv;
int value = 0;

//在当前层生成所有走法
GenAllMove();
int Num = MoveNum[Depth];

for (int i = 0; i < Num; i++) {
mv = MoveArray[Depth][i];

//切换到下一搜索层
Depth++;

MakeMove(mv);
value = BetaSearch(depth-1,alpha,beta);
UnMakeMove();

//返回到上一搜索层
Depth--;

if(value>=beta)
return value;

if(value>alpha){
alpha = value;
if(depth==MAXDEPTH)
BestMove = mv;
}
}

return alpha;
}
//寻找当前层最小值
int Board::BetaSearch(int depth, int alpha, int beta){
if (depth == 0) {
return Eval();
}

move mv;
int value = 0;

//在当前层生成所有走法
GenAllMove();
int Num = MoveNum[Depth];

for (int i = 0; i < Num; i++) {
mv = MoveArray[Depth][i];

//切换到下一搜索层
Depth++;

MakeMove(mv);
value = AlphaSearch(depth-1,alpha,beta);
UnMakeMove();

//返回到上一搜索层
Depth--;

if(value<=alpha)
return value;

if(value<beta){
beta = value;
if(depth==MAXDEPTH)
BestMove = mv;
}
}

return beta;
}


//置换表相关函数
int Board::ReadHashTable(){
//查找
std::hash_map<long,station>::iterator temp = HashTable.find(PresentStation);

//找到相关信息
if(temp!=HashTable.end()){
if(temp->second.depth<=Depth)
return temp->second.score;
}
return SCORENAN;
}

void Board::SaveHashTable(int value){
station temp;
temp.score = value;
temp.depth = Depth;
HashTable[PresentStation] = temp;
}