1
/****************************************************************************
3
* Velena Source Code V1.0 *
4
* Written by Giuliano Bertoletti *
5
* Based on the knowledged approach of Louis Victor Allis *
6
* Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR *
8
****************************************************************************
10
Portable engine version.
11
read the README file for further informations.
13
============================================================================
15
Changes have been made to this code for inclusion with Gnect. It is
16
released under the GNU General Public License with Giuliano's approval.
17
The original and complete Velena Engine source code can be found at:
19
http://www.ce.unipr.it/~gbe/velena.html
38
/* FIXME: These should probably go into a header file or be defined as static */
40
short whatfight (void);
41
void her_generate_all_children (struct node *node);
42
void her_free_whole_tree (struct bintree *tree);
43
short her_evaluate (struct node *node);
44
short her_resources_available (long maxnodes);
45
struct node *her_select_most_proving_node (struct node *node,
47
void her_set_pdv_according_to_children (struct node *node);
48
void her_set_proof_and_disproof_numbers (struct node *node);
49
void her_develop_node (struct node *node);
50
void her_update_ancestors (struct node *node);
51
void her_pn_search (struct node *root, long maxnodes, struct info *info);
52
short heuristic_search (struct node *mynode, long maxnodenum);
53
short heuristic_play_best (struct board *board, long maxnodenum);
56
extern short nodeseq[];
57
struct board *auxboard;
60
struct bintree *streeroot;
61
struct node *rootnode;
63
short nodeseq[] = { 3, 2, 4, 5, 1, 0, 6 }; /* This is the sequence we follow to
64
* scan the seven moves available
67
char fight_for_win = 0;
82
return (short) fight_for_win;
87
long her_node_expanded, her_node_not_expanded;
92
her_generate_all_children (struct node *node)
94
struct node *dummy, *symm;
95
short x, y, x1, y1, backtrace;
98
for (x = 0; x < BOARDX; x++) {
100
fatal_error ("Tried to allocate a node twice!");
101
else if (node->stack[x] < BOARDY) {
102
node->child[x] = (struct node *) malloc (sizeof (struct node));
103
symm = (struct node *) malloc (sizeof (struct node));
105
if (!node->child[x] || !symm)
106
fatal_error ("Not enough memory to build the tree");
108
memcpy (node->child[x]->square, node->square,
109
(BOARDX + 1) * (BOARDY + 2));
110
memcpy (node->child[x]->stack, node->stack, BOARDX + 1);
113
node->child[x]->square[ELM (x, node->child[x]->stack[x]++)] =
115
node->child[x]->turn = node->turn ^ SWITCHSIDE;
116
symm->turn = node->turn ^ SWITCHSIDE;
118
for (y1 = 0; y1 < BOARDY; y1++) {
119
symm->square[ELM (BOARDX, y1)] =
120
node->child[x]->square[ELM (BOARDX, y1)];
121
for (x1 = 0; x1 < BOARDX; x1++)
122
symm->square[ELM (x1, y1)] =
123
node->child[x]->square[ELM (BOARDX - x1 - 1, y1)];
126
symm->stack[BOARDX] = node->child[x]->stack[BOARDX];
127
for (x1 = 0; x1 < BOARDX; x1++)
128
symm->stack[x1] = node->child[x]->stack[BOARDX - x1 - 1];
130
if (bin_compare (symm->square, node->child[x]->square) > 0) {
132
symm = node->child[x];
133
node->child[x] = dummy;
134
backtrace = BOARDX - x - 1;
137
dummy = fast_check_node (streeroot, node->child[x], 0);
139
free (node->child[x]);
140
node->child[x] = dummy;
141
node->child[x]->parent[backtrace] = node;
142
her_node_not_expanded++;
144
node->child[x]->expanded = NO;
145
node->child[x]->evaluated = NO;
147
for (y = 0; y < BOARDX; y++)
148
node->child[x]->parent[y] = NULL;
150
node->child[x]->parent[backtrace] = node;
152
for (y = 0; y < BOARDX; y++)
153
node->child[x]->child[y] = NULL;
157
if (node->type == AND_TYPE)
158
node->child[x]->type = OR_TYPE;
159
else if (node->type == OR_TYPE)
160
node->child[x]->type = AND_TYPE;
162
fatal_error ("Could not recognize node type!");
164
/*add_node(streeroot,node->child[x]); */
167
node->symmetric[x] = backtrace;
172
node->child[x] = NULL;
179
her_free_whole_tree (struct bintree *tree)
184
her_free_whole_tree (tree->lson);
186
her_free_whole_tree (tree->rson);
194
her_evaluate (struct node *node)
199
node->evaluated = YES;
201
for (x = 0; x < 64; x++)
202
auxboard->square[x] = (short) node->square[x];
204
auxboard->turn = node->turn;
205
auxboard->filled = 0;
207
for (x = 0; x < BOARDX + 1; x++) {
208
auxboard->stack[x] = (short) node->stack[x];
210
auxboard->filled += auxboard->stack[x];
213
if (auxboard->filled == MAXMEN) {
214
if (rootnode->turn == WHITE) {
215
if (!fight_for_win) {
216
if (rootnode->type == OR_TYPE)
217
node->value = DISPROVED;
219
node->value = PROVED;
221
if (rootnode->type == OR_TYPE)
222
node->value = PROVED;
224
node->value = DISPROVED;
227
if (!fight_for_win) {
228
if (rootnode->type == OR_TYPE)
229
node->value = PROVED;
231
node->value = DISPROVED;
233
if (rootnode->type == OR_TYPE)
234
node->value = DISPROVED;
236
node->value = PROVED;
242
bestmove = fast_try_to_win (auxboard);
243
if (bestmove != -1) {
244
if (node->type == OR_TYPE)
245
node->value = PROVED;
246
if (node->type == AND_TYPE)
247
node->value = DISPROVED;
251
node->value = UNKNOWN;
259
her_resources_available (long maxnodes)
261
if (her_node_expanded > maxnodes)
269
her_select_most_proving_node (struct node *node, struct info *info)
271
short i, flag, depth = 0;
274
while (node->expanded) {
278
switch (node->type) {
281
if (node->child[nodeseq[i]] &&
282
node->child[nodeseq[i]]->proof == node->proof)
286
} while (i < BOARDX && !flag);
289
fatal_error ("Could not find a good OR child!");
294
if (node->child[nodeseq[i]] &&
295
node->child[nodeseq[i]]->disproof == node->disproof)
299
} while (i < BOARDX && !flag);
302
fatal_error ("Could not find a good AND child!");
306
fatal_error ("Unknown node type!");
311
fatal_error ("Null node found!");
314
info->bestmove = nodeseq[i];
315
node = node->child[nodeseq[i]];
321
info->max_tree_depth = max (info->max_tree_depth, depth + 1);
328
her_set_pdv_according_to_children (struct node *node)
330
short x, children = 0;
333
for (x = 0; x < BOARDX; x++)
334
if (node->stack[x] < BOARDY)
338
fatal_error ("Father without children but of value unknown");
340
switch (node->type) {
342
node->proof = children;
348
node->disproof = children;
356
her_set_proof_and_disproof_numbers (struct node *node)
362
fatal_error ("Invalid node chosen");
363
else if (node->expanded) {
364
switch (node->type) {
367
node->disproof = MAXVALUE;
368
for (x = 0; x < BOARDX; x++)
369
if (node->child[x]) {
370
node->proof += node->child[x]->proof;
371
node->disproof = min (node->disproof, node->child[x]->disproof);
373
if (node->disproof == 0)
374
node->proof = MAXVALUE;
378
node->proof = MAXVALUE;
380
for (x = 0; x < BOARDX; x++)
381
if (node->child[x]) {
382
node->proof = min (node->proof, node->child[x]->proof);
383
node->disproof += node->child[x]->disproof;
385
if (node->proof == 0)
386
node->disproof = MAXVALUE;
390
fatal_error ("I don't know what to prove or disprove!");
394
if (node->proof < 0 || node->disproof < 0)
395
fatal_error ("Proof and disproof numbers cannot be lower than zero");
397
} else if (node->evaluated) {
398
switch (node->value) {
401
node->disproof = MAXVALUE;
405
node->proof = MAXVALUE;
410
her_set_pdv_according_to_children (node);
414
fatal_error ("Asked to set a node never evaluated!");
420
her_develop_node (struct node *node)
425
node->expanded = YES;
426
her_generate_all_children (node);
428
for (i = 0; i < BOARDX; i++) {
429
if (node->child[i]) {
430
her_evaluate (node->child[i]);
431
her_set_proof_and_disproof_numbers (node->child[i]);
439
her_update_ancestors (struct node *node)
445
her_set_proof_and_disproof_numbers (node);
447
for (x = 0; x < BOARDX; x++)
449
her_update_ancestors (node->parent[x]);
456
her_pn_search (struct node *root, long maxnodes, struct info *info)
458
struct node *her_most_proving_node;
461
info->max_tree_depth = 1;
462
info->bestmove = her_evaluate (root);
463
her_set_proof_and_disproof_numbers (root);
465
while (root->proof != 0 && root->disproof != 0
466
&& her_resources_available (maxnodes)) {
467
her_most_proving_node = her_select_most_proving_node (root, info);
468
her_develop_node (her_most_proving_node);
469
her_update_ancestors (her_most_proving_node);
472
if (root->proof == 0)
473
root->value = PROVED;
474
else if (root->disproof == 0)
475
root->value = DISPROVED;
477
root->value = UNKNOWN;
483
heuristic_search (struct node *mynode, long maxnodenum)
489
if (mynode->expanded || mynode->evaluated)
490
fatal_error ("Request to evaluate a node already evaluated or expanded!");
492
mynode->evaluated = YES;
494
rootnode = (struct node *) malloc (sizeof (struct node));
496
fatal_error ("Not enough memory");
498
memcpy (rootnode, mynode, sizeof (struct node));
500
her_node_expanded = 0L;
501
her_node_not_expanded = 0L;
503
for (x = 0; x < BOARDX; x++)
504
rootnode->parent[x] = NULL;
506
streeroot = fast_init_bin_tree (rootnode);
507
her_pn_search (rootnode, maxnodenum, &info);
509
mynode->value = rootnode->value;
510
mynode->proof = rootnode->proof;
511
mynode->disproof = rootnode->disproof;
513
her_free_whole_tree (streeroot);
514
fast_free_bin_tree (streeroot);
516
if (mynode->value != UNKNOWN)
526
heuristic_play_best (struct board *board, long maxnodenum)
528
struct board *tempboard;
531
struct node *symmetric;
532
short x, y, issymm = NO;
536
tempboard = (struct board *) malloc (sizeof (struct board));
538
fatal_error ("Cannot store temporary board");
539
memcpy (tempboard, board, sizeof (struct board));
541
rootnode = (struct node *) malloc (sizeof (struct node));
542
symmetric = (struct node *) malloc (sizeof (struct node));
543
if (!rootnode || !symmetric)
544
fatal_error ("Not enough memory");
546
for (y = 0; y < BOARDY; y++) {
547
rootnode->square[ELM (BOARDX, y)] =
548
(unsigned char) (board->square[ELM (BOARDX, y)] & 0xff);
549
symmetric->square[ELM (BOARDX, y)] =
550
(unsigned char) (board->square[ELM (BOARDX, y)] & 0xff);
551
for (x = 0; x < BOARDX; x++) {
552
rootnode->square[ELM (x, y)] =
553
(unsigned char) (board->square[ELM (x, y)] & 0xff);
554
symmetric->square[ELM (x, y)] =
555
(unsigned char) (board->square[ELM (BOARDX - x - 1, y)] & 0xff);
559
rootnode->turn = board->turn;
560
symmetric->turn = board->turn;
562
for (x = 0; x < BOARDX; x++) {
563
rootnode->stack[x] = (unsigned char) (board->stack[x] & 0xff);
564
symmetric->stack[x] =
565
(unsigned char) (board->stack[BOARDX - 1 - x] & 0xff);
568
rootnode->stack[BOARDX] = (unsigned char) (board->stack[BOARDX] & 0xff);
569
symmetric->stack[BOARDX] = (unsigned char) (board->stack[BOARDX] & 0xff);
571
if (bin_compare (symmetric->square, rootnode->square) > 0) {
573
rootnode = symmetric;
578
her_node_expanded = 0L;
579
her_node_not_expanded = 0L;
581
for (x = 0; x < BOARDX; x++) {
582
rootnode->parent[x] = NULL;
583
rootnode->child[x] = NULL;
586
rootnode->evaluated = NO;
587
rootnode->expanded = NO;
588
rootnode->value = UNKNOWN;
589
rootnode->type = OR_TYPE;
591
streeroot = fast_init_bin_tree (rootnode);
592
her_pn_search (rootnode, maxnodenum, &info);
593
mymove = info.bestmove;
595
if (rootnode->value == UNKNOWN)
597
else if (rootnode->value == DISPROVED)
600
mymove = BOARDX - 1 - mymove;
602
her_free_whole_tree (streeroot);
603
fast_free_bin_tree (streeroot);
605
memcpy (board, tempboard, sizeof (struct board));
608
board->nodes_visited = her_node_expanded + her_node_not_expanded;
609
board->maxtreedepth = info.max_tree_depth;
added
removed
src/heurist.c
