toruschess/src/toruschess.cpp

/***************************************************************************
 *   Copyright (C) 2009 by Stefan Bühler                                   *
 *   stbuehler@web.de                                                      *
 *                                                                         *
 *   This program 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 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#include "toruschess.h"
#include "ai.h"

namespace toruschess {

	static void init() {
		static bool done = FALSE;
		if (done) return;
		done = TRUE;
		qRegisterMetaType<Move>("Move");
		qRegisterMetaType<Pos>("Pos");
	}

	QString state2string(GameState state) {
		switch (state) {
		case TURN_WHITE: return "White's turn";
		case TURN_BLACK: return "Black's turn";
		case WON_WHITE: return "White is the winner";
		case WON_BLACK: return "Black is the winner";
		case DRAW: return "Draw game";
		}
		return "Invalid GameState";
	}

	Move::Move(const Field* field, const Pos &from, const Pos &to)
	: m_from(from), m_to(to), m_prevFrom(field->place(from)), m_prevTo(field->place(to)), m_player(field->player(from)) { }

	Move::Move()
	: m_from(), m_to(), m_prevFrom(0), m_prevTo(0), m_player(NOPLAYER) { }

	static const int start_field[8][8] = {
		{ -KNIGHT, -PAWN, -ROOK, 0, 0, 0, 0, 0 },
		{ -BISHOP, -KING, -QUEEN, 0, 0, 0, 0, 0 },
		{ -ROOK, -PAWN, -KNIGHT, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, ROOK, PAWN, KNIGHT, 0 },
		{ 0, 0, 0, 0, QUEEN, KING, BISHOP, 0 },
		{ 0, 0, 0, 0, KNIGHT, PAWN, ROOK, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0 }
	};

	Field::Field()
	: m_wking(5, 5), m_bking(1, 1) {
		memcpy(m_places, start_field, sizeof(start_field));
	}

	void Field::reset() {
		m_wking = Pos(5, 5);
		m_bking = Pos(1, 1);
		memcpy(m_places, start_field, sizeof(start_field));
	}

	void tryDirection(QList<Move> &moves, const Field *field, int thePlace, const Pos &from, int dx, int dy) {
		for (int d = 1; d < 8; d++) {
			Pos to = Pos(from.x() + d*dx, from.y() + d*dy);
			int toPlace = field->place(to);
			if (0 == toPlace) {
// 				qDebug("move 1, %i", d);
				moves.push_back(Move(field, from, to)); /* move */
			} else {
				if (0 > toPlace * thePlace) {
// 					qDebug("beat 1, %i", d);
					moves.push_back(Move(field, from, to)); /* beat */
				} else {
// 					qDebug("hit friend, %i", d);
				}
				for (int c = 7; c > d; c--) {
					to = Pos(from.x() + c*dx, from.y() + c*dy);
					toPlace = field->place(to);
					if (0 == toPlace) {
// 						qDebug("move 2, %i %i", d, c);
						moves.push_back(Move(field, from, to)); /* move */
					} else if (0 > toPlace * thePlace) {
// 						qDebug("beat 2, %i %i", d, c);
						moves.push_back(Move(field, from, to)); /* beat */
						break;
					} else {
// 						qDebug("hit friend, %i %i, (%i, %i) = %i", d, c, to.x(), to.y(), toPlace);
						break;
					}
				}
				break;
			}
		}
	}

	/* 7 == -1 mod 8, 6 == -2: but positive values are needed for (a + b) % 8 >= 0 */
	typedef struct { int x, y; } move_delta;
	static const move_delta moves_pawn_walk[4] = { { 1, 0 }, { 0, 1 }, { 7, 0 }, { 0, 7 } };
	static const move_delta moves_pawn_beat[4] = { { 1, 1 }, { 1, 7 }, { 7, 7 }, { 7, 1 } };
	static const move_delta moves_knight[8] = { { 1, 2 }, { 1, 6 }, { 7, 2 }, { 7, 6 }, { 2, 1 }, { 2, 7 }, { 6, 1 }, { 6, 7 } };
	static const move_delta moves_king[8] = { { 1, 1 }, { 1, 0 }, { 1, 7 }, { 0, 7 }, { 7, 7 }, { 7, 0 }, { 7, 1 }, { 0, 1 } };

	static Pos operator + (const Pos &p, move_delta d) {
		return Pos(p.x() + d.x, p.y() + d.y);
	}

	QList<Move> Field::simpleValidMoves(const Pos &from) const {
		QList<Move> moves;
		int thePlace = place(from);
		Piece thePiece = place2piece(thePlace);
// 		qDebug("simpleValidMoves: %i", thePiece);
		switch (thePiece) {
		case NOPIECE:
			break;
		case PAWN:
			for (int i = 0; i < 4; i++) {
				if (0 == place(from + moves_pawn_walk[i])) {
					moves.push_back(Move(this, from, from + moves_pawn_walk[i]));
				}
				if (0 > thePlace * place(from + moves_pawn_beat[i])) {
					moves.push_back(Move(this, from, from + moves_pawn_beat[i]));
				}
			}
			break;
		case KNIGHT:
			for (int i = 0; i < 8; i++) {
				if (0 >= thePlace * place(from + moves_knight[i])) {
					moves.push_back(Move(this, from, from + moves_knight[i]));
				}
			}
			break;
		case BISHOP:
			tryDirection(moves, this, thePlace, from, 1, 1);
			tryDirection(moves, this, thePlace, from, 1, 7);
			break;
		case ROOK:
			tryDirection(moves, this, thePlace, from, 1, 0);
			tryDirection(moves, this, thePlace, from, 0, 1);
			break;
		case QUEEN:
			tryDirection(moves, this, thePlace, from, 1, 1);
			tryDirection(moves, this, thePlace, from, 1, 7);
			tryDirection(moves, this, thePlace, from, 1, 0);
			tryDirection(moves, this, thePlace, from, 0, 1);
			break;
		case KING:
			for (int i = 0; i < 8; i++) {
				if (0 >= thePlace * place(from + moves_king[i])) {
					moves.push_back(Move(this, from, from + moves_king[i]));
				}
			}
			break;
		}
// 		qDebug("simpleValidMoves: found %i", moves.size());
		return moves;
	}
	
	QList<Move> Field::validMoves(const Pos &from) const {
		QList<Move> moves = simpleValidMoves(from);
		QList<Move> resMoves;
		Field testField(*this);
		Player pl = player(from);
		foreach(Move m, moves) {
			Q_ASSERT(validMove(m));
			testField.move_unchecked(m);
			if (!testField.inCheck(pl)) {
				resMoves.push_back(m);
			}
			testField.undo_unchecked(m);
		}
		return resMoves;
	}
	
	static bool checkReach(const Field *field, const Pos &from, const Pos &dest, int dx, int dy) {
		for (int d = 1; d < 8; d++) {
			Pos to = Pos(from.x() + d*dx, from.y() + d*dy);
			if (dest == to) return true;
			int toPlace = field->place(to);
			if (0 == toPlace) {
				continue;
			} else {
				for (int c = 7; c > d; c--) {
					to = Pos(from.x() + c*dx, from.y() + c*dy);
					if (dest == to) return true;
					toPlace = field->place(to);
					if (0 == toPlace) {
						continue;
					} else {
						return false;
					}
				}
				return false;
			}
		}
		return false;
	}
	
	bool Field::validMove(const Move &m) const {
		if (player(m.from()) != m.player()) return false;
		if (m.player() == NOPLAYER) return false;
		if (place(m.from()) != m.prevFrom() || place(m.to()) != m.prevTo()) return false;
		if (player(m.to()) == m.player()) return false;
		switch (piece(m.from())) {
		case NOPIECE:
			return false;
		case PAWN: {
			int dx = (8 + m.from().x() - m.to().x()) % 8, dy = (8 + m.from().y() - m.to().y()) % 8;
			if ((dx > 1 && dx < 7) || (dy > 1 && dy < 7)) return false;
			if (dx != 0 && dy != 0) return player(m.to()) != NOPLAYER; /* beat */
			return player(m.to()) == NOPLAYER; /* walk */
		}
		case KNIGHT: {
			int dx = (8 + m.from().x() - m.to().x()) % 8, dy = (8 + m.from().y() - m.to().y()) % 8;
			return ((dx == 2 || dx == 6) && (dy == 1 || dy == 7)) || ((dx == 1 || dx == 7) && (dy == 2 || dy == 6));
		}
		case BISHOP: {
			int dx = (8 + m.from().x() - m.to().x()) % 8, dy = (8 + m.from().y() - m.to().y()) % 8;
			if (dx == dy) {
				if (dx == 4) {
					return checkReach(this, m.from(), m.to(), 1, 1) || checkReach(this, m.from(), m.to(), 1, 7);
				} else {
					return checkReach(this, m.from(), m.to(), 1, 1);
				}
			} else if (dx + dy == 8) {
				return checkReach(this, m.from(), m.to(), 1, 7);
			} else {
				return false;
			}
		}
		case ROOK: {
			int dx = (8 + m.from().x() - m.to().x()) % 8, dy = (8 + m.from().y() - m.to().y()) % 8;
			if (dy == 0) {
				return checkReach(this, m.from(), m.to(), 1, 0);
			} else if (dx == 0) {
				return checkReach(this, m.from(), m.to(), 0, 1);
			} else {
				return false;
			}
		}
		case QUEEN: {
			int dx = (8 + m.from().x() - m.to().x()) % 8, dy = (8 + m.from().y() - m.to().y()) % 8;
			if (dx == dy) {
				if (dx == 4) {
					return checkReach(this, m.from(), m.to(), 1, 1) || checkReach(this, m.from(), m.to(), 1, 7);
				} else {
					return checkReach(this, m.from(), m.to(), 1, 1);
				}
			} else if (dx + dy == 8) {
				return checkReach(this, m.from(), m.to(), 1, 7);
			} else if (dy == 0) {
				return checkReach(this, m.from(), m.to(), 1, 0);
			} else if (dx == 0) {
				return checkReach(this, m.from(), m.to(), 0, 1);
			} else {
				return false;
			}
		}
		case KING: {
			int dx = (8 + m.from().x() - m.to().x()) % 8, dy = (8 + m.from().y() - m.to().y()) % 8;
			if ((dx > 1 && dx < 7) || (dy > 1 && dy < 7)) return false;
			return true;
		}
		}
		return false;
	}
	
	void Field::move_unchecked(const Move &m) {
		place(m.from()) = 0;
		place(m.to()) = m.prevFrom();
		if (m.prevFrom() == KING) {
			m_wking = m.to();
		} else if (m.prevFrom() == -KING) {
			m_bking = m.to();
		}
	}
	
	void Field::undo_unchecked(const Move &m) {
		place(m.from()) = m.prevFrom();
		place(m.to()) = m.prevTo();
		if (m.prevFrom() == KING) {
			m_wking = m.from();
		} else if (m.prevFrom() == -KING) {
			m_bking = m.from();
		}
	}
	
	bool Field::move(const Move &m) {
		if (!m.valid()) return false;
		if (!validMove(m)) return false;
		move_unchecked(m);
		if (inCheck(m.player())) {
			undo_unchecked(m);
			return false;
		}
		return true;
	}
	bool Field::undo(const Move &m) {
		if (place(m.from()) != 0 || place(m.to()) != m.prevFrom()) return false;
		undo_unchecked(m);
		return true;
	}
	
	bool Field::inCheck(Player player, const Pos &pking) const {
		for (int x = 0; x < 8; x++) for (int y = 0; y < 8; y++) {
			Pos curp(x, y);
			if (0 > place(curp) * player && validMove(Move(this, curp, pking))) {
				return true;
			}
		}
		return false;
	}
	
	bool Field::inCheck(Player p) const {
		const Pos &pos = (p == WHITE) ? m_wking : m_bking;
		if (player(pos) != p || piece(pos) != KING) return false;
		return inCheck(p, pos);
	}
	
	Game::Game(QObject *parent)
	: QObject(parent), m_field(new Field()), m_state(TURN_WHITE), m_gameMode(HUMAN_COMPUTER), m_aiStrength(2), m_aiThread(0) {
		init();
	}

	Game::~Game() {
		delete m_field;
	}
	
	bool Game::move(const Move &m) {
		if (m_aiThread) return false;
		if (!m.valid()) return false;
		switch (m_state) {
		case TURN_WHITE:
			if (m.player() != WHITE) return false;
			break;
		case TURN_BLACK:
			if (m.player() != BLACK) return false;
			break;
		default:
			return false;
		}
		if (m_field->move(m)) {
			m_moves.push_back(m);
			if (m_state == TURN_WHITE) {
				m_state = TURN_BLACK;
				if (possibleMoves().empty()) {
					if (m_field->inCheck(BLACK)) {
						m_state = WON_WHITE;
					} else {
						m_state = DRAW;
					}
				}
			} else {
				m_state = TURN_WHITE;
				if (possibleMoves().empty()) {
					if (m_field->inCheck(WHITE)) {
						m_state = WON_BLACK;
					} else {
						m_state = DRAW;
					}
				}
			}
			checkAI();
			emit moved(m);
			emit changed(m_state);
			emit updated();
			return true;
		}
		return false;
	}
	
	void Game::restart() {
		m_state = TURN_WHITE;
		m_field->reset();
		checkAI();
		emit changed(m_state);
		emit started();
		emit updated();
	}
	
	QList<Move> Game::possibleMoves() const {
		Player player = NOPLAYER;
		switch (m_state) {
		case TURN_WHITE:
			player = WHITE;
			break;
		case TURN_BLACK:
			player = BLACK;
			break;
		default:
			return QList<Move>();
		}
		QList<Move> moves;
		for (int x = 0; x < 8; x++) for (int y = 0; y < 8; y++) {
			Pos curp(x, y);
			if (0 < m_field->place(curp) * player)
				moves += m_field->validMoves(curp);
		}
		return moves;
	}
	
	void Game::setGameMode(GameMode gm) {
		m_gameMode = gm;
		checkAI();
		emit changedMode(m_gameMode);
	}
	
	void Game::setAiStrength(int s) {
		m_aiStrength = qMin(7, qMax(2, s));
		emit changedAIStrength(m_aiStrength);
	}
	
	void Game::checkAI() {
		if (m_aiThread) {
			switch (m_gameMode) {
			case HUMAN_HUMAN:
				m_ignoreAI = true;
				break;
			case HUMAN_COMPUTER:
				if (m_state != TURN_BLACK) m_ignoreAI = true;
				break;
			case COMPUTER_HUMAN:
				if (m_state != TURN_WHITE) m_ignoreAI = true;
				break;
			case COMPUTER_COMPUTER:
				break;
			}
		} else {
			Player curp = NOPLAYER;
			switch (m_state) {
			case TURN_WHITE:
				curp = WHITE;
				break;
			case TURN_BLACK:
				curp = BLACK;
				break;
			default:
				return;
			}
			switch (m_gameMode) {
			case HUMAN_HUMAN:
				return;
			case HUMAN_COMPUTER:
				if (m_state != TURN_BLACK) return;
				break;
			case COMPUTER_HUMAN:
				if (m_state != TURN_WHITE) return;
				break;
			case COMPUTER_COMPUTER:
				break;
			}
			m_aiThread = new GameAIThread(*m_field, curp, m_aiStrength, this);
			m_ignoreAI = false;
			connect(m_aiThread, SIGNAL(aiFinished(Move)), this, SLOT(finishedAI(Move)));
			m_aiThread->start();
		}
	}
	
	void Game::finishedAI(Move m) {
		m_aiThread->wait();
		delete m_aiThread;
		m_aiThread = 0;
		if (!m_ignoreAI) {
			move(m);
		}
		checkAI();
	}
	
	GameAIThread::GameAIThread(const Field &field, Player curp, int depth, QObject *parent)
	: QThread(parent), m_field(field), m_curp(curp), m_depth(depth) {
	}
	
	void GameAIThread::run() {
		Move m = ai::getMove(m_field, m_curp, m_depth);
		emit aiFinished(m);
	}
	
}