1/*******************************************************************
2 *
3 * Copyright 1997 Mario Weilguni <mweilguni@sime.com>
4 *
5 * This file is part of the KDE project "KREVERSI"
6 *
7 * KREVERSI is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2, or (at your option)
10 * any later version.
11 *
12 * KREVERSI is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with KREVERSI; see the file COPYING. If not, write to
19 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 * Boston, MA 02110-1301, USA.
21 *
22 *******************************************************************
23 *
24 *
25 * KREVERSI
26 *
27 *
28 *******************************************************************
29 *
30 * A Reversi (or sometimes called Othello) game
31 *
32 *******************************************************************
33 *
34 * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file
35 * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet.
36 * Many thanks to Mr. Luthman who has allowed me to put this port
37 * under the GNU GPL. Without his wonderful game engine kreversi
38 * would be just another of those Reversi programs a five year old
39 * child could beat easily. But with it it's a worthy opponent!
40 *
41 * If you are interested on the JAVA applet of Mr. Luthman take a
42 * look at http://www.sylog.se/~mats/
43 */
44
45// The class Engine produces moves from a Game object through calls to the
46// function ComputeMove().
47//
48// First of all: this is meant to be a simple example of a game playing
49// program. Not everything is done in the most clever way, particularly not
50// the way the moves are searched, but it is hopefully made in a way that makes
51// it easy to understand. The function ComputeMove2() that does all the work
52// is actually not much more than a hundred lines. Much could be done to
53// make the search faster though, I'm perfectly aware of that. Feel free
54// to experiment.
55//
56// The method used to generate the moves is called minimax tree search with
57// alpha-beta pruning to a fixed depth. In short this means that all possible
58// moves a predefined number of moves ahead are either searched or refuted
59// with a method called alpha-beta pruning. A more thorough explanation of
60// this method could be found at the world wide web at http:
61// //yoda.cis.temple.edu:8080/UGAIWWW/lectures96/search/minimax/alpha-beta.html
62// at the time this was written. Searching for "minimax" would also point
63// you to information on this subject. It is probably possible to understand
64// this method by reading the source code though, it is not that complicated.
65//
66// At every leaf node at the search tree, the resulting position is evaluated.
67// Two things are considered when evaluating a position: the number of pieces
68// of each color and at which squares the pieces are located. Pieces at the
69// corners are valuable and give a high value, and having pieces at squares
70// next to a corner is not very good and they give a lower value. In the
71// beginning of a game it is more important to have pieces on "good" squares,
72// but towards the end the total number of pieces of each color is given a
73// higher weight. Other things, like how many legal moves that can be made in a
74// position, and the number of pieces that can never be turned would probably
75// make the program stronger if they were considered in evaluating a position,
76// but that would make things more complicated (this was meant to be very
77// simple example) and would also slow down computation (considerably?).
78//
79// The member m_board[10][10]) holds the current position during the
80// computation. It is initiated at the start of ComputeMove() and
81// every move that is made during the search is made on this board. It should
82// be noted that 1 to 8 is used for the actual board, but 0 and 9 can be
83// used too (they are always empty). This is practical when turning pieces
84// when moves are made on the board. Every piece that is put on the board
85// or turned is saved in the stack m_squarestack (see class SquareStack) so
86// every move can easily be reversed after the search in a node is completed.
87//
88// The member m_bc_board[][] holds board control values for each square
89// and is initiated by a call to the function private void SetupBcBoard()
90// from Engines constructor. It is used in evaluation of positions except
91// when the game tree is searched all the way to the end of the game.
92//
93// The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to
94// speed up the tree search. This goes against the principle of keeping things
95// simple, but to understand the program you do not need to understand them
96// at all. They are there to make it possible to throw away moves where
97// the piece that is played is not adjacent to a piece of opposite color
98// at an early stage (because they could never be legal). It should be
99// pointed out that not all moves that pass this test are legal, there will
100// just be fewer moves that have to be tested in a more time consuming way.
101//
102// There are also two other members that should be mentioned: Score m_score
103// and Score m_bc_score. They hold the number of pieces of each color and
104// the sum of the board control values for each color during the search
105// (this is faster than counting at every leaf node).
106//
107
108// The classes SquareStackEntry and SquareStack implement a
109// stack that is used by Engine to store pieces that are turned during
110// searching (see ComputeMove()).
111//
112// The class MoveAndValue is used by Engine to store all possible moves
113// at the first level and the values that were calculated for them.
114// This makes it possible to select a random move among those with equal
115// or nearly equal value after the search is completed.
116
117#include <Engine.h>
118
119#include <QVector>
120#include <QApplication>
121
122#include <KDebug>
123
124// ================================================================
125// Classes SquareStackEntry and SquareStack
126
127
128// A SquareStack is used to store changes to the squares on the board
129// during search.
130
131
132inline void SquareStackEntry::setXY(int x, int y)
133{
134 m_x = x;
135 m_y = y;
136}
137
138
139SquareStackEntry::SquareStackEntry()
140{
141 setXY(0, 0);
142}
143
144
145// ----------------------------------------------------------------
146
147
148SquareStack::SquareStack()
149{
150 init(0);
151}
152
153
154SquareStack::SquareStack(int size)
155{
156 init(size);
157}
158
159
160void SquareStack::resize(int size)
161{
162 m_squarestack.resize(size);
163}
164
165
166// (Re)initialize the stack so that is empty, and at the same time
167// resize it to 'size'.
168//
169
170void SquareStack::init(int size)
171{
172 resize(size);
173
174 m_top = 0;
175 for (int i = 0; i < size; i++)
176 m_squarestack[i].setXY(0, 0);
177}
178
179
180
181inline SquareStackEntry SquareStack::Pop()
182{
183 return m_squarestack[--m_top];
184}
185
186
187inline void SquareStack::Push(int x, int y)
188{
189 m_squarestack[m_top].m_x = x;
190 m_squarestack[m_top++].m_y = y;
191}
192
193
194// ================================================================
195// Class MoveAndValue
196
197
198// Class MoveAndValue aggregates a move with its value.
199//
200
201
202inline void MoveAndValue::setXYV(int x, int y, int value)
203{
204 m_x = x;
205 m_y = y;
206 m_value = value;
207}
208
209
210MoveAndValue::MoveAndValue()
211{
212 setXYV(0, 0, 0);
213}
214
215
216MoveAndValue::MoveAndValue(int x, int y, int value)
217{
218 setXYV(x, y, value);
219}
220
221// ================================================================
222// class Score
223
224/* This class keeps track of the score for both colors. Such a score
225 * could be either the number of pieces, the score from the evaluation
226 * function or anything similar.
227 */
228class Score
229{
230public:
231 Score() {
232 m_score[White] = 0;
233 m_score[Black] = 0;
234 }
235
236 uint score(ChipColor color) const {
237 return m_score[color];
238 }
239
240 void set(ChipColor color, uint score) {
241 m_score[color] = score;
242 }
243 void inc(ChipColor color) {
244 m_score[color]++;
245 }
246 void dec(ChipColor color) {
247 m_score[color]--;
248 }
249 void add(ChipColor color, uint s) {
250 m_score[color] += s;
251 }
252 void sub(ChipColor color, uint s) {
253 m_score[color] -= s;
254 }
255
256private:
257 uint m_score[2];
258};
259
260// ================================================================
261// The Engine itself
262
263
264// Some special values used in the search.
265static const int LARGEINT = 99999;
266static const int ILLEGAL_VALUE = 8888888;
267static const int BC_WEIGHT = 3;
268
269
270Engine::Engine(int st, int sd)/* : SuperEngine(st, sd) */
271 : m_strength(st), m_computingMove(false)
272{
273 m_random.setSeed(sd);
274 m_score = new Score;
275 m_bc_score = new Score;
276 SetupBcBoard();
277 SetupBits();
278}
279
280
281Engine::Engine(int st) //: SuperEngine(st)
282 : m_strength(st), m_computingMove(false)
283{
284 m_random.setSeed(0);
285 m_score = new Score;
286 m_bc_score = new Score;
287 SetupBcBoard();
288 SetupBits();
289}
290
291
292Engine::Engine()// : SuperEngine(1)
293 : m_strength(1), m_computingMove(false)
294{
295 m_random.setSeed(0);
296 m_score = new Score;
297 m_bc_score = new Score;
298 SetupBcBoard();
299 SetupBits();
300}
301
302Engine::~Engine()
303{
304 delete m_score;
305 delete m_bc_score;
306}
307
308// keep GUI alive
309void Engine::yield()
310{
311 qApp->processEvents();
312}
313
314
315// Calculate the best move from the current position, and return it.
316
317KReversiMove Engine::computeMove(const KReversiGame& game, bool competitive)
318{
319 if (m_computingMove)
320 return KReversiMove();
321
322 m_computingMove = true;
323
324 ChipColor color;
325
326 // A competitive game is one where we try our damnedest to make the
327 // best move. The opposite is a casual game where the engine might
328 // make "a mistake". The idea behind this is not to scare away
329 // newbies. The member m_competitive is used during search for this
330 // very move.
331 m_competitive = competitive;
332
333 // Suppose that we should give a heuristic evaluation. If we are
334 // close to the end of the game we can make an exhaustive search,
335 // but that case is determined further down.
336 m_exhaustive = false;
337
338 // Get the color to calculate the move for.
339 color = game.currentPlayer();
340 if (color == NoColor) {
341 m_computingMove = false;
342 return KReversiMove();
343 }
344
345 // Figure out the current score
346 m_score->set(White, game.playerScore(White));
347 m_score->set(Black, game.playerScore(Black));
348
349 // Treat the first move as a special case (we can basically just
350 // pick a move at random).
351 if (m_score->score(White) + m_score->score(Black) == 4) {
352 m_computingMove = false;
353 return ComputeFirstMove(game);
354 }
355
356 // Let there be room for 3000 changes during the recursive search.
357 // This is more than will ever be needed.
358 m_squarestack.init(3000);
359
360 // Get the search depth. If we are close to the end of the game,
361 // the number of possible moves goes down, so we can search deeper
362 // without using more time.
363 m_depth = m_strength;
364 if (m_score->score(White) + m_score->score(Black) + m_depth + 3 >= 64)
365 m_depth = 64 - m_score->score(White) - m_score->score(Black);
366 else if (m_score->score(White) + m_score->score(Black) + m_depth + 4 >= 64)
367 m_depth += 2;
368 else if (m_score->score(White) + m_score->score(Black) + m_depth + 5 >= 64)
369 m_depth++;
370
371 // If we are very close to the end, we can even make the search
372 // exhaustive.
373 if (m_score->score(White) + m_score->score(Black) + m_depth >= 64)
374 m_exhaustive = true;
375
376 // The evaluation is a linear combination of the score (number of
377 // pieces) and the sum of the scores for the squares (given by
378 // m_bc_score). The earlier in the game, the more we use the square
379 // values and the later in the game the more we use the number of
380 // pieces.
381 m_coeff = 100 - (100 *
382 (m_score->score(White) + m_score->score(Black)
383 + m_depth - 4)) / 60;
384
385 // Initialize the board that we use for the search.
386 for (uint x = 0; x < 10; x++)
387 for (uint y = 0; y < 10; y++) {
388 if (1 <= x && x <= 8
389 && 1 <= y && y <= 8)
390 m_board[x][y] = game.chipColorAt(KReversiPos(y - 1, x - 1));
391 else
392 m_board[x][y] = NoColor;
393 }
394
395 // Initialize a lot of stuff that we will use in the search.
396
397 // Initialize m_bc_score to the current bc score. This is kept
398 // up-to-date incrementally so that way we won't have to calculate
399 // it from scratch for each evaluation.
400 m_bc_score->set(White, CalcBcScore(White));
401 m_bc_score->set(Black, CalcBcScore(Black));
402
403 quint64 colorbits = ComputeOccupiedBits(color);
404 quint64 opponentbits = ComputeOccupiedBits(Utils::opponentColorFor(color));
405
406 int maxval = -LARGEINT;
407 int max_x = 0;
408 int max_y = 0;
409
410 MoveAndValue moves[60];
411 int number_of_moves = 0;
412 int number_of_maxval = 0;
413
414 setInterrupt(false);
415
416 quint64 null_bits;
417 null_bits = 0;
418
419 // The main search loop. Step through all possible moves and keep
420 // track of the most valuable one. This move is stored in
421 // (max_x, max_y) and the value is stored in maxval.
422 m_nodes_searched = 0;
423 for (int x = 1; x < 9; x++) {
424 for (int y = 1; y < 9; y++) {
425 // Don't bother with non-empty squares and squares that aren't
426 // neighbors to opponent pieces.
427 if (m_board[x][y] != NoColor
428 || (m_neighbor_bits[x][y] & opponentbits) == null_bits)
429 continue;
430
431
432 int val = ComputeMove2(x, y, color, 1, maxval,
433 colorbits, opponentbits);
434
435 if (val != ILLEGAL_VALUE) {
436 moves[number_of_moves++].setXYV(x, y, val);
437
438 // If the move is better than all previous moves, then record
439 // this fact...
440 if (val > maxval) {
441
442 // ...except that we want to make the computer miss some
443 // good moves so that beginners can play against the program
444 // and not always lose. However, we only do this if the
445 // user wants a casual game, which is set in the settings
446 // dialog.
447 int randi = m_random.getLong(7);
448 if (maxval == -LARGEINT
449 || m_competitive
450 || randi < (int) m_strength) {
451 maxval = val;
452 max_x = x;
453 max_y = y;
454
455 number_of_maxval = 1;
456 }
457 } else if (val == maxval)
458 number_of_maxval++;
459 }
460
461 // Jump out prematurely if interrupt is set.
462 if (interrupted())
463 break;
464 }
465 }
466
467 // long endtime = times(&tmsdummy);
468
469 // If there are more than one best move, the pick one randomly.
470 if (number_of_maxval > 1) {
471 int r = m_random.getLong(number_of_maxval) + 1;
472 int i;
473
474 for (i = 0; i < number_of_moves; ++i) {
475 if (moves[i].m_value == maxval && --r <= 0)
476 break;
477 }
478
479 max_x = moves[i].m_x;
480 max_y = moves[i].m_y;
481 }
482
483 m_computingMove = false;
484 // Return a suitable move.
485 if (interrupted())
486 return KReversiMove(NoColor, -1, -1);
487 else if (maxval != -LARGEINT)
488 return KReversiMove(color, max_y - 1, max_x - 1);
489 else
490 return KReversiMove(NoColor, -1, -1);
491}
492
493
494// Get the first move. We can pick any move at random.
495//
496
497KReversiMove Engine::ComputeFirstMove(const KReversiGame& game)
498{
499 int r;
500 ChipColor color = game.currentPlayer();
501
502 r = m_random.getLong(4) + 1;
503
504 if (color == White) {
505 if (r == 1) return KReversiMove(color, 4, 2);
506 else if (r == 2) return KReversiMove(color, 5, 3);
507 else if (r == 3) return KReversiMove(color, 2, 4);
508 else return KReversiMove(color, 3, 5);
509 } else {
510 if (r == 1) return KReversiMove(color, 3, 2);
511 else if (r == 2) return KReversiMove(color, 5, 4);
512 else if (r == 3) return KReversiMove(color, 2, 3);
513 else return KReversiMove(color, 4, 5);
514 }
515}
516
517
518// Play a move at (xplay, yplay) and generate a value for it. If we
519// are at the maximum search depth, we get the value by calling
520// EvaluatePosition(), otherwise we get it by performing an alphabeta
521// search.
522//
523
524int Engine::ComputeMove2(int xplay, int yplay, ChipColor color, int level,
525 int cutoffval, quint64 colorbits,
526 quint64 opponentbits)
527{
528 int number_of_turned = 0;
529 SquareStackEntry mse;
530 ChipColor opponent = Utils::opponentColorFor(color);
531
532 m_nodes_searched++;
533
534 // Put the piece on the board and incrementally update scores and bitmaps.
535 m_board[xplay][yplay] = color;
536 colorbits |= m_coord_bit[xplay][yplay];
537 m_score->inc(color);
538 m_bc_score->add(color, m_bc_board[xplay][yplay]);
539
540 // Loop through all 8 directions and turn the pieces that can be turned.
541 for (int xinc = -1; xinc <= 1; xinc++)
542 for (int yinc = -1; yinc <= 1; yinc++) {
543 if (xinc == 0 && yinc == 0)
544 continue;
545
546 int x, y;
547
548 for (x = xplay + xinc, y = yplay + yinc; m_board[x][y] == opponent;
549 x += xinc, y += yinc)
550 ;
551
552 // If we found the end of a turnable row, then go back and turn
553 // all pieces on the way back. Also push the squares with
554 // turned pieces on the squarestack so that we can undo the move
555 // later.
556 if (m_board[x][y] == color)
557 for (x -= xinc, y -= yinc; x != xplay || y != yplay;
558 x -= xinc, y -= yinc) {
559 m_board[x][y] = color;
560 colorbits |= m_coord_bit[x][y];
561 opponentbits &= ~m_coord_bit[x][y];
562
563 m_squarestack.Push(x, y);
564
565 m_bc_score->add(color, m_bc_board[x][y]);
566 m_bc_score->sub(opponent, m_bc_board[x][y]);
567 number_of_turned++;
568 }
569 }
570
571 int retval = -LARGEINT;
572
573 // If we managed to turn at least one piece, then (xplay, yplay) was
574 // a legal move. Now find out the value of the move.
575 if (number_of_turned > 0) {
576
577 // First adjust the number of pieces for each side.
578 m_score->add(color, number_of_turned);
579 m_score->sub(opponent, number_of_turned);
580
581 // If we are at the bottom of the search, get the evaluation.
582 if (level >= m_depth)
583 retval = EvaluatePosition(color); // Terminal node
584 else {
585 int maxval = TryAllMoves(opponent, level, cutoffval, opponentbits,
586 colorbits);
587
588 if (maxval != -LARGEINT)
589 retval = -maxval;
590 else {
591
592 // No possible move for the opponent, it is colors turn again:
593 retval = TryAllMoves(color, level, -LARGEINT, colorbits, opponentbits);
594
595 if (retval == -LARGEINT) {
596
597 // No possible move for anybody => end of game:
598 int finalscore = m_score->score(color) - m_score->score(opponent);
599
600 if (m_exhaustive)
601 retval = finalscore;
602 else {
603 // Take a sure win and avoid a sure loss (may not be optimal):
604
605 if (finalscore > 0)
606 retval = LARGEINT - 65 + finalscore;
607 else if (finalscore < 0)
608 retval = -(LARGEINT - 65 + finalscore);
609 else
610 retval = 0;
611 }
612 }
613 }
614 }
615
616 m_score->add(opponent, number_of_turned);
617 m_score->sub(color, number_of_turned);
618 }
619
620 // Undo the move. Start by unturning the turned pieces.
621 for (int i = number_of_turned; i > 0; i--) {
622 mse = m_squarestack.Pop();
623 m_bc_score->add(opponent, m_bc_board[mse.m_x][mse.m_y]);
624 m_bc_score->sub(color, m_bc_board[mse.m_x][mse.m_y]);
625 m_board[mse.m_x][mse.m_y] = opponent;
626 }
627
628 // Now remove the new piece that we put down.
629 m_board[xplay][yplay] = NoColor;
630 m_score->sub(color, 1);
631 m_bc_score->sub(color, m_bc_board[xplay][yplay]);
632
633 // Return a suitable value.
634 if (number_of_turned < 1 || interrupted())
635 return ILLEGAL_VALUE;
636 else
637 return retval;
638}
639
640
641// Generate all legal moves from the current position, and do a search
642// to see the value of them. This function returns the value of the
643// most valuable move, but not the move itself.
644//
645
646int Engine::TryAllMoves(ChipColor opponent, int level, int cutoffval,
647 quint64 opponentbits, quint64 colorbits)
648{
649 int maxval = -LARGEINT;
650
651 // Keep GUI alive by calling the event loop.
652 yield();
653
654 quint64 null_bits;
655 null_bits = 0;
656
657 for (int x = 1; x < 9; x++) {
658 for (int y = 1; y < 9; y++) {
659 if (m_board[x][y] == NoColor
660 && (m_neighbor_bits[x][y] & colorbits) != null_bits) {
661 int val = ComputeMove2(x, y, opponent, level + 1, maxval, opponentbits,
662 colorbits);
663
664 if (val != ILLEGAL_VALUE && val > maxval) {
665 maxval = val;
666 if (maxval > -cutoffval || interrupted())
667 break;
668 }
669 }
670 }
671
672 if (maxval > -cutoffval || interrupted())
673 break;
674 }
675
676 if (interrupted())
677 return -LARGEINT;
678
679 return maxval;
680}
681
682
683// Calculate a heuristic value for the current position. If we are at
684// the end of the game, do this by counting the pieces. Otherwise do
685// it by combining the score using the number of pieces, and the score
686// using the board control values.
687//
688
689int Engine::EvaluatePosition(ChipColor color)
690{
691 int retval;
692
693 ChipColor opponent = Utils::opponentColorFor(color);
694
695 int score_color = m_score->score(color);
696 int score_opponent = m_score->score(opponent);
697
698 if (m_exhaustive)
699 retval = score_color - score_opponent;
700 else {
701 retval = (100 - m_coeff) *
702 (m_score->score(color) - m_score->score(opponent))
703 + m_coeff * BC_WEIGHT * (m_bc_score->score(color)
704 - m_bc_score->score(opponent));
705 }
706
707 return retval;
708}
709
710
711// Calculate bitmaps for each square, and also for neighbors of each
712// square.
713//
714
715void Engine::SetupBits()
716{
717 //m_coord_bit = new long[9][9];
718 //m_neighbor_bits = new long[9][9];
719
720 quint64 bits = 1;
721
722 // Store a 64 bit unsigned it with the corresponding bit set for
723 // each square.
724 for (int i = 1; i < 9; i++)
725 for (int j = 1; j < 9; j++) {
726 m_coord_bit[i][j] = bits;
727 bits *= 2;
728 }
729
730 // Store a bitmap consisting of all neighbors for each square.
731 for (int i = 1; i < 9; i++)
732 for (int j = 1; j < 9; j++) {
733 m_neighbor_bits[i][j] = 0;
734
735 for (int xinc = -1; xinc <= 1; xinc++)
736 for (int yinc = -1; yinc <= 1; yinc++) {
737 if (xinc != 0 || yinc != 0)
738 if (i + xinc > 0 && i + xinc < 9 && j + yinc > 0 && j + yinc < 9)
739 m_neighbor_bits[i][j] |= m_coord_bit[i + xinc][j + yinc];
740 }
741 }
742}
743
744
745// Set up the board control values that will be used in evaluation of
746// the position.
747//
748
749void Engine::SetupBcBoard()
750{
751 // JAVA m_bc_board = new int[9][9];
752
753 for (int i = 1; i < 9; i++)
754 for (int j = 1; j < 9; j++) {
755 if (i == 2 || i == 7)
756 m_bc_board[i][j] = -1;
757 else
758 m_bc_board[i][j] = 0;
759
760 if (j == 2 || j == 7)
761 m_bc_board[i][j] -= 1;
762 }
763
764 m_bc_board[1][1] = 2;
765 m_bc_board[8][1] = 2;
766 m_bc_board[1][8] = 2;
767 m_bc_board[8][8] = 2;
768
769 m_bc_board[1][2] = -1;
770 m_bc_board[2][1] = -1;
771 m_bc_board[1][7] = -1;
772 m_bc_board[7][1] = -1;
773 m_bc_board[8][2] = -1;
774 m_bc_board[2][8] = -1;
775 m_bc_board[8][7] = -1;
776 m_bc_board[7][8] = -1;
777}
778
779
780// Calculate the board control score.
781//
782
783int Engine::CalcBcScore(ChipColor color)
784{
785 int sum = 0;
786
787 for (int i = 1; i < 9; i++)
788 for (int j = 1; j < 9; j++)
789 if (m_board[i][j] == color)
790 sum += m_bc_board[i][j];
791
792 return sum;
793}
794
795
796// Calculate a bitmap of the occupied squares for a certain color.
797//
798
799quint64 Engine::ComputeOccupiedBits(ChipColor color)
800{
801 quint64 retval = 0;
802
803 for (int i = 1; i < 9; i++)
804 for (int j = 1; j < 9; j++)
805 if (m_board[i][j] == color) retval |= m_coord_bit[i][j];
806
807 return retval;
808}
809
810