summaryrefslogtreecommitdiffstats
path: root/kreversi/Position.cpp
diff options
context:
space:
mode:
authortoma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2009-11-25 17:56:58 +0000
committertoma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2009-11-25 17:56:58 +0000
commitc90c389a8a8d9d8661e9772ec4144c5cf2039f23 (patch)
tree6d8391395bce9eaea4ad78958617edb20c6a7573 /kreversi/Position.cpp
downloadtdegames-c90c389a8a8d9d8661e9772ec4144c5cf2039f23.tar.gz
tdegames-c90c389a8a8d9d8661e9772ec4144c5cf2039f23.zip
Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.
BUG:215923 git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdegames@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da
Diffstat (limited to 'kreversi/Position.cpp')
-rw-r--r--kreversi/Position.cpp366
1 files changed, 366 insertions, 0 deletions
diff --git a/kreversi/Position.cpp b/kreversi/Position.cpp
new file mode 100644
index 00000000..22ffb3cf
--- /dev/null
+++ b/kreversi/Position.cpp
@@ -0,0 +1,366 @@
+/* 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 Position is used to represent an Othello position as white and
+// black pieces and empty squares (see class Score) on an 8x8 Othello board.
+
+
+#include "kdebug.h"
+
+#include "Position.h"
+#include <stdlib.h>
+
+
+Position::Position()
+{
+ setupStartPosition();
+}
+
+
+Position::Position(Position &pos, SimpleMove &move)
+{
+ constrCopy(pos, move);
+}
+
+
+Position &Position::operator=(Position &pos)
+{
+ // Copy the position itself.
+ for (uint row = 0; row < 10; row++)
+ for (uint col = 0; col < 10; col++)
+ m_board[row][col] = pos.m_board[row][col];
+ m_toMove = pos.m_toMove;
+
+ m_score = pos.m_score;
+
+ return *this;
+}
+
+
+// ----------------------------------------------------------------
+// Helpers to the constructors
+
+
+// Construct a Position by copying another one and then make a move.
+//
+
+void Position::constrCopy(Position &pos, SimpleMove &move)
+{
+ *this = pos;
+ doMove(move);
+}
+
+
+// Setup the Position by setting it to the initial Reversi position.
+
+void Position::setupStartPosition()
+{
+ // Initialize the real board
+ for (uint i = 0; i < 10; i++)
+ for (uint j = 0; j < 10; j++)
+ m_board[i][j] = Nobody;
+
+ // The initial position
+ m_board[4][4] = White;
+ m_board[5][5] = White;
+ m_board[5][4] = Black;
+ m_board[4][5] = Black;
+
+ // Black always starts the game in Reversi.
+ m_toMove = Black;
+
+ // Each side starts out with two pieces.
+ m_score.set(White, 2);
+ m_score.set(Black, 2);
+}
+
+
+// ----------------------------------------------------------------
+// Access methods
+
+
+Color Position::color(uint x, uint y) const
+{
+ if (x < 1 || x > 8 || y < 1 || y > 8)
+ return Nobody;
+
+ return m_board[x][y];
+}
+
+
+// ----------------------------------------------------------------
+// Moves in the position
+
+
+// Return true if the move is legal.
+//
+// NOTE: This function does *NOT* test wether the move is done
+// by the color to move. That must be checked separately.
+//
+
+bool Position::moveIsLegal(SimpleMove &move) const
+{
+ if (m_board[move.x()][move.y()] != Nobody)
+ return false;
+
+ Color color = move.color();
+ Color opponent = ::opponent(color);
+
+ // Check in all directions and see if there is a turnable row of
+ // opponent pieces. If there is at least one such row, then the
+ // move is legal.
+ for (int xinc = -1; xinc <= 1; xinc++) {
+ for (int yinc = -1; yinc <= 1; yinc++) {
+ int x, y;
+
+ if (xinc == 0 && yinc == 0)
+ continue;
+
+ // Find the end of such a row of pieces.
+ for (x = move.x()+xinc, y = move.y()+yinc; m_board[x][y] == opponent;
+ x += xinc, y += yinc)
+ ;
+
+ // If the row ends with a piece of our own and there was at
+ // least one opponent piece between it and the move point, then
+ // we have found a turnable row.
+ if (m_board[x][y] == color
+ && (x - xinc != move.x() || y - yinc != move.y()))
+ return true;
+ }
+ }
+
+ return false;
+}
+
+
+// See if 'color' can make a move in the current position. This is
+// independent of wether it is 'color's turn to move or not.
+
+bool Position::moveIsPossible(Color color) const
+{
+ // Make it simple: Step through all squares and see if it is a legal move.
+ for (uint i = 1; i < 9; i++)
+ for (uint j = 1; j < 9; j++) {
+ SimpleMove move(color, i, j);
+
+ if (moveIsLegal(move))
+ return true;
+ }
+
+ return false;
+}
+
+
+// Return true if any side can move. (If not, the game is over.)
+
+bool Position::moveIsAtAllPossible() const
+{
+ return (moveIsPossible(White) || moveIsPossible(Black));
+}
+
+
+// Make a move in the position.
+//
+// Return true if the move was legal, otherwise return false.
+//
+bool Position::doMove(SimpleMove &move, QValueList<char> *turned)
+{
+ if (move.color() == Nobody)
+ return false;
+
+ Color color = move.color();
+ Color opponent = ::opponent(color);
+
+ // Put the piece on the board
+ m_board[move.x()][move.y()] = color;
+ m_score.inc(color);
+
+ // Turn pieces.
+ uint scoreBefore = m_score.score(color);
+ for (int xinc = -1; xinc <= 1; xinc++) {
+ for (int yinc = -1; yinc <= 1; yinc++) {
+ int x, y;
+
+ // Skip the case where both xinc and yinc == 0, since then we
+ // won't move in any direction at all.
+ if (xinc == 0 && yinc == 0)
+ continue;
+
+ // Find the end point (x, y) of a possible row of turnable pieces.
+ for (x = move.x()+xinc, y = move.y()+yinc; m_board[x][y] == opponent;
+ x += xinc, y += yinc)
+ ;
+
+ // If the row was indeed turnable, then do it.
+ if (m_board[x][y] == color) {
+ for (x -= xinc, y -= yinc; x != move.x() || y != move.y();
+ x -= xinc, y -= yinc) {
+ // Turn the piece.
+ m_board[x][y] = color;
+ if (turned)
+ turned->append(10 * x + y);
+
+ // Make the piece count correct again.
+ m_score.inc(color);
+ m_score.dec(opponent);
+ }
+ }
+ }
+ }
+
+ // If nothing was turned, the move wasn't legal.
+ if (m_score.score(color) == scoreBefore) {
+ m_board[move.x()][move.y()] = Nobody;
+ m_score.dec(color);
+
+ return false;
+ }
+
+ // Set the next color to move.
+ if (moveIsPossible(opponent))
+ m_toMove = opponent;
+ else if (moveIsPossible(color))
+ m_toMove = color;
+ else
+ m_toMove = Nobody;
+
+ return true;
+}
+
+
+bool Position::doMove(Move &move)
+{
+ move.m_turnedPieces.clear();
+ return doMove((SimpleMove &) move, &move.m_turnedPieces);
+}
+
+
+bool Position::undoMove(Move &move)
+{
+ Color color = move.color();
+ Color other = opponent(color);
+
+ // Sanity checks
+ // 1. The move must be on the board and be of the right color.
+ if (color != m_board[move.x()][move.y()]) {
+ //kdDebug() << "move on the board is wrong color: " << (int) color << "["
+ // << move.x() << "," << move.y() << "]" << endl;
+ return false;
+ }
+
+ // 2. All turned pieces must be on the board anb be of the right color.
+ QValueList<char>::iterator it;
+ for (it = move.m_turnedPieces.begin();
+ it != move.m_turnedPieces.end();
+ ++it) {
+ int sq = *it;
+
+ if (m_board[sq / 10][sq % 10] != color) {
+ //kdDebug() << "turned piece the board is wrong color: ["
+ // << sq / 10 << "," << sq % 10 << "]" << endl;
+ return false;
+ }
+ }
+
+ // Ok, everything seems allright. Let's do it!
+ // 1. Unturn all the turned pieces.
+ for (it = move.m_turnedPieces.begin();
+ it != move.m_turnedPieces.end();
+ ++it) {
+ int sq = *it;
+
+ m_board[sq / 10][sq % 10] = other;
+ m_score.dec(color);
+ m_score.inc(other);
+ }
+
+ // 2. Remove the move itself.
+ m_score.dec(color);
+ m_board[move.x()][move.y()] = Nobody;
+
+
+ return true;
+}
+
+
+MoveList Position::generateMoves(Color color) const
+{
+ MoveList moves;
+
+ // Make it simple: Step through all squares and see if it is a legal move.
+ for (uint i = 1; i < 9; i++) {
+ for (uint j = 1; j < 9; j++) {
+ Move move(color, i, j);
+
+ if (moveIsLegal(move))
+ moves.append(move);
+ }
+ }
+
+ return moves;
+}
+
+
+QString Position::asString() const
+{
+ QString result;
+
+ for (uint y = 1; y < 9; ++y) {
+ for (uint x = 1; x < 9; ++x) {
+ switch (m_board[x][y]) {
+ case Nobody: result.append(' '); break;
+ case Black: result.append('*'); break;
+ case White: result.append('o'); break;
+ default: result.append('?'); break;
+ }
+ }
+
+ result.append('\n');
+ }
+
+ return result;
+}