/* * Quackle -- Crossword game artificial intelligence and analysis tool * Copyright (C) 2005-2019 Jason Katz-Brown, John O'Laughlin, and John Fultz. * * 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 3 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, see . */ #ifndef QUACKLE_GAME_H #define QUACKLE_GAME_H #include #include #include "alphabetparameters.h" #include "bag.h" #include "board.h" #include "player.h" #include "playerlist.h" namespace Quackle { class ComputerPlayer; class History; class HistoryLocation { public: HistoryLocation(int playerId, int turnNumber); int playerId() const; int turnNumber() const; private: int m_playerId; int m_turnNumber; }; // comparison based on turn number then player id bool operator<(const Quackle::HistoryLocation &hl1, const Quackle::HistoryLocation &hl2); inline int HistoryLocation::playerId() const { return m_playerId; } inline int HistoryLocation::turnNumber() const { return m_turnNumber; } class GamePosition { public: // Constructs a new position with empty, prepared board // and full, prepared bag // using players playing the game // where the first player of players starts the game (at turn number 1) // after Game::addPosition() is called to get things going. // You *must* call increment() if you do not use Game::addPosition() // because this constructor leaves current player pointing to the end of // the player list, which is invalid. GamePosition(const PlayerList &players); // copy constructor that preserves current-player iterator // and includes copying the move list and moveMade // Natch, preserves board and bag. // MAKE SURE THAT ANY NEW FIELDS YOU ADD // ALSO GET COPIED!!!!!!!!!!!!!!!!!!!!!! GamePosition(const GamePosition &position); // empty constructor to appease value lists // empty prepared board, full prepared bag GamePosition(); // operator= that preserves current-player iterator // and includes copying the move list and moveMade // Natch, preserves board and bag. // MAKE SURE THAT ANY NEW FIELDS YOU ADD // ALSO GET COPIED!!!!!!!!!!!!!!!!!!!!!! const GamePosition &operator=(const GamePosition &position); // kibitz up to nmoves best moves; stored in move list void kibitz(int nmoves = 10); // get what's in the move list const MoveList &moves() const; void setMoves(const MoveList &moves); // kibitz (destroying previous move list) // and return the best move based on static evaluation const Move &staticBestMove(); // erase a move from move list that equals move void removeMove(const Move &move); // erase all moves from move list void removeAllMoves(); // Add move to move list (so list is still ordered). // Does *not* check if the move is already in the move list, // so this could duplicate a move in the list. // Does nothing is move is a nonmove. // Ensures the move's prettiness and sanity of playthru tiles // in the tiles. void addMove(const Move &move); // for each move in list, add it to our list if we don't // already have it void makeSureMoveListContainsMoves(const MoveList &moves); // fill the move list with computerPlayer's moves, or // the current player's computer player's moves void kibitzAs(ComputerPlayer *computerPlayer, int nmoves); // if move does not have a pretty tiles field set, make it void ensureMovePrettiness(Move &move); // If the move's tiles are PANELINg, and the P is played through, // turn the tiles into .ANELINg void ensureMoveTilesDoNotIncludePlayThru(Move &move); // add move to move list and set as move made for this position void addAndSetMoveMade(const Move &move); // ValidMode - okeydokey // TooLateExchange - not enough tiles in the bag for an exchange // InvalidTiles - tiles to play or exchange aren't on rack // InvalidPlace - word does not connect to rest of board // InvalidOpeningPlace - word does not connect to start square // of empty board // UnacceptableWord - word is not in our lexicon // InvalidAction - type of move is not Place, Pass, or Exchange enum MoveValidity { ValidMove = 0x0000, InvalidTiles = 0x0001, TooLateExchange = 0x0002, InvalidPlace = 0x0004, InvalidOpeningPlace = 0x0008, UnacceptableWord = 0x0010, InvalidAction = 0x0020 }; // Returns validity of this move for current player. // MoveValidity flags are OR'ed together into the return int. int validateMove(const Move &move) const; // returns whether the words formed by this move are all acceptable bool formsAcceptableWords(const Move &move) const; MoveList allWordsFormedBy(const Move &move) const; // returns whether the board is empty or tiles of move touch // at least one other square of the board bool isConnected(const Move &move) const; // returns whether the tiles of move are a word in our lexicon bool isAcceptableWord(const LetterString &word) const; // returns true if any exchange is allowed right now bool exchangeAllowed() const; enum OverdrawValidity { ValidOverdraw = 0x0000, InvalidOverdrawNumber = 0x0001, OverdrawnTilesNotUnseen = 0x0002}; // computers letters that should be thrown back if specified letters // are the faceup tiles and returns if these faceup tiles are valid int handleOverdraw(const LetterString &letters, LetterString *throwback) const; // Make move on the board and add score of move // to current player's score. // If the move is an exchange, tosses the exchanged tiles // back in the bag. // If maintainBoard is false, the board can no longer be used // with kibitzing capabilities. void makeMove(const Move &move, bool maintainBoard = true); // Used when modifying the board without going through the motions, // or preparing a freshly-loaded-from-file board for analysis void ensureBoardIsPreparedForAnalysis(); // score specified move and return a move with score field // filled in and equity field guessed at; score of // non-place moves is zero void scoreMove(Move &move); // equity value is a combination of static score, player consideration, // and shared consideration heuristics: (rack is assumed to be // current player's rack if not specified) double calculateEquity(const Move &move); // 1. score of play int calculateScore(const Move &move); // 2. definitionally, rack leave value double calculatePlayerConsideration(const Move &move); // just get me the leave value, please double leaveValue(const LetterString &leave) const; // 3. other considerations like board geometry double calculateSharedConsideration(const Move &move); void setBoard(const Board &board); const Board &board() const; // all tiles not on board or players' // (probably) filled racks const Bag &bag() const; // Set drawing order, starting from back of drawingOrder. // The drawing order is reset to randomness after letters // are drawn when incremented. // This only is meaningful if you don't // manually set racks and make only valid plays. // (Otherwise there may be letters in the drawing order // that are no longer in the bag. Incidentally the drawing // order is also followed if you do set rack.) void setDrawingOrder(const LetterString &drawingOrder); const LetterString &drawingOrder() const; // get tiles unseen to current player Bag unseenBag() const; Bag unseenBagFromPlayerPerspective(const Player &player) const; // this must be called if you call makeMove with a nonvalid-for- // current-player move void ensureProperBag() const; // reset board to be empty and prepared for a new game void setEmptyBoard(); // current player *really* on turn const Player ¤tPlayer() const; Player ¤tPlayer(); // Returns true if currentPlayer was set, false if no player with // this id was found. bool setCurrentPlayer(int playerID); // Fake player on turn. // Of all libquackle classes, only History uses this field. // Player on turn is reset to the current player whenever this // position is incremented. const Player &playerOnTurn() const; Player &playerOnTurn(); // returns true if currentPlayer was set, false if no player with // this id was found bool setPlayerOnTurn(int playerID); // Returns the current player if he or she is human, // or the next human player if one exists, // or the current player if all players are nonhuman. const Player &humanPlayer() const; // returns a pointer to the next player PlayerList::const_iterator nextPlayer() const; // Returns a pointer to the next player of a type. // This starts its search on the player after the current player, // so the current player will only be returned if it is the only player // of the specified type. // If no player of that type exists, the current player is returned // and found is set to false. PlayerList::const_iterator nextPlayerOfType(Player::PlayerType type, bool &found) const; // Returns the player with the abbreviated name specified, or the current player // if not found. PlayerList::const_iterator playerWithAbbreviatedName(const UVString &abbreviatedName, bool &found) const; const PlayerList &players() const; // If in the endgame, returns players with adjusted scores. // Otherwise returns players. PlayerList endgameAdjustedScores() const; // returns the players with the highest score PlayerList leadingPlayers() const; // returns point difference between current player and // highest-scoring other player int spread() const; // as above, but treating playerID as current player int spread(int playerID) const; // returns true when there is a player with an empty rack and the bag // is empty, so in all frames after the frame containing a player // making the final move, gameOver is true bool gameOver() const; // the move made will // be set to the proper UnusedTilesBonus move. // The score of the bonus is *not* added to score of current player, // therefor this method is quite misnamed. void adjustScoresToFinishGame(); // this is a little special: don't subtract score of bonus from // current player, but subtract it from other players; set move made // to a negative UnusedTilesBonus for the current player void adjustScoresToFinishPassedOutGame(); // returns true if the game will be over after committing this move bool doesMoveEndGame(const Move &move) const; // if the game is over or will be after this turn, // returns how many extra points the current player will get, // and which tiles those are int deadwood(LetterString *tiles) const; // replenishes previousRack from bag and sets it as current player's rack void replenishAndSetRack(const Rack &previousRack); void replenishAndSetRack(const Rack &previousRack, Player &player); // set rack of current player. // This isn't simple because we must ensure the bag contains the proper tiles, // if adjustBag is true, by readding to bag tiles were on rack but no longer void setCurrentPlayerRack(const Rack &rack, bool adjustBag = true); // same as above for a given player void setPlayerRack(int playerID, const Rack &rack, bool adjustBag = true); // Set rack of current player's opponent. // This is broken for number of players != 2 and but I don't care much. // This isn't simple because we must ensure the bag contains the proper tiles, // if adjustBag is true, by readding to bag tiles were on rack but no longer void setOppRack(const Rack &rack, bool adjustBag = true); // return opponent's rack (for preendgame win% usage) Rack oppRack(); // if we set player's rack to this, will there be more tiles in // play than before? bool canSetCurrentPlayerRackWithoutBagExpansion(const Rack &rack) const; bool canSetPlayerRackWithoutBagExpansion(int playerID, const Rack &rack) const; // set bag to a full bag of tiles void resetBag(); // set bag to whatever you want void setBag(const Bag &bag); // move made FROM this position, or candidate play being considered void setMoveMade(const Move &move); const Move &moveMade() const; // Move committed from this position. Can be different from the moveMade // for example if the user loads a gcg file then looks at different // possible plays without committing them. void setCommittedMove(const Move &move); const Move &committedMove() const; void setTileBonus(const UVString &player, const LetterString &allegedTiles, int allegedTileBonus); // saves the current candidate as the committedMove. void prepareForCommit(); // returns the board with the moveMade made on it. // Note that this board won't be ready to be fed to a Generator! // It should only be used to have a representation of a board for // example to display. Board boardAfterMoveMade() const; // set move made to the default, a nonmove void resetMoveMade(); // The new position is made by incrementing // the current player.If the current player was the last in the player list, // turnNumber is incremented in the created position and true is returned, // otherwise false is returned. // Player on turn is set to the new current player. // If after incrementing, gameOver() is true, then the current player is // reset to be the player who made the last turn of the game. // If needed, current player at time of call's rack is refilled // from the bag based on move made. // Furthermove, any empty player's rack is refilled (this happens // at start of game.) // If applicable, this player's score is also incremented by score of move // made. bool incrementTurn(const History* history = NULL); // Turn numbers in games start from 1. // A turn number of zero indicates a position that is pregame. int turnNumber() const; // nestedness of this position in a recursive calculation void setNestedness(unsigned int nestedness); void incrementNestedness(); unsigned int nestedness() const; // returns a blank string that is one tab per nestedness UVString nestednessIndentation() const; // number of plays in a row that have been scoreless int scorelessTurnsInARow() const; HistoryLocation location() const; const UVString &explanatoryNote() const; void setExplanatoryNote(const UVString &explanatoryNote); // not recommended to use this! Board &underlyingBoardReference(); protected: PlayerList m_players; PlayerList::iterator m_currentPlayer; PlayerList::iterator m_playerOnTurn; // moves originally from kibitzer MoveList m_moves; // It is very important that these two variables almost always be // modified together, unless one is experimenting with different // candidates before deciding on the move to commit. // For instance, the end-of-game bonus move is stored in both fields. Move m_moveMade; Move m_committedMove; // I feel safer with this not being public void setTurnNumber(int turnNumber); int m_turnNumber; unsigned int m_nestedness; int m_scorelessTurnsInARow; bool m_gameOver; int m_tilesInBag; int m_tilesOnRack; Quackle::Board m_board; // Keeping the bag holding the correct letters is VOUDOU! // If you break its behavior, I will be bemaddened! Quackle::Bag m_bag; LetterString m_drawingOrder; UVString m_explanatoryNote; // Use this instead of m_bag.removeTiles(); if the bag // doesn't contain the tiles to remove, it removes from // non-current player racks if they have tiles and then refills. // Returns false if one of the letters was found nowhere to be // removed from. bool removeLetters(const LetterString &letters); }; inline const Player &GamePosition::currentPlayer() const { return *m_currentPlayer; } inline Player &GamePosition::currentPlayer() { return *m_currentPlayer; } inline const Player &GamePosition::playerOnTurn() const { return *m_playerOnTurn; } inline Player &GamePosition::playerOnTurn() { return *m_playerOnTurn; } inline const MoveList &GamePosition::moves() const { return m_moves; } inline void GamePosition::setMoves(const MoveList &moves) { m_moves = moves; } inline void GamePosition::setBoard(const Board &board) { m_board = board; } inline const Board &GamePosition::board() const { return m_board; } inline Board &GamePosition::underlyingBoardReference() { return m_board; } inline const Bag &GamePosition::bag() const { return m_bag; } inline void GamePosition::setBag(const Bag &bag) { m_bag = bag; } inline void GamePosition::setDrawingOrder(const LetterString &drawingOrder) { m_drawingOrder = drawingOrder; } inline const LetterString &GamePosition::drawingOrder() const { return m_drawingOrder; } inline const PlayerList &GamePosition::players() const { return m_players; } inline int GamePosition::spread() const { return spread(currentPlayer().id()); } inline void GamePosition::replenishAndSetRack(const Rack &previousRack) { replenishAndSetRack(previousRack, currentPlayer()); } inline bool GamePosition::gameOver() const { return m_gameOver; } inline void GamePosition::setMoveMade(const Move &move) { m_moveMade = move; if (m_gameOver && move.action != Quackle::Move::UnusedTilesBonus && move.action != Quackle::Move::UnusedTilesBonusError) { m_gameOver = false; // apparently the game isn't over...somebody's force-feeding us bad plays --m_turnNumber; m_moveMade.action = Quackle::Move::PlaceError; m_explanatoryNote = "Quackle says: Tiles were drawn out of order, leading to extra turns"; if (++m_currentPlayer == m_players.end()) { m_currentPlayer = m_players.begin(); } } } inline const Move &GamePosition::moveMade() const { return m_moveMade; } inline void GamePosition::setCommittedMove(const Move &move) { m_committedMove = move; } inline const Move &GamePosition::committedMove() const { return m_committedMove; } inline void GamePosition::setTurnNumber(int turnNumber) { m_turnNumber = turnNumber; } inline void GamePosition::setNestedness(unsigned int nestedness) { m_nestedness = nestedness; } inline void GamePosition::incrementNestedness() { ++m_nestedness; } inline int GamePosition::scorelessTurnsInARow() const { return m_scorelessTurnsInARow; } inline HistoryLocation GamePosition::location() const { return HistoryLocation(currentPlayer().id(), turnNumber()); } inline int GamePosition::turnNumber() const { return m_turnNumber; } inline unsigned int GamePosition::nestedness() const { return m_nestedness; } inline const UVString &GamePosition::explanatoryNote() const { return m_explanatoryNote; } inline void GamePosition::setExplanatoryNote(const UVString &explanatoryNote) { m_explanatoryNote = explanatoryNote; } // simple modifiable list of positions typedef vector PositionList; class Game; // unmodifiable list of positions in a game class History : public PositionList { public: History() : /* a position in the past */ m_currentLocation(0, -1) { } const PlayerList &players() const; const Player &lastPlayer() const; const GamePosition &lastPosition() const; // returns number of levels of turns so far in this game // If this contains no positions, returns 0. // Remember turns are numbered starting at 1. int maximumTurnNumber() const; // location at [maximumTurnNumber(), lastPlayer().id()] HistoryLocation lastLocation() const; // current location and position -- usually the last one unless // it's been manually set with Game::setCurrentLocation. HistoryLocation currentLocation() const; const GamePosition ¤tPosition() const; GamePosition ¤tPosition(); // all positions this player has been in PositionList positionsFacedBy(int playerID) const; // the next position after the current position const GamePosition &nextPosition(bool *exists = 0) const; // the next item of positionsFacedBy(playerID) const GamePosition &nextPositionFacedBy(int playerID, bool *exists = 0) const; // the previous position before the current position const GamePosition &previousPosition(bool *exists = 0) const; // the first position in the game const GamePosition &firstPosition(bool *exists = 0) const; const GamePosition &positionAt(const HistoryLocation &location, bool *exists = 0) const; private: PlayerList m_players; void setPlayers(const PlayerList &list); HistoryLocation m_currentLocation; void setCurrentLocation(const HistoryLocation &location); // erase all positions that are after location gamewise void eraseAfter(const HistoryLocation &location); GamePosition &mutablePositionAt(const HistoryLocation &location, bool *exists = 0); GamePosition &lastPosition(); friend class Game; }; inline void History::setPlayers(const PlayerList &list) { m_players = list; } inline const PlayerList &History::players() const { return m_players; } inline const Player &History::lastPlayer() const { return back().playerOnTurn(); } inline const GamePosition &History::lastPosition() const { return back(); } inline GamePosition &History::lastPosition() { return back(); } inline HistoryLocation History::lastLocation() const { return lastPosition().location(); } inline HistoryLocation History::currentLocation() const { return m_currentLocation; } inline const GamePosition &History::currentPosition() const { return positionAt(currentLocation()); } inline GamePosition &History::currentPosition() { return mutablePositionAt(currentLocation()); } inline void History::setCurrentLocation(const HistoryLocation &location) { m_currentLocation = location; } class Game { public: Game(); ~Game(); // return to like-new board and empty player list. // Use to make new game. See setPlayers() and addPosition(); // both should each be called at least once manually // (with setPlayers() coming before addPosition()) void reset(); // game starts with first player of list. // This method sets the ids of the players to // numbers in ascending order, starting at 0. // Because the player IDs cannot be later changed, // this is a representation invariant. void setPlayers(const PlayerList &list); const PlayerList &players() const; // returns whether or not addPosition has been called after a // reset or being newly constructed bool hasPositions() const; // history of all positions encountered this game, including // the current position const History &history() const; // This should be called after players() to get the first player // started off with his or her first rack and the game underway. // // implementation details: // Create a new GamePosition that is a copy of the current position // and add it to the end of our positions list, making it the // current position. // The first position added after a reset() is the first player // going first to start the game. // In other cases, the new current position is the // GamePosition::incrementTurn() of the older position, // with racks replenished from suitable bag void addPosition(); // don't call without having called addPosition! const GamePosition ¤tPosition() const; GamePosition ¤tPosition(); // moves our current location pointer void setCurrentPosition(const HistoryLocation &location); // set current position to position and point current // position to this position (strange that this must // be explicit, but it must be) void setCurrentPosition(const GamePosition &position); // Sets the computer player that will play for player with // given playerId. Game does not take control of deleting this pointer. void associateComputerPlayer(int playerId, ComputerPlayer *computerPlayer); // returns the computer player associated with given playerId ComputerPlayer *computerPlayer(int playerId); // sets the computer player that will play for players for whom // a computer player has not been associated void setDefaultComputerPlayer(ComputerPlayer *computerPlayer); // associates computer players for players with known ComputerPlayer // type void associateKnownComputerPlayers(); ComputerPlayer *defaultComputerPlayer(); // Have quackle commit a move for the current player // using the specified computerPlayer, or, if computerPlayer is 0, // use the associated computer player, // or a default computer player if none has been associated. // Returns the move that is played. // Does nothing if the game is over. Move haveComputerPlay(ComputerPlayer *computerPlayer = 0); // haveComputerPlay() until the current player type is not // ComputerPlayer or the game is over void advanceToNoncomputerPlayer(); // the candidate play is stored in currentPosition().moveMade() // and defaults to a nonmove. // // put candidate on platform, the current position void setCandidate(const Move &move); const Move &candidate() const; // reset candidate to a nonmove void resetCandidature(); // Copy current candidate play as the moveMade in the current position // then addPosition and set up the new position with the play on the board. // Also makes sure the bag is full of only kosher letters afterward. // maintainBoard must be true if you want to keep using this game. // If the game is over, does nothing. void commitCandidate(bool maintainBoard = true); // convience to set move as candidate and then commit the candidate void commitMove(const Move &move); const UVString &description() const; void setDescription(const UVString &description); const UVString &title() const; void setTitle(const UVString &title); protected: History m_positions; typedef map ComputerPlayerMap; ComputerPlayer *m_defaultComputerPlayer; ComputerPlayerMap m_computerPlayers; UVString m_title; UVString m_description; // create a new GamePosition that is a copy of the current position // without incrementing. Adds it after the current position and // erases all later positions. void addClonePosition(); }; inline const PlayerList &Game::players() const { return m_positions.players(); } inline bool Game::hasPositions() const { return !m_positions.empty(); } inline const History &Game::history() const { return m_positions; } inline void Game::setCandidate(const Move &move) { currentPosition().setMoveMade(move); } inline const Move &Game::candidate() const { return currentPosition().moveMade(); } inline void Game::resetCandidature() { currentPosition().resetMoveMade(); } inline const GamePosition &Game::currentPosition() const { return m_positions.currentPosition(); } inline GamePosition &Game::currentPosition() { return m_positions.currentPosition(); } inline void Game::setCurrentPosition(const HistoryLocation &location) { m_positions.setCurrentLocation(location); } inline const UVString &Game::description() const { return m_description; } inline void Game::setDescription(const UVString &description) { m_description = description; } inline const UVString &Game::title() const { return m_title; } inline void Game::setTitle(const UVString &title) { m_title = title; } } bool operator==(const Quackle::HistoryLocation &hl1, const Quackle::HistoryLocation &hl2); UVOStream& operator<<(UVOStream& o, const Quackle::GamePosition &position); UVOStream& operator<<(UVOStream& o, const Quackle::PositionList &positions); UVOStream& operator<<(UVOStream& o, const Quackle::HistoryLocation &historyLocation); #endif