summaryrefslogtreecommitdiffstats
path: root/kreversi/Engine.cpp
blob: da7750ce9daa15905cd3a9f8f5d5ce28b82ed771 (plain)
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
778
779
780
781
782
783
784
785
786
787
/* Yo Emacs, this -*- C++ -*-
 *******************************************************************
 *******************************************************************
 *
 *
 * KREVERSI
 *
 *
 *******************************************************************
 *
 * A Reversi (or sometimes called Othello) game
 *
 *******************************************************************
 *
 * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file
 * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet.
 * Many thanks to Mr. Luthman who has allowed me to put this port
 * under the GNU GPL. Without his wonderful game engine kreversi
 * would be just another of those Reversi programs a five year old
 * child could beat easily. But with it it's a worthy opponent!
 *
 * If you are interested on the JAVA applet of Mr. Luthman take a
 * look at http://www.sylog.se/~mats/
 *
 *******************************************************************
 *
 * This file is part of the KDE project "KREVERSI"
 *
 * KREVERSI is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * KREVERSI is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with KREVERSI; see the file COPYING.  If not, write to
 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 *******************************************************************
 */

// The class Engine produces moves from a Game object through calls to the
// function ComputeMove().
//
// First of all: this is meant to be a simple example of a game playing
// program. Not everything is done in the most clever way, particularly not
// the way the moves are searched, but it is hopefully made in a way that makes
// it easy to understand. The function ComputeMove2() that does all the work
// is actually not much more than a hundred lines. Much could be done to
// make the search faster though, I'm perfectly aware of that. Feel free
// to experiment.
//
// The method used to generate the moves is called minimax tree search with
// alpha-beta pruning to a fixed depth. In short this means that all possible
// moves a predefined number of moves ahead are either searched or refuted
// with a method called alpha-beta pruning. A more thorough explanation of
// this method could be found at the world wide web at http:
// //yoda.cis.temple.edu:8080/UGAIWWW/lectures96/search/minimax/alpha-beta.html
// at the time this was written. Searching for "minimax" would also point
// you to information on this subject. It is probably possible to understand
// this method by reading the source code though, it is not that complicated.
//
// At every leaf node at the search tree, the resulting position is evaluated.
// Two things are considered when evaluating a position: the number of pieces
// of each color and at which squares the pieces are located. Pieces at the
// corners are valuable and give a high value, and having pieces at squares
// next to a corner is not very good and they give a lower value. In the
// beginning of a game it is more important to have pieces on "good" squares,
// but towards the end the total number of pieces of each color is given a
// higher weight. Other things, like how many legal moves that can be made in a
// position, and the number of pieces that can never be turned would probably
// make the program stronger if they were considered in evaluating a position,
// but that would make things more complicated (this was meant to be very
// simple example) and would also slow down computation (considerably?).
//
// The member m_board[10][10]) holds the current position during the
// computation. It is initiated at the start of ComputeMove() and
// every move that is made during the search is made on this board. It should
// be noted that 1 to 8 is used for the actual board, but 0 and 9 can be
// used too (they are always empty). This is practical when turning pieces
// when moves are made on the board. Every piece that is put on the board
// or turned is saved in the stack m_squarestack (see class SquareStack) so
// every move can easily be reversed after the search in a node is completed.
//
// The member m_bc_board[][] holds board control values for each square
// and is initiated by a call to the function private void SetupBcBoard()
// from Engines constructor. It is used in evaluation of positions except
// when the game tree is searched all the way to the end of the game.
//
// The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to
// speed up the tree search. This goes against the principle of keeping things
// simple, but to understand the program you do not need to understand them
// at all. They are there to make it possible to throw away moves where
// the piece that is played is not adjacent to a piece of opposite color
// at an early stage (because they could never be legal). It should be
// pointed out that not all moves that pass this test are legal, there will
// just be fewer moves that have to be tested in a more time consuming way.
//
// There are also two other members that should be mentioned: Score m_score
// and Score m_bc_score. They hold the number of pieces of each color and
// the sum of the board control values for each color during the search
// (this is faster than counting at every leaf node).
//

// The classes SquareStackEntry and SquareStack implement a
// stack that is used by Engine to store pieces that are turned during
// searching (see ComputeMove()).
//
// The class MoveAndValue is used by Engine to store all possible moves
// at the first level and the values that were calculated for them.
// This makes it possible to select a random move among those with equal
// or nearly equal value after the search is completed.


#include <qapplication.h>

#include "Engine.h"


// ================================================================
//                          Class ULONG64


#if !defined(__GNUC__)


ULONG64::ULONG64() : QBitArray(64) 
{
  fill(0);
}


// Initialize an ULONG64 from a 32 bit value.
//

ULONG64::ULONG64( unsigned int value ) : QBitArray(64) 
{
  fill(0);
  for(int i = 0; i < 32; i++) {
    setBit(i, (bool)(value & 1));
    value >>= 1;
  }
}


// Shift an ULONG64 left one bit.
//

void ULONG64::shl() 
{
  for(int i = 63; i > 0; i--)
    setBit(i, testBit(i - 1));
  setBit(0, 0);
}

#endif


// ================================================================
//           Classes SquareStackEntry and SquareStack


// A SquareStack is used to store changes to the squares on the board
// during search.


inline void SquareStackEntry::setXY(int x, int y) {
  m_x = x;
  m_y = y;
}


SquareStackEntry::SquareStackEntry()
{
  setXY(0,0);
}


// ----------------------------------------------------------------


SquareStack::SquareStack() {
  init(0);
}


SquareStack::SquareStack(int size) {
  init(size);
}


void SquareStack::resize(int size) 
{
  m_squarestack.resize(size);
}


// (Re)initialize the stack so that is empty, and at the same time
// resize it to 'size'.
//

void SquareStack::init(int size) 
{
  resize(size);

  m_top = 0;
  for (int i = 0; i < size; i++)
    m_squarestack[i].setXY(0,0);
}



inline SquareStackEntry SquareStack::Pop() 
{
  return m_squarestack[--m_top];
}


inline void SquareStack::Push(int x, int y)
{
  m_squarestack[m_top].m_x = x;
  m_squarestack[m_top++].m_y = y;
}


// ================================================================
//                       Class MoveAndValue


// Class MoveAndValue aggregates a move with its value.
//


inline void MoveAndValue::setXYV(int x, int y, int value) 
{
  m_x     = x;
  m_y     = y;
  m_value = value;
}


MoveAndValue::MoveAndValue() 
{
  setXYV(0,0,0);
}


MoveAndValue::MoveAndValue(int x, int y, int value) 
{
  setXYV(x, y, value);
}


// ================================================================
//                        The Engine itself


// Some special values used in the search.
const int Engine::LARGEINT      = 99999;
const int Engine::ILLEGAL_VALUE = 8888888;
const int Engine::BC_WEIGHT     = 3;


Engine::Engine(int st, int sd) : SuperEngine(st, sd) 
{
  SetupBcBoard();
  SetupBits();
}


Engine::Engine(int st) : SuperEngine(st) 
{
  SetupBcBoard();
  SetupBits();
}


Engine::Engine() : SuperEngine(1) 
{
  SetupBcBoard();
  SetupBits();
}


// keep GUI alive
void Engine::yield() 
{
  qApp->processEvents();
}


// Calculate the best move from the current position, and return it.

Move Engine::computeMove(Game *game, bool competitive) 
{
  Color color;

  // A competitive game is one where we try our damnedest to make the
  // best move.  The opposite is a casual game where the engine might
  // make "a mistake".  The idea behind this is not to scare away
  // newbies.  The member m_competitive is used during search for this
  // very move.
  m_competitive = competitive;

  // Suppose that we should give a heuristic evaluation.  If we are
  // close to the end of the game we can make an exhaustive search,
  // but that case is determined further down.
  m_exhaustive = false;

  // Get the color to calculate the move for.
  color = game->toMove();
  if (color == Nobody)
    return Move(Nobody, -1, -1);

  // Figure out the current score
  m_score.set(White, game->score(White));
  m_score.set(Black, game->score(Black));

  // Treat the first move as a special case (we can basically just
  // pick a move at random).
  if (m_score.score(White) + m_score.score(Black) == 4)
    return ComputeFirstMove(game);

  // Let there be room for 3000 changes during the recursive search.
  // This is more than will ever be needed.
  m_squarestack.init(3000);

  // Get the search depth.  If we are close to the end of the game,
  // the number of possible moves goes down, so we can search deeper
  // without using more time.  
  m_depth = m_strength;
  if (m_score.score(White) + m_score.score(Black) + m_depth + 3 >= 64)
    m_depth = 64 - m_score.score(White) - m_score.score(Black);
  else if (m_score.score(White) + m_score.score(Black) + m_depth + 4 >= 64)
    m_depth += 2;
  else if (m_score.score(White) + m_score.score(Black) + m_depth + 5 >= 64)
    m_depth++;

  // If we are very close to the end, we can even make the search
  // exhaustive.
  if (m_score.score(White) + m_score.score(Black) + m_depth >= 64)
    m_exhaustive = true;

  // The evaluation is a linear combination of the score (number of
  // pieces) and the sum of the scores for the squares (given by
  // m_bc_score).  The earlier in the game, the more we use the square
  // values and the later in the game the more we use the number of
  // pieces.
  m_coeff = 100 - (100*
		   (m_score.score(White) + m_score.score(Black) 
		    + m_depth - 4)) / 60;

  // Initialize the board that we use for the search.
  for (uint x = 0; x < 10; x++)
    for (uint y = 0; y < 10; y++) {
      if (1 <= x && x <= 8
	  && 1 <= y && y <= 8)
	m_board[x][y] = game->color(x, y);
      else
	m_board[x][y] = Nobody;
    }

  // Initialize a lot of stuff that we will use in the search.

  // Initialize m_bc_score to the current bc score.  This is kept
  // up-to-date incrementally so that way we won't have to calculate
  // it from scratch for each evaluation.
  m_bc_score.set(White, CalcBcScore(White));
  m_bc_score.set(Black, CalcBcScore(Black));

  ULONG64 colorbits    = ComputeOccupiedBits(color);
  ULONG64 opponentbits = ComputeOccupiedBits(opponent(color));

  int maxval = -LARGEINT;
  int max_x = 0;
  int max_y = 0;

  MoveAndValue moves[60];
  int number_of_moves = 0;
  int number_of_maxval = 0;

  setInterrupt(false);

  ULONG64 null_bits;
  null_bits = 0;

  // The main search loop.  Step through all possible moves and keep
  // track of the most valuable one.  This move is stored in 
  // (max_x, max_y) and the value is stored in maxval.
  m_nodes_searched = 0;
  for (int x = 1; x < 9; x++) {
    for (int y = 1; y < 9; y++) {
      // Don't bother with non-empty squares and squares that aren't
      // neighbors to opponent pieces.
      if (m_board[x][y] != Nobody
	  || (m_neighbor_bits[x][y] & opponentbits) == null_bits)
	continue;


      int val = ComputeMove2(x, y, color, 1, maxval,
			     colorbits, opponentbits);

      if (val != ILLEGAL_VALUE) {
	moves[number_of_moves++].setXYV(x, y, val);

	// If the move is better than all previous moves, then record
	// this fact...
	if (val > maxval) {

	  // ...except that we want to make the computer miss some
	  // good moves so that beginners can play against the program
	  // and not always lose.  However, we only do this if the
	  // user wants a casual game, which is set in the settings
	  // dialog.
	  int randi = m_random.getLong(7);
	  if (maxval == -LARGEINT 
	      || m_competitive 
	      || randi < (int) m_strength) {
	    maxval = val;
	    max_x  = x;
	    max_y  = y;

	    number_of_maxval = 1;
	  }
	}
	else if (val == maxval)
	  number_of_maxval++;
      }

      // Jump out prematurely if interrupt is set.
      if (interrupted()) 
	break;
    }
  }

  // long endtime = times(&tmsdummy);

  // If there are more than one best move, the pick one randomly.
  if (number_of_maxval > 1) {
    int  r = m_random.getLong(number_of_maxval) + 1;
    int  i;

    for (i = 0; i < number_of_moves; i++) {
      if (moves[i].m_value == maxval && --r <= 0) 
	break;
    }

    max_x = moves[i].m_x;
    max_y = moves[i].m_y;
  }

  // Return a suitable move.
  if (interrupted())
    return Move(Nobody, -1, -1);
  else if (maxval != -LARGEINT)
    return Move(color, max_x, max_y);
  else
    return Move(Nobody, -1, -1);
}


// Get the first move.  We can pick any move at random.
//

Move Engine::ComputeFirstMove(Game *game) 
{
  int    r;
  Color  color = game->toMove();

  r = m_random.getLong(4) + 1;

  if (color == White) {
    if (r == 1)      return  Move(color, 3, 5);
    else if (r == 2) return  Move(color, 4, 6);
    else if (r == 3) return  Move(color, 5, 3);
    else             return  Move(color, 6, 4);
  }
  else {
    if (r == 1)      return  Move(color, 3, 4);
    else if (r == 2) return  Move(color, 5, 6);
    else if (r == 3) return  Move(color, 4, 3);
    else             return  Move(color, 6, 5);
  }
}


// Play a move at (xplay, yplay) and generate a value for it.  If we
// are at the maximum search depth, we get the value by calling
// EvaluatePosition(), otherwise we get it by performing an alphabeta
// search.
//

int Engine::ComputeMove2(int xplay, int yplay, Color color, int level,
			 int cutoffval, ULONG64 colorbits,
			 ULONG64 opponentbits)
{
  int               number_of_turned = 0;
  SquareStackEntry  mse;
  Color             opponent = ::opponent(color);

  m_nodes_searched++;

  // Put the piece on the board and incrementally update scores and bitmaps.
  m_board[xplay][yplay] = color;
  colorbits |= m_coord_bit[xplay][yplay];
  m_score.inc(color);
  m_bc_score.add(color, m_bc_board[xplay][yplay]);

  // Loop through all 8 directions and turn the pieces that can be turned.
  for (int xinc = -1; xinc <= 1; xinc++)
    for (int yinc = -1; yinc <= 1; yinc++) {
      if (xinc == 0 && yinc == 0) 
	continue;

      int x, y;

      for (x = xplay + xinc, y = yplay + yinc; m_board[x][y] == opponent;
	   x += xinc, y += yinc)
	;

      // If we found the end of a turnable row, then go back and turn
      // all pieces on the way back.  Also push the squares with
      // turned pieces on the squarestack so that we can undo the move
      // later.
      if (m_board[x][y] == color)
	for (x -= xinc, y -= yinc; x != xplay || y != yplay;
	     x -= xinc, y -= yinc) {
	  m_board[x][y] = color;
	  colorbits |= m_coord_bit[x][y];
	  opponentbits &= ~m_coord_bit[x][y];

	  m_squarestack.Push(x, y);

	  m_bc_score.add(color, m_bc_board[x][y]);
	  m_bc_score.sub(opponent, m_bc_board[x][y]);
	  number_of_turned++;
	}
    }

  int retval = -LARGEINT;

  // If we managed to turn at least one piece, then (xplay, yplay) was
  // a legal move.  Now find out the value of the move.
  if (number_of_turned > 0) {

    // First adjust the number of pieces for each side.
    m_score.add(color, number_of_turned);
    m_score.sub(opponent, number_of_turned);

    // If we are at the bottom of the search, get the evaluation.
    if (level >= m_depth)
      retval = EvaluatePosition(color); // Terminal node
    else {
      int maxval = TryAllMoves(opponent, level, cutoffval, opponentbits,
			       colorbits);

      if (maxval != -LARGEINT)
	retval = -maxval;
      else {

	// No possible move for the opponent, it is colors turn again:
	retval = TryAllMoves(color, level, -LARGEINT, colorbits, opponentbits);

	if (retval == -LARGEINT) {

	  // No possible move for anybody => end of game:
	  int finalscore = m_score.score(color) - m_score.score(opponent);

	  if (m_exhaustive)
	    retval = finalscore;
	  else {
	    // Take a sure win and avoid a sure loss (may not be optimal):

	    if (finalscore > 0) 
	      retval = LARGEINT - 65 + finalscore;
	    else if (finalscore < 0)
	      retval = -(LARGEINT - 65 + finalscore);
	    else
	      retval = 0;
	  }
	}
      }
    }

    m_score.add(opponent, number_of_turned);
    m_score.sub(color, number_of_turned);
  }

  // Undo the move.  Start by unturning the turned pieces.
  for (int i = number_of_turned; i > 0; i--) {
    mse = m_squarestack.Pop();
    m_bc_score.add(opponent, m_bc_board[mse.m_x][mse.m_y]);
    m_bc_score.sub(color, m_bc_board[mse.m_x][mse.m_y]);
    m_board[mse.m_x][mse.m_y] = opponent;
  }

  // Now remove the new piece that we put down.
  m_board[xplay][yplay] = Nobody;
  m_score.sub(color, 1);
  m_bc_score.sub(color, m_bc_board[xplay][yplay]);

  // Return a suitable value.
  if (number_of_turned < 1 || interrupted())
    return ILLEGAL_VALUE;
  else
    return retval;
}


// Generate all legal moves from the current position, and do a search
// to see the value of them.  This function returns the value of the
// most valuable move, but not the move itself.
//

int Engine::TryAllMoves(Color opponent, int level, int cutoffval,
			ULONG64 opponentbits, ULONG64 colorbits)
{
  int maxval = -LARGEINT;

  // Keep GUI alive by calling the event loop.
  yield();

  ULONG64  null_bits;
  null_bits = 0;

  for (int x = 1; x < 9; x++) {
    for (int y = 1; y < 9; y++) {
      if (m_board[x][y] == Nobody 
	  && (m_neighbor_bits[x][y] & colorbits) != null_bits) {
	int val = ComputeMove2(x, y, opponent, level+1, maxval, opponentbits,
			       colorbits);

	if (val != ILLEGAL_VALUE && val > maxval) {
	  maxval = val;
	  if (maxval > -cutoffval || interrupted()) 
	    break;
	}
      }
    }

    if (maxval > -cutoffval || interrupted())
      break;
  }

  if (interrupted()) 
    return -LARGEINT;

  return maxval;
}


// Calculate a heuristic value for the current position.  If we are at
// the end of the game, do this by counting the pieces.  Otherwise do
// it by combining the score using the number of pieces, and the score
// using the board control values.
//

int Engine::EvaluatePosition(Color color)
{
  int retval;

  Color  opponent = ::opponent(color);

  int    score_color    = m_score.score(color);
  int    score_opponent = m_score.score(opponent);

  if (m_exhaustive)
    retval = score_color - score_opponent;
  else {
    retval = (100-m_coeff) *
      (m_score.score(color) - m_score.score(opponent)) 
      + m_coeff * BC_WEIGHT * (m_bc_score.score(color)
			       - m_bc_score.score(opponent));
  }

  return retval;
}


// Calculate bitmaps for each square, and also for neighbors of each
// square.
//

void Engine::SetupBits()
{
  //m_coord_bit = new long[9][9];
  //m_neighbor_bits = new long[9][9];

  ULONG64 bits = 1;

  // Store a 64 bit unsigned it with the corresponding bit set for
  // each square.
  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++) {
      m_coord_bit[i][j] = bits;
#if !defined(__GNUC__)
      bits.shl();
#else
      bits *= 2;
#endif
    }

  // Store a bitmap consisting of all neighbors for each square.
  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++) {
      m_neighbor_bits[i][j] = 0;

      for (int xinc=-1; xinc<=1; xinc++)
	for (int yinc=-1; yinc<=1; yinc++) {
	  if (xinc != 0 || yinc != 0)
	    if (i + xinc > 0 && i + xinc < 9 && j + yinc > 0 && j + yinc < 9)
	      m_neighbor_bits[i][j] |= m_coord_bit[i + xinc][j + yinc];
	}
    }
}


// Set up the board control values that will be used in evaluation of
// the position.
//

void Engine::SetupBcBoard()
{
  // JAVA m_bc_board = new int[9][9];

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++) {
      if (i == 2 || i == 7)
	m_bc_board[i][j] = -1;
      else
	m_bc_board[i][j] = 0;

      if (j == 2 || j == 7)
	m_bc_board[i][j] -= 1;
    }

  m_bc_board[1][1] = 2;
  m_bc_board[8][1] = 2;
  m_bc_board[1][8] = 2;
  m_bc_board[8][8] = 2;

  m_bc_board[1][2] = -1;
  m_bc_board[2][1] = -1;
  m_bc_board[1][7] = -1;
  m_bc_board[7][1] = -1;
  m_bc_board[8][2] = -1;
  m_bc_board[2][8] = -1;
  m_bc_board[8][7] = -1;
  m_bc_board[7][8] = -1;
}


// Calculate the board control score.
//

int Engine::CalcBcScore(Color color)
{
  int sum = 0;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      if (m_board[i][j] == color)
	sum += m_bc_board[i][j];

  return sum;
}


// Calculate a bitmap of the occupied squares for a certain color.
//

ULONG64 Engine::ComputeOccupiedBits(Color color)
{
  ULONG64 retval = 0;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      if (m_board[i][j] == color) retval |= m_coord_bit[i][j];

  return retval;
}