Initial git commit.

1 files changed, 1266 insertions, 0 deletions

diff --git a/game.cpp b/game.cpp
new file mode 100644
index 0000000..1e32e61
--- /dev/null
+++ b/game.cpp
@@ -0,0 +1,1266 @@
+/*
+ *  Quackle -- Crossword game artificial intelligence and analysis tool
+ *  Copyright (C) 2005-2006 Jason Katz-Brown and John O'Laughlin.
+ *
+ *  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., 51 Franklin Street, Fifth Floor, Boston, MA  
+ *  02110-1301  USA
+ */
+
+#include <iostream>
+#include <sstream>
+
+#include "computerplayer.h"
+#include "datamanager.h"
+#include "enumerator.h"
+#include "evaluator.h"
+#include "gameparameters.h"
+#include "game.h"
+#include "generator.h"
+
+// define this to get warnings when there's a problem bag
+#define DEBUG_BAG
+
+using namespace Quackle;
+
+Game::Game()
+	: m_defaultComputerPlayer(0)
+{
+	reset();
+}
+
+Game::~Game()
+{
+}
+
+void Game::reset()
+{
+	m_positions.clear();
+
+	m_title = UVString();
+	m_description = UVString();
+
+	PlayerList dummyPlayers;
+	dummyPlayers.push_back(Player(MARK_UV("Dummy"), Quackle::Player::HumanPlayerType, 0));
+	setPlayers(dummyPlayers);
+}
+
+void Game::setPlayers(const PlayerList &list)
+{
+	PlayerList idedPlayers(list);
+	const PlayerList::iterator end(idedPlayers.end());
+	int i = 0;
+	for (PlayerList::iterator it = idedPlayers.begin(); it != end; ++it, ++i)
+		(*it).setId(i);
+
+	m_positions.setPlayers(idedPlayers);
+}
+
+void Game::addPosition()
+{
+	addClonePosition();
+	m_positions.lastPosition().incrementTurn();
+
+	m_positions.setCurrentLocation(m_positions.lastLocation());
+
+	// start with move list afresh
+	m_positions.lastPosition().removeAllMoves();
+
+	// don't reset if game is over as increment might
+	// have set the move made to be an unused tile bonus
+	if (!m_positions.lastPosition().gameOver())
+		resetCandidature();
+}
+
+void Game::addClonePosition()
+{
+	m_positions.eraseAfter(m_positions.currentLocation());
+
+	if (m_positions.empty())
+		m_positions.push_back(GamePosition(m_positions.players()));
+	else
+		m_positions.push_back(m_positions.lastPosition());
+}
+
+void Game::setCurrentPosition(const GamePosition &position)
+{
+	currentPosition() = position;
+	setCurrentPosition(position.location());
+}
+
+void Game::associateComputerPlayer(int playerId, ComputerPlayer *computerPlayer)
+{
+	m_computerPlayers[playerId] = computerPlayer;
+}
+
+void Game::associateKnownComputerPlayers()
+{
+	const PlayerList::const_iterator end(m_positions.players().end());
+	for (PlayerList::const_iterator it = m_positions.players().begin(); it != end; ++it)
+	{
+		if ((*it).type() == Player::ComputerPlayerType)
+		{
+			ComputerPlayer *computerPlayer = (*it).computerPlayer();
+
+			if (computerPlayer)
+				associateComputerPlayer((*it).id(), computerPlayer);
+		}
+	}
+}
+
+ComputerPlayer *Game::computerPlayer(int playerId)
+{
+	if (m_computerPlayers.find(playerId) == m_computerPlayers.end())
+		return defaultComputerPlayer();
+	
+	return m_computerPlayers[playerId];
+}
+
+void Game::setDefaultComputerPlayer(ComputerPlayer *computerPlayer)
+{
+	m_defaultComputerPlayer = computerPlayer;
+}
+
+ComputerPlayer *Game::defaultComputerPlayer()
+{
+	if (m_defaultComputerPlayer)
+		return m_defaultComputerPlayer;
+	
+	m_defaultComputerPlayer = new StaticPlayer;
+	return m_defaultComputerPlayer;
+}
+
+Move Game::haveComputerPlay(ComputerPlayer *computerPlayer)
+{
+	if (currentPosition().gameOver())
+		return Move::createNonmove();
+
+	if (!computerPlayer)
+		computerPlayer = this->computerPlayer(currentPosition().currentPlayer().id());
+	
+	computerPlayer->setPosition(currentPosition());
+
+	Move move(computerPlayer->move());
+	commitMove(move);
+	return move;
+}
+
+void Game::advanceToNoncomputerPlayer()
+{
+	while (!currentPosition().gameOver() && currentPosition().currentPlayer().type() == Player::ComputerPlayerType)
+		haveComputerPlay();
+}
+
+void Game::commitCandidate(bool maintainBoard)
+{
+	if (currentPosition().gameOver())
+		return;
+
+	currentPosition().prepareForCommit();
+	Move moveMade(currentPosition().moveMade());
+	addPosition();
+
+	// Note this comes after addPosition --
+	// ensuring exchanged tiles can't be drawn.
+	// TODO how does this ensure that exchanged tiles can't be drawn?
+	currentPosition().makeMove(moveMade, maintainBoard);
+}
+
+void Game::commitMove(const Move &move)
+{
+	setCandidate(move);
+	commitCandidate();
+}
+
+///////////
+
+GamePosition::GamePosition(const PlayerList &players)
+	: m_players(players), m_currentPlayer(m_players.end()), m_playerOnTurn(m_players.end()), m_turnNumber(0), m_nestedness(0), m_scorelessTurnsInARow(0), m_gameOver(false)
+{
+	setEmptyBoard();
+	resetMoveMade();
+	resetBag();
+}
+
+GamePosition::GamePosition(const GamePosition &position)
+	: m_players(position.m_players), m_moves(position.m_moves), m_moveMade(position.m_moveMade), m_committedMove(position.m_committedMove), m_turnNumber(position.m_turnNumber), m_nestedness(position.m_nestedness), m_scorelessTurnsInARow(position.m_scorelessTurnsInARow), m_gameOver(position.m_gameOver), m_board(position.m_board), m_bag(position.m_bag), m_drawingOrder(position.m_drawingOrder), m_explanatoryNote(position.m_explanatoryNote)
+{
+	// reset iterator
+	if (position.turnNumber() == 0)
+	{
+		m_currentPlayer = m_players.end();
+		m_playerOnTurn = m_players.end();
+	}
+	else
+	{
+		setCurrentPlayer(position.currentPlayer().id());
+		setPlayerOnTurn(position.currentPlayer().id());
+	}
+}
+
+const GamePosition &GamePosition::operator=(const GamePosition &position)
+{
+	m_players = position.m_players;
+	m_moves = position.m_moves;
+	m_moveMade = position.m_moveMade;
+	m_committedMove = position.m_committedMove;
+	m_turnNumber = position.m_turnNumber;
+	m_nestedness = position.m_nestedness;
+	m_scorelessTurnsInARow = position.m_scorelessTurnsInARow;
+	m_gameOver = position.m_gameOver;
+	m_board = position.m_board;
+	m_bag = position.m_bag;
+	m_drawingOrder = position.m_drawingOrder;
+	m_explanatoryNote = position.m_explanatoryNote;
+
+	// reset iterator
+	if (position.turnNumber() == 0)
+	{
+		m_currentPlayer = m_players.end();
+		m_playerOnTurn = m_players.end();
+	}
+	else
+	{
+		setCurrentPlayer(position.currentPlayer().id());
+		setPlayerOnTurn(position.currentPlayer().id());
+	}
+	return *this;
+}
+
+GamePosition::GamePosition()
+	: m_currentPlayer(m_players.end()), m_playerOnTurn(m_players.end()), m_turnNumber(0), m_nestedness(0), m_scorelessTurnsInARow(0), m_gameOver(false) 
+{
+	setEmptyBoard();
+	resetMoveMade();
+	resetBag();
+}
+
+void GamePosition::kibitz(int nmoves)
+{
+	Generator generator(*this);
+	generator.kibitz(nmoves, exchangeAllowed()? Generator::RegularKibitz : Generator::CannotExchange);
+
+	m_moves = generator.kibitzList();
+
+	const MoveList::iterator end(m_moves.end());
+	for (MoveList::iterator it = m_moves.begin(); it != end; ++it)
+		ensureMovePrettiness(*it);
+}
+
+const Move &GamePosition::staticBestMove()
+{
+	kibitz(1);
+	return m_moves.back();
+}
+
+void GamePosition::removeMove(const Quackle::Move &move)
+{
+	const MoveList::iterator end(m_moves.end());
+	for (MoveList::iterator it = m_moves.begin(); it != end; ++it)
+	{
+		if ((*it) == move)
+		{
+			m_moves.erase(it);
+			break;
+		}
+	}
+}
+
+void GamePosition::removeAllMoves()
+{
+	m_moves.clear();
+}
+
+void GamePosition::ensureMovePrettiness(Move &move)
+{
+	if (move.prettyTiles().empty())
+		move.setPrettyTiles(m_board.prettyTilesOfMove(move));
+}
+
+void GamePosition::ensureMoveTilesDoNotIncludePlayThru(Move &move)
+{
+	move.setTiles(m_board.sanitizedTilesOfMove(move));
+}
+
+void GamePosition::addMove(const Move &move)
+{
+	if (move.isAMove())
+	{
+		Move prettifiedMove(move);
+		ensureMoveTilesDoNotIncludePlayThru(prettifiedMove);
+		ensureMovePrettiness(prettifiedMove);
+		m_moves.push_back(prettifiedMove);
+
+		MoveList::sort(m_moves, MoveList::Win);
+	}
+}
+
+void GamePosition::makeSureMoveListContainsMoves(const MoveList &moves)
+{
+	for (MoveList::const_iterator it = moves.begin(); it != moves.end(); ++it)
+		if (!m_moves.contains(*it))
+			addMove(*it);
+}
+
+void GamePosition::kibitzAs(ComputerPlayer *computerPlayer, int nmoves)
+{
+	computerPlayer->setPosition(*this);
+	setMoves(computerPlayer->moves(nmoves));
+}
+
+void GamePosition::addAndSetMoveMade(const Move &move)
+{
+	addMove(move);
+	setMoveMade(move);
+}
+
+int GamePosition::validateMove(const Move &move) const
+{
+	int ret = ValidMove;
+
+	switch (move.action)
+	{
+	case Move::Place:
+	case Move::Exchange:
+		if (!currentPlayer().rack().contains(move.usedTiles()))
+			ret |= InvalidTiles;
+
+		if (move.action == Move::Place)
+		{
+			// Place action -- ensure the word connects to others
+			if (!isConnected(move))
+				ret |= InvalidPlace;
+
+			if (m_board.isUnacceptableOpeningMove(move))
+				ret |= InvalidOpeningPlace;
+
+			// check if the word is acceptable
+			if (!formsAcceptableWords(move))
+				ret |= UnacceptableWord;
+		}
+		else
+		{
+			// Exchange action -- ensure there are enough tiles in bag
+			if (!exchangeAllowed())
+				ret |= TooLateExchange;
+		}
+		break;
+	
+	case Move::UnusedTilesBonus:
+	case Move::TimePenalty:
+		ret = InvalidAction;
+		break;
+
+	case Move::Pass:
+	case Move::Nonmove:
+		break;
+	}
+
+	return ret;
+}
+
+bool GamePosition::isConnected(const Move &move) const
+{
+	return m_board.isConnected(move);
+}
+
+bool GamePosition::formsAcceptableWords(const Move &move) const
+{
+	vector<Move> words = m_board.allWordsFormedBy(move);
+
+	for (vector<Move>::const_iterator it = words.begin(); it != words.end(); ++it)
+	{
+		if (!isAcceptableWord((*it).wordTiles()))
+			return false;
+	}
+	
+	return true;
+}
+
+MoveList GamePosition::allWordsFormedBy(const Move &move) const
+{
+    return m_board.allWordsFormedBy(move);
+}
+
+bool GamePosition::isAcceptableWord(const LetterString &word) const
+{
+	Generator generator;
+	return generator.isAcceptableWord(word);
+}
+
+bool GamePosition::exchangeAllowed() const
+{
+	return m_bag.size() >= QUACKLE_PARAMETERS->minimumTilesForExchange();
+}
+
+int GamePosition::handleOverdraw(const LetterString &letters, LetterString *throwback) const
+{
+	if (!unseenBag().removeLetters(letters))
+		return OverdrawnTilesNotUnseen;
+
+	if (letters.size() <= QUACKLE_PARAMETERS->overdrawPenalty())
+		return InvalidOverdrawNumber;
+
+	ProbableRackList racks;
+	Bag bag(letters);
+	Enumerator enumerator(bag);
+	enumerator.enumerate(&racks, QUACKLE_PARAMETERS->overdrawPenalty());
+
+	double minimumLeaveValue = 99999;
+
+	for (ProbableRackList::const_iterator it = racks.begin(); it != racks.end(); ++it)
+	{
+		double value = leaveValue((*it).rack.tiles());
+
+		if (value < minimumLeaveValue)
+		{
+			Rack rack(letters);
+			rack.unload((*it).rack.tiles());
+			*throwback = (Rack(letters) - (*it).rack).tiles();
+			minimumLeaveValue = value;
+		}
+	}
+	return ValidOverdraw;
+}
+
+void GamePosition::makeMove(const Move &move, bool maintainBoard)
+{
+	if (!move.isChallengedPhoney())
+	{
+		Generator generator(*this);
+		generator.makeMove(move, maintainBoard);
+		m_board = generator.position().board();
+	}
+
+	if (move.action == Move::Exchange)
+		m_bag.toss(move.usedTiles());
+}
+
+void GamePosition::scoreMove(Move &move)
+{
+	move.score = calculateScore(move);
+	move.equity = calculateEquity(move);
+}
+
+void GamePosition::ensureBoardIsPreparedForAnalysis()
+{
+	Generator generator(*this);
+	generator.allCrosses();
+	m_board = generator.position().board();
+}
+
+int GamePosition::calculateScore(const Move &move)
+{
+	return m_board.score(move);
+}
+
+double GamePosition::calculateEquity(const Move &move)
+{
+	return QUACKLE_EVALUATOR->equity(*this, move);
+}
+
+double GamePosition::calculatePlayerConsideration(const Move &move)
+{
+	return QUACKLE_EVALUATOR->playerConsideration(*this, move);
+}
+
+double GamePosition::leaveValue(const LetterString &leave) const
+{
+	return QUACKLE_EVALUATOR->leaveValue(leave);
+}
+
+double GamePosition::calculateSharedConsideration(const Move &move)
+{
+	return QUACKLE_EVALUATOR->sharedConsideration(*this, move);
+}
+
+Bag GamePosition::unseenBag() const
+{
+	return unseenBagFromPlayerPerspective(currentPlayer());
+}
+
+Bag GamePosition::unseenBagFromPlayerPerspective(const Player &player) const
+{
+	// one way:
+	//Bag ret(m_board.tilesNotOnBoard());
+	//ret.removeLetters(currentPlayer().rack().usedTiles());
+
+	// other way:
+	Bag ret(m_bag);
+	const PlayerList::const_iterator end(m_players.end());
+	for (PlayerList::const_iterator it = m_players.begin(); it != end; ++it)
+	{
+		if (!((*it) == player))
+		{
+			ret.toss((*it).rack());
+		}
+	}
+	
+	return ret;
+}
+
+void GamePosition::ensureProperBag() const
+{
+#ifdef DEBUG_BAG
+	Bag allTiles(m_board.tilesOnBoard());
+
+	UVString debugString;
+
+	Bag racks;
+	racks.clear();
+
+	const PlayerList::const_iterator end(m_players.end());
+	for (PlayerList::const_iterator it = m_players.begin(); it != end; ++it)
+	{
+		allTiles.toss((*it).rack());
+		racks.toss((*it).rack());
+	}
+	
+	allTiles.toss(m_bag.shuffledTiles());
+	
+	Bag fullDistribution;
+
+	bool mismatch = false;
+
+	char allTilesCounts[QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE];
+	char fullCounts[QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE];
+	allTiles.letterCounts(allTilesCounts);
+	fullDistribution.letterCounts(fullCounts);
+
+	for (Letter letter = 0; letter <= QUACKLE_ALPHABET_PARAMETERS->lastLetter(); ++letter)
+	{
+		if (allTilesCounts[(int)(letter)] != fullCounts[(int)(letter)])
+		{
+			mismatch = true;
+			if (debugString.empty()) {
+			    debugString += MARK_UV("-------------------------\n");
+			    debugString += MARK_UV("tiles on board: ");
+			    debugString += m_board.tilesOnBoard().toString() + MARK_UV("\n");
+			    debugString += MARK_UV("racks: ") + racks.toString() + MARK_UV("\n");
+			    debugString += MARK_UV("bag: ") + m_bag.toString() + MARK_UV("\n");
+			    debugString += MARK_UV("All tiles: ") + allTiles.toString() + MARK_UV("\n");
+			}
+			debugString += MARK_UV("Letter doesn't match: ") + QUACKLE_ALPHABET_PARAMETERS->userVisible(letter) + MARK_UV("\n");
+		}
+	}
+	if (mismatch)
+	{
+		UVcout << "********* PROBLEM PROBLEM *********" << endl;
+		UVcout << debugString;
+		UVcout << "-------------------------" << endl;
+	}
+#endif
+}
+
+void GamePosition::setEmptyBoard()
+{
+	m_board.prepareEmptyBoard();
+}
+
+const Player &GamePosition::humanPlayer() const
+{
+	if (currentPlayer().type() == Player::HumanPlayerType)
+		return currentPlayer();
+	bool found;
+	return *nextPlayerOfType(Player::HumanPlayerType, found);
+}
+
+void GamePosition::replenishAndSetRack(const Rack &previousRack, Player &player)
+{
+#ifdef VERBOSE_DEBUG_BAG
+	UVcout << "replenishAndSetRack(" << previousRack << ", " << player << ")" << endl;
+#endif
+	Rack newRack(previousRack);
+
+#ifdef VERBOSE_DEBUG_BAG
+	UVcout << "(Before refill) " << m_bag << endl;
+#endif
+
+	if (m_drawingOrder.empty())
+		m_bag.refill(newRack);
+	else
+		m_drawingOrder = m_bag.refill(newRack, m_drawingOrder);
+
+	player.setRack(newRack);
+	player.setDrawnLetters(newRack - previousRack);
+
+#ifdef VERBOSE_DEBUG_BAG
+	UVcout << "(After  refill) " << m_bag << endl;
+	UVcout << "Rack refilled to " << newRack << endl;
+#endif
+}
+
+void GamePosition::setCurrentPlayerRack(const Rack &rack, bool adjustBag)
+{
+	setPlayerRack(currentPlayer().id(), rack, adjustBag);
+}
+
+UVString GamePosition::nestednessIndentation() const
+{
+	UVString ret;
+	for (unsigned int i = 0; i < m_nestedness; ++i)
+		ret += MARK_UV("\t");
+	return ret;
+}
+
+void GamePosition::setOppRack(const Rack &rack, bool adjustBag)
+{
+	int oppID;
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+		if ((*it).id() != currentPlayer().id())
+		{
+			m_bag.toss((*it).rack());
+			(*it).setRack(Rack(""));
+			oppID = (*it).id();
+			setPlayerRack(oppID, rack, adjustBag);
+			return;
+		}
+}
+
+// TODO(jasonkb): this function is poorly implemented. Also it should return a reference.
+Rack GamePosition::oppRack()
+{
+	UVcout << "currentPlayer(): " << currentPlayer() << endl;
+	
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+		UVcout << "rack " << *it << " " << (*it).rack() << endl;
+
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+	{
+		if ((*it).id() != currentPlayer().id())
+		{
+			return (*it).rack();
+		}
+	}
+
+	return Rack();
+}
+
+void GamePosition::setPlayerRack(int playerID, const Rack &rack, bool adjustBag)
+{
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+	{
+		if ((*it).id() == playerID)
+		{
+			// restore bag
+			if (adjustBag)
+			{
+				// please be correct code
+				m_bag.toss((*it).rack() - rack);
+				removeLetters((rack - (*it).rack()).tiles());
+			}
+
+			(*it).setRack(rack);
+		}
+	}
+}
+
+bool GamePosition::canSetCurrentPlayerRackWithoutBagExpansion(const Rack &rack) const
+{
+	return canSetPlayerRackWithoutBagExpansion(currentPlayer().id(), rack);
+}
+
+bool GamePosition::canSetPlayerRackWithoutBagExpansion(int playerID, const Rack &rack) const
+{
+        (void) playerID;
+	Bag someTiles(m_bag);
+
+	const PlayerList::const_iterator end(m_players.end());
+	for (PlayerList::const_iterator it = m_players.begin(); it != end; ++it)
+		someTiles.toss((*it).rack());
+	
+	// Now we have a bag with all tiles not on the board
+	return someTiles.removeLetters(rack.tiles());
+}
+
+bool GamePosition::setCurrentPlayer(int playerID)
+{
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+	{
+		if ((*it).id() == playerID)
+		{
+			m_currentPlayer = it;
+			return true;
+		}
+	}
+	
+	m_currentPlayer = m_players.begin();
+	return false;
+}
+
+bool GamePosition::setPlayerOnTurn(int playerID)
+{
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+	{
+		if ((*it).id() == playerID)
+		{
+			m_playerOnTurn = it;
+			return true;
+		}
+	}
+	
+	m_playerOnTurn = m_players.begin();
+	return false;
+}
+
+void GamePosition::prepareForCommit()
+{
+	setCommittedMove(moveMade());
+}
+
+Board GamePosition::boardAfterMoveMade() const
+{
+	Board ret(m_board);
+	ret.makeMove(m_moveMade);
+	return ret;
+}
+
+void GamePosition::resetMoveMade()
+{
+	m_moveMade = Move::createNonmove();
+	m_committedMove = Move::createNonmove();
+}
+
+void GamePosition::resetBag()
+{
+	m_bag.prepareFullBag();
+}
+
+bool GamePosition::incrementTurn()
+{
+	if (gameOver() || m_players.empty())
+		return false;
+
+	PlayerList::iterator previousCurrentPlayer(m_currentPlayer);
+
+	bool ret = false;
+
+	// if current player is players.end(), we haven't started game
+	// and go to first player after incrementing
+	if (m_currentPlayer != m_players.end())
+	{
+		Rack remainingRack(currentPlayer().rack() - m_moveMade);
+
+		Rack moveTiles(m_moveMade.usedTiles());
+		moveTiles.unload(currentPlayer().rack().tiles());
+
+		// now moveTiles is the tiles that are in play but not on rack
+		removeLetters(moveTiles.tiles());
+
+		// update our current player's score before possibly
+		// adding endgame bonuses
+		currentPlayer().addToScore(m_moveMade.effectiveScore());
+
+		// player played out
+		if (m_bag.empty() && remainingRack.empty())
+		{
+			// magic!
+			++m_turnNumber;
+
+			if (!m_gameOver)
+			{
+				// we become over based on player playing out
+				// with empty bag
+				adjustScoresToFinishGame();
+
+				m_gameOver = true;
+			}
+		}
+
+		if ((m_moveMade.action == Move::Place && m_moveMade.effectiveScore() == 0) || m_moveMade.action == Move::Exchange || m_moveMade.action == Move::Pass)
+			++m_scorelessTurnsInARow;
+		else
+			m_scorelessTurnsInARow = 0;
+
+		if (!m_gameOver)
+		{
+			if (QUACKLE_PARAMETERS->numberOfScorelessTurnsThatEndsGame() >= 0 && m_scorelessTurnsInARow >= QUACKLE_PARAMETERS->numberOfScorelessTurnsThatEndsGame() && !m_board.isEmpty())
+			{
+				// magic!
+				++m_turnNumber;
+
+				adjustScoresToFinishPassedOutGame();
+
+				m_gameOver = true;
+			}
+		}
+
+		// refill rack of player that just played
+		replenishAndSetRack(remainingRack);
+
+		// now move onto next player
+		++m_currentPlayer;
+	}
+
+	if (m_currentPlayer == m_players.end())
+	{
+		++m_turnNumber;
+		m_currentPlayer = m_players.begin();
+		ret = true;
+	}
+
+	// ensure players get a rack at the beginning of the game,
+	// and that the first player draws first (even though yes
+	// olaugh I realize that it doesn't matter :-)
+	if (currentPlayer().rack().empty())
+		replenishAndSetRack(currentPlayer().rack());
+
+	// refill rack of any player whose rack is empty (again for
+	// beginning of game)
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+		if ((*it).rack().empty())
+			replenishAndSetRack((*it).rack(), *it);
+
+	// freeze current player as last person who played out
+	if (gameOver())
+		m_currentPlayer = previousCurrentPlayer;
+
+	m_playerOnTurn = m_currentPlayer;
+
+	// kill drawing order
+	m_drawingOrder = LetterString();
+
+	// reset note to a clean slate
+	m_explanatoryNote = UVString();
+
+	return ret;
+}
+
+bool GamePosition::removeLetters(const LetterString &letters)
+{
+	bool ret = true;
+
+	const LetterString::const_iterator end(letters.end());
+	for (LetterString::const_iterator it = letters.begin(); it != end; ++it)
+	{
+#ifdef VERBOSE_DEBUG_BAG
+		UVcout << "removeLetters processing " << QUACKLE_ALPHABET_PARAMETERS->userVisible(*it) << endl;
+#endif
+
+		const bool removedFromBag = m_bag.removeLetter(*it);
+		if (removedFromBag)
+		{
+#ifdef VERBOSE_DEBUG_BAG
+			UVcout << "removed from bag" << endl;
+#endif
+		}
+		else
+		{
+			bool removedFromPlayer = false;
+			const PlayerList::iterator playersEnd(m_players.end());
+			for (PlayerList::iterator playerIt = m_players.begin(); playerIt != playersEnd; ++playerIt)
+			{
+				if (*playerIt == currentPlayer())
+					continue;
+
+				LetterString letterString;
+				letterString += (*it);
+
+				Rack newRack((*playerIt).rack());
+				removedFromPlayer = newRack.unload(letterString);
+				if (removedFromPlayer)
+				{
+					replenishAndSetRack(newRack, *playerIt);
+					break;
+				}
+			}
+
+			if (removedFromPlayer)
+			{
+#ifdef VERBOSE_DEBUG_BAG
+				UVcout << "removed from player" << endl;
+#endif
+			}
+			else
+			{
+#ifdef VERBOSE_DEBUG_BAG
+				UVcout << "couldn't find any place to remove " << QUACKLE_ALPHABET_PARAMETERS->userVisible(*it) << " from!" << endl;
+#endif
+
+				ret = false;
+			}
+		}
+	}
+
+	return ret;
+}
+
+PlayerList::const_iterator GamePosition::nextPlayer() const
+{
+	PlayerList::const_iterator ret = m_currentPlayer;
+	ret++;
+	if (ret == m_players.end())
+		ret = m_players.begin();
+	return ret;
+}
+
+PlayerList::const_iterator GamePosition::playerWithId(int id, bool &found) const
+{
+	PlayerList::const_iterator it = m_currentPlayer;
+	for (++it; ; ++it)
+	{
+		if (it == m_players.end())
+			it = m_players.begin();
+
+		if ((*it).id() == id)
+		{
+			found = true;
+			return it;
+		}
+
+		if (it == m_currentPlayer)
+		{
+			found = false;
+			return it;
+		}
+	}
+}
+
+PlayerList::const_iterator GamePosition::nextPlayerOfType(Player::PlayerType type, bool &found) const
+{
+	PlayerList::const_iterator ret = m_currentPlayer;
+	++ret;
+	while (true)
+	{
+		if (ret == m_players.end())
+			ret = m_players.begin();
+
+		if ((*ret).type() == type)
+			break;
+
+		if (ret == m_currentPlayer)
+		{
+			found = false;
+			break;
+		}
+
+		++ret;
+	}
+
+	found = true;
+	return ret;
+}
+
+PlayerList GamePosition::endgameAdjustedScores() const
+{
+	PlayerList ret;
+	const PlayerList::const_iterator end(m_players.end());
+	for (PlayerList::const_iterator it = m_players.begin(); it != end; ++it)
+	{
+		Player adjustedPlayer(*it);
+
+		if (gameOver() && adjustedPlayer == currentPlayer())
+		{
+			adjustedPlayer.addToScore(m_moveMade.effectiveScore());
+		}
+
+		ret.push_back(adjustedPlayer);
+	}
+
+	return ret;
+}
+
+PlayerList GamePosition::leadingPlayers() const
+{
+	PlayerList ret;
+
+	PlayerList players(endgameAdjustedScores());
+	for (PlayerList::const_iterator it = players.begin(); it != players.end(); ++it)
+	{
+		if (!ret.empty() && (*it).score() > ret.back().score())
+			ret.clear();
+
+		if (ret.empty() || (*it).score() >= ret.back().score())
+			ret.push_back(*it);
+	}
+
+	return ret;
+}
+
+int GamePosition::spread(int playerID) const
+{
+	int nextBest = 0;
+	int currentPlayerScore = 0;
+
+	PlayerList players(endgameAdjustedScores());
+	for (PlayerList::const_iterator it = players.begin(); it != players.end(); ++it)
+	{
+		if ((*it).id() == playerID)
+		{
+			currentPlayerScore = (*it).score();
+			continue;
+		}
+
+		if ((*it).score() > nextBest)
+			nextBest = (*it).score();
+	}
+
+	return currentPlayerScore - nextBest;
+}
+
+void GamePosition::adjustScoresToFinishPassedOutGame()
+{
+	const PlayerList::iterator end(m_players.end());
+	for (PlayerList::iterator it = m_players.begin(); it != end; ++it)
+	{
+		if ((*it) == currentPlayer())
+		{
+			m_moveMade = Move::createUnusedTilesBonus((*it).rack().tiles(), -(*it).rack().score());
+			m_committedMove = m_moveMade;
+		}
+		else
+		{
+			(*it).addToScore(-(*it).rack().score());
+		}
+	}
+}
+
+void GamePosition::adjustScoresToFinishGame()
+{
+	int addand = 0;
+	LetterString clobberedTiles;
+	
+	addand = deadwood(&clobberedTiles);
+
+	m_moveMade = Move::createUnusedTilesBonus(clobberedTiles, addand);
+	m_committedMove = m_moveMade;
+}
+
+int GamePosition::deadwood(LetterString *tiles) const
+{
+	int addand = 0;
+	tiles->clear();
+
+	const PlayerList::const_iterator end(m_players.end());
+	for (PlayerList::const_iterator it = m_players.begin(); it != end; ++it)
+	{
+		if ((*it) == currentPlayer())
+			continue;
+
+		addand += (*it).rack().score();
+		*tiles += (*it).rack().tiles();
+	}
+
+	return addand * 2;
+}
+
+bool GamePosition::doesMoveEndGame(const Move &move) const
+{
+	return (currentPlayer().rack() - move).empty() && m_bag.empty();
+}
+
+UVOStream& operator<<(UVOStream& o, const Quackle::GamePosition &position)
+{
+	o << "------------" << endl;
+	o << "Position [turnNumber = " << position.turnNumber() << ", current player " << position.currentPlayer() << endl;
+	o << position.board() << endl;
+	o << "Move made is " << position.moveMade() << endl;
+	o << "All Players: " << endl;
+	PlayerList players(position.players());
+	const PlayerList::const_iterator end(players.end());
+	for (PlayerList::const_iterator it = players.begin(); it != end; ++it)
+		o << *it << endl;
+	o << position.bag() << endl;
+	if (position.gameOver())
+		o << "Game over." << endl;
+	o << "------------" << endl;
+    return o;
+}
+
+UVOStream& operator<<(UVOStream& o, const Quackle::PositionList &positions)
+{
+	const Quackle::PositionList::const_iterator end(positions.end());
+	for (Quackle::PositionList::const_iterator it = positions.begin(); it != end; ++it)
+		o << *it << endl;
+	return o;
+}
+
+///////////////
+
+int History::maximumTurnNumber() const
+{
+	if (empty())
+		return 0;
+
+	return back().turnNumber();
+}
+
+PositionList History::positionsFacedBy(int playerID) const
+{
+	PositionList ret;
+	const PositionList::const_iterator ourEnd(end());
+	for (PositionList::const_iterator it = begin(); it != ourEnd; ++it)
+		if ((*it).playerOnTurn().id() == playerID)
+			ret.push_back(*it);
+
+	return ret;
+}
+
+const GamePosition &History::positionAt(const HistoryLocation &location, bool *exists) const
+{
+	for (PositionList::const_reverse_iterator it = rbegin(); it != rend(); ++it)
+	{
+		if ((*it).playerOnTurn().id() == location.playerId() && (*it).turnNumber() == location.turnNumber())
+		{
+			if (exists) *exists = true;
+			return *it;
+		}
+	}
+
+	if (exists) *exists = false;
+	return back();
+}
+
+GamePosition &History::mutablePositionAt(const HistoryLocation &location, bool *exists)
+{
+	for (PositionList::reverse_iterator it = rbegin(); it != rend(); ++it)
+	{
+		if ((*it).playerOnTurn().id() == location.playerId() && (*it).turnNumber() == location.turnNumber())
+		{
+			if (exists) *exists = true;
+			return *it;
+		}
+	}
+
+	if (exists) *exists = false;
+	return back();
+}
+
+const GamePosition &History::nextPosition(bool *exists) const
+{
+	bool found = false;
+	for (PositionList::const_iterator it = begin(); it != end(); ++it)
+	{
+		if (found)
+		{
+			if (exists) *exists = true;
+			return *it;
+		}
+
+		if ((*it).playerOnTurn().id() == m_currentLocation.playerId() && (*it).turnNumber() == m_currentLocation.turnNumber())
+		{
+			found = true;
+		}
+	}
+
+	if (exists) *exists = false;
+	return back();
+}
+
+const GamePosition &History::previousPosition(bool *exists) const
+{
+	bool found = false;
+	for (PositionList::const_reverse_iterator it = rbegin(); it != rend(); ++it)
+	{
+		if (found)
+		{
+			if (exists) *exists = true;
+			return *it;
+		}
+
+		if ((*it).playerOnTurn().id() == m_currentLocation.playerId() && (*it).turnNumber() == m_currentLocation.turnNumber())
+		{
+			found = true;
+		}
+	}
+
+	if (exists) *exists = false;
+	return back();
+}
+
+const GamePosition &History::nextPositionFacedBy(int playerID, bool *exists) const
+{
+	bool found = false;
+	for (PositionList::const_iterator it = begin(); it != end(); ++it)
+	{
+		if (found && (*it).playerOnTurn().id() == playerID)
+		{
+			if (exists) *exists = true;
+			return *it;
+		}
+
+		if ((*it).playerOnTurn().id() == m_currentLocation.playerId() && (*it).turnNumber() == m_currentLocation.turnNumber())
+		{
+			found = true;
+		}
+	}
+
+	if (exists) *exists = false;
+	return back();
+}
+
+const GamePosition &History::firstPosition(bool *exists) const
+{
+	if (empty())
+	{
+		if (exists) *exists = false;
+		return back();
+	}
+
+	if (exists) *exists = true;
+	return front();
+}
+
+void History::eraseAfter(const HistoryLocation &location)
+{
+	while (true)
+	{
+		if (empty())
+			break;
+
+		bool isAfter;
+
+		if (location.turnNumber() == back().turnNumber())
+			isAfter = location.playerId() < back().playerOnTurn().id();
+		else
+			isAfter = location.turnNumber() < back().turnNumber();
+
+		if (isAfter)
+			pop_back();
+		else
+			break;
+	}
+}
+
+////////
+
+HistoryLocation::HistoryLocation(int playerId, int turnNumber)
+	: m_playerId(playerId), m_turnNumber(turnNumber)
+{
+}
+
+bool operator<(const HistoryLocation &hl1, const HistoryLocation &hl2)
+{
+	if (hl1.turnNumber() != hl2.turnNumber())
+		return hl1.turnNumber() < hl2.turnNumber();
+	return hl1.playerId() < hl2.playerId();
+}
+
+bool operator==(const Quackle::HistoryLocation &hl1, const Quackle::HistoryLocation &hl2)
+{
+	return hl1.turnNumber() == hl2.turnNumber() && hl1.playerId() == hl2.playerId();
+}
+
+UVOStream& operator<<(UVOStream& o, const Quackle::HistoryLocation &historyLocation)
+{
+	o << "location turn number " << historyLocation.turnNumber() << ", player id " << historyLocation.playerId();
+	return o;
+}
+