From 9306cb60c32082c5403931de0823a9fd5daa196c Mon Sep 17 00:00:00 2001 From: Jason Katz-Brown Date: Sun, 25 Aug 2013 02:17:13 -0700 Subject: Initial git commit. --- generator.cpp | 1883 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1883 insertions(+) create mode 100644 generator.cpp (limited to 'generator.cpp') diff --git a/generator.cpp b/generator.cpp new file mode 100644 index 0000000..b2d5acd --- /dev/null +++ b/generator.cpp @@ -0,0 +1,1883 @@ +/* + * 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 +#include +#include + +#include "datamanager.h" +#include "evaluator.h" +#include "generator.h" +#include "gaddag.h" +#include "board.h" +#include "boardparameters.h" +#include "gameparameters.h" +#include "lexiconparameters.h" + +// #define DEBUG_GENERATOR + +using namespace std; +using namespace Quackle; + +Generator::Generator() +{ +} + +Generator::Generator(const GamePosition &position) + : m_position(position) +{ +} + +Generator::~Generator() +{ +} + +void Generator::kibitz(int kibitzLength, int flags) +{ + // don't just record best move, unless kibitz length is one + setrecordall(kibitzLength > 1); + + // perform actual kibitz + findstaticbest(!(flags & CannotExchange)); + + m_kibitzList.clear(); + + if (kibitzLength <= 1) + { + m_kibitzList.push_back(best); + return; + } + + filterOutDuplicatePlays(); + + MoveList::sort(m_moveList, MoveList::Equity); + + int i = 0; + MoveList::iterator end(m_moveList.end()); + for (MoveList::iterator it = m_moveList.begin(); it != end; ++it, ++i) + { + if (i >= kibitzLength) + break; + + m_kibitzList.push_back(*it); + } +} + +void Generator::filterOutDuplicatePlays() +{ + map oneTilePlayMap; + for (MoveList::iterator it = m_moveList.begin(); it != m_moveList.end();) + { + LetterString usedTiles = (*it).usedTiles(); + if (usedTiles.size() == 1) + { + const LetterString &tiles = (*it).tiles(); + int actualTileIndex = 0; + for (LetterString::const_iterator letterIt = tiles.begin(); letterIt != tiles.end(); ++letterIt, ++actualTileIndex) + if ((*letterIt) != QUACKLE_PLAYED_THRU_MARK) + break; + + const int row = (*it).startrow + ((*it).horizontal? 0 : actualTileIndex); + const int column = (*it).startcol + ((*it).horizontal? actualTileIndex : 0); + int key = row + QUACKLE_MAXIMUM_BOARD_SIZE * column + (QUACKLE_MAXIMUM_BOARD_SIZE * QUACKLE_MAXIMUM_BOARD_SIZE) * String::front(usedTiles); + + if (oneTilePlayMap.find(key) == oneTilePlayMap.end()) + { + oneTilePlayMap[key] = true; + ++it; + } + else + { + it = m_moveList.erase(it); + } + } + else + { + ++it; + } + } +} + +void Generator::allCrosses() +{ + vector vrows, vcols, hrows, hcols; + + for (int i = 0; i < board().height(); i++) { + for (int j = 0; j < board().width(); j++) { + vrows.push_back(i); + vcols.push_back(j); + hrows.push_back(i); + hcols.push_back(j); + } + } + + // check the appropriate crosses + for (unsigned int i = 0; i < vrows.size(); i++) { + int row = vrows[i]; + int col = vcols[i]; + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + board().setVCross(row, col, 0); + } + else { + LetterString pre; + if (row > 0) { + for (int i = row - 1; i >= 0; i--) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { + i = -1; + } + else { + LetterString newpre; + newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); + newpre += pre; + pre = newpre; + } + } + } + + LetterString suf; + if (row < board().height() - 1) { + for (int i = row + 1; i < board().height(); i++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { + i = board().height(); + } + else { + suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); + } + } + } + +#ifdef DEBUG_GENERATOR + UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << " / " << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; +#endif + + if (pre.empty() && suf.empty()) { + board().setVCross(row, col, Utility::Max); + } + else { + board().setVCross(row, col, fitbetween(pre, suf)); + } + +#ifdef DEBUG_GENERATOR + UVcout << "board().vcross[" << row << "][" << col << "] = " << cross2string(board().vcross(row, col)) << endl; +#endif + } + } + + for (unsigned int i = 0; i < hrows.size(); i++) { + int row = hrows[i]; + int col = hcols[i]; + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + board().setHCross(row, col, 0); + } + else { + LetterString pre; + if (col > 0) { + for (int i = col - 1; i >= 0; i--) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { + i = -1; + } + else { + LetterString newpre; + newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); + newpre += pre; + pre = newpre; + } + } + } + + LetterString suf; + if (col < board().width() - 1) { + for (int i = col + 1; i < board().width(); i++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { + i = board().width(); + } + else { + suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); + } + } + } + if (pre.empty() && suf.empty()) { + board().setHCross(row, col, Utility::Max); + } + else { + board().setHCross(row, col, fitbetween(pre, suf)); + } + +#ifdef DEBUG_GENERATOR + UVcout << "board().hcross[" << row << "][" << col << "] = " << cross2string(board().hcross(row, col)) << endl; +#endif + } + } +} + +void Generator::makeMove(const Move &move, bool regenerateCrosses) +{ + if (move.action != Move::Place) + return; + + if (!regenerateCrosses) + { + board().makeMove(move); + return; + } + + // mark which squares need their crosses checked + vector hrows; + vector hcols; + vector vrows; + vector vcols; + hrows.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); + hcols.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); + vrows.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); + vcols.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); + + if (move.horizontal) { + int row = move.startrow; + int endcol = move.startcol + move.tiles().length() - 1; + + if (move.startcol > 0) { + hrows.push_back(row); + hcols.push_back(move.startcol - 1); + } + + if (endcol < board().width() - 1) { + hrows.push_back(row); + hcols.push_back(endcol + 1); + } + + for (int col = move.startcol; col <= endcol; col++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + int upempty = -1; + for (int hookrow = row - 1; hookrow >= 0; hookrow--) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(hookrow, col))) { + upempty = hookrow; + hookrow = -1; + } + } + if (upempty >= 0) { + vrows.push_back(upempty); + vcols.push_back(col); + } + + int downempty = board().height(); + for (int hookrow = row + 1; hookrow < board().height(); hookrow++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(hookrow, col))) { + downempty = hookrow; + hookrow = board().height(); + } + } + if (downempty < board().height()) { + vrows.push_back(downempty); + vcols.push_back(col); + } + } + } + } + else { + int col = move.startcol; + int endrow = move.startrow + move.tiles().length() - 1; + + if (move.startrow > 0) { + vrows.push_back(move.startrow - 1); + vcols.push_back(col); + } + + if (endrow < board().height() - 1) { + vrows.push_back(endrow + 1); + vcols.push_back(col); + } + + for (int row = move.startrow; row <= endrow; row++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + int upempty = -1; + for (int hookcol = col - 1; hookcol >= 0; hookcol--) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, hookcol))) { + upempty = hookcol; + hookcol = -1; + } + } + if (upempty >= 0) { + hrows.push_back(row); + hcols.push_back(upempty); + } + + int downempty = board().width(); + for (int hookcol = col + 1; hookcol < board().width(); hookcol++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, hookcol))) { + downempty = hookcol; + hookcol = board().width(); + } + } + if (downempty < board().width()) { + hrows.push_back(row); + hcols.push_back(downempty); + } + } + } + } + + board().makeMove(move); + + // check the appropriate crosses + for (unsigned int i = 0; i < vrows.size(); i++) { + int row = vrows[i]; + int col = vcols[i]; + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + board().setVCross(row, col, 0); + } + else { + LetterString pre; + if (row > 0) { + for (int i = row - 1; i >= 0; i--) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { + i = -1; + } + else { + LetterString newpre; + newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); + newpre += pre; + pre = newpre; + } + } + } + LetterString suf; + if (row < board().height() - 1) { + for (int i = row + 1; i < board().height(); i++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { + i = board().height(); + } + else { + suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); + } + } + } + +#ifdef DEBUG_GENERATOR + UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << " / " << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; +#endif + + if ((pre.empty()) && (suf.empty())) { + board().setVCross(row, col, Utility::Max); + } + else { + board().setVCross(row, col, fitbetween(pre, suf)); + } + +#ifdef DEBUG_GENERATOR + UVcout << "board().vcross[" << row << "][" << col << "] = " << cross2string(board().vcross(row, col)) << endl; +#endif + } + } + + for (unsigned int i = 0; i < hrows.size(); i++) { + int row = hrows[i]; + int col = hcols[i]; + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + board().setHCross(row, col, 0); + } + else { + LetterString pre; + if (col > 0) { + for (int i = col - 1; i >= 0; i--) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { + i = -1; + } + else { + LetterString newpre; + newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); + newpre += pre; + pre = newpre; + } + } + } + LetterString suf; + if (col < board().width() - 1) { + for (int i = col + 1; i < board().width(); i++) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { + i = board().width(); + } + else { + suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); + } + } + } + +#ifdef DEBUG_GENERATOR + UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << " / " << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; +#endif + + if ((pre.empty()) && (suf.empty())) { + board().setHCross(row, col, Utility::Max); + } + else { + board().setHCross(row, col, fitbetween(pre, suf)); + } + +#ifdef DEBUG_GENERATOR + UVcout << "board().hcross[" << row << "][" << col << "] = " << cross2string(board().hcross(row, col)) << endl; +#endif + } + } +} + +void Generator::readFromDawg(int index, unsigned int &p, Letter &letter, bool &t, bool &lastchild, bool &british, int &playability) const +{ + index *= 7; + p = (QUACKLE_LEXICON_PARAMETERS->dawgAt(index) << 16) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 1) << 8) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 2)); + letter = QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 3); + + t = (letter & 32); + lastchild = (letter & 64); + british = !(letter & 128); + letter = (letter & 31) + QUACKLE_FIRST_LETTER; + + playability = (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 4) << 16) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 5) << 8) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 6)); +} + +bool Generator::checksuffix(int i, const LetterString &suffix) { + unsigned int p; + Letter c; + bool t; + bool lastchild; + bool british; + int playability; + + readFromDawg(i, p, c, t, lastchild, british, playability); + + Letter sc = suffix[0]; + +//#ifdef DEBUG_BOARD + //UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(suffix) << " i: " << i << ", p: " << p << ", c: " << QUACKLE_ALPHABET_PARAMETERS->userVisible(c) << ", sc: " << QUACKLE_ALPHABET_PARAMETERS->userVisible(sc) << endl; +//#endif + + if (c == sc) { + if (suffix.length() == 1) { + return t; + } + else { + if (p != 0) { + return checksuffix(p, String::allButFront(suffix)); + } + else { + return false; + } + } + } + else if (true) { + //else if (c < sc) { + if (lastchild) { + return false; + } + else { + return checksuffix(i + 1, suffix); + } + } + else { + return false; + } +} + +int Generator::gaddagFitbetween(const LetterString &pre, const LetterString &suf) +{ +// UVcout << "fit " +// << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) +// << "_" +// << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; + int crosses = 0; + /* process the suffix once */ + const GaddagNode *sufNode = QUACKLE_LEXICON_PARAMETERS->gaddagRoot(); + int sufLen = suf.length(); + for (int i = sufLen - 1; i >= 0; --i) { + sufNode = sufNode->child(suf[i]); + if (!sufNode) { // this can only happen if an illegal word is on the board + return crosses; + } + } + + int preLen = pre.length(); + for (const GaddagNode* node = sufNode->firstChild(); node; node = node->nextSibling()) { + Letter childLetter = node->letter(); + if (childLetter == QUACKLE_GADDAG_SEPARATOR) { + break; + } + const GaddagNode *n = node; + for (int i = preLen - 1; i >= 0; --i) { + n = n->child(pre[i]); + if (!n) { + break; + } + } + + if (n && n->isTerminal()) { + crosses |= Utility::Bits[(int)(childLetter - QUACKLE_FIRST_LETTER)]; + } + } + return crosses; +} + +int Generator::fitbetween(const LetterString &pre, const LetterString &suf) +{ + if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) { + return gaddagFitbetween(pre, suf); + } + + //UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << "_" << + // QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; + + int crosses = 0; + + for (Letter c = QUACKLE_FIRST_LETTER; c <= QUACKLE_ALPHABET_PARAMETERS->lastLetter(); c++) { +/* + UVcout << "Let's check " << + QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << + QUACKLE_ALPHABET_PARAMETERS->userVisible(c) << + QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; +*/ + if (checksuffix(1, pre + c + suf)) { + // subtract first letter because crosses hold values starting from zero + crosses |= Utility::Bits[c - QUACKLE_FIRST_LETTER]; + //UVcout << " that's a word" << endl; + // UVcout << c; + } + } + + //UVcout << " crosses: " << crosses << " " << cross2string(crosses) << endl; + return crosses; +} + +UVString Generator::counts2string() +{ + UVString ret; + + for (Letter i = 0; i < QUACKLE_ALPHABET_PARAMETERS->lastLetter(); i++) + for (int j = 0; j < m_counts[i]; j++) + ret += QUACKLE_ALPHABET_PARAMETERS->userVisible(i); + + return ret; +} + +UVString Generator::cross2string(int cross) +{ + UVString ret; + + for (int i = 0; i < QUACKLE_ALPHABET_PARAMETERS->length(); i++) + if (cross & Utility::Bits[i]) + ret += QUACKLE_ALPHABET_PARAMETERS->userVisible(QUACKLE_FIRST_LETTER + i); + + return ret; +} + +/* + Gen(pos, word, rack, arc): pos = offset from anchor + IF a letter, L, is already on this square THEN + GoOn(pos, L, word, rack, NextArc(arc, L), arc) + ELSE IF letters remain on the rack THEN + FOR each letter on the rack, L, allowed on this square + GoOn(pos, L, word, rack - L, NextArc(arc, L), arc) + IF the rack contains a BLANK THEN + FOR each letter the BLANK could be, L, allowed... + GoOn(pos, L, word, rack - BLANK, NextArc(arc, L), arc) + + GoOn(pos, L, word, rack, NewArc, OldArc): + IF pos <= 0 THEN // moving left + word <- L + word + IF L on OldArc & no letter directly left THEN Record + IF NewArc != 0 THEN + IF room to the left THEN Gen(pos - 1, word, rack, NewArc) + NewArc <- NextArc(NewArc, ^) + IF NewArc != 0, no letter directly left & room to the right THEN + Gen(1, word, rack, NewArc) + ELSE IF pos > 0 THEN // moving right + word <- word + L + IF L on OldArc & no letter directly right THEN Record + IF NewArc != & room to the right THEN + Gen(pos + 1, word, rack, NewArc) + */ + +void Generator::gordongoon(int pos, char L, LetterString word, const GaddagNode *node) +{ + //UVcout << "gordongoon(" << pos << ", " << L << ", " << word << ", " << newarc << ", " << oldarc << ")" << + // " horiz: " << m_gordonhoriz << endl; + + if (pos <= 0) { + + int currow = m_anchorrow; + int curcol = m_anchorcol; + + int leftrow = m_anchorrow; + int leftcol = m_anchorcol; + + if (m_gordonhoriz) { + curcol += pos; + leftcol += pos - 1; + } + else { + currow += pos; + leftrow += pos - 1; + } + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol))) { + L = QUACKLE_PLAYED_THRU_MARK; + } + + LetterString newWord; + newWord += L; + newWord += word; + + bool emptyleft = true; + bool roomtoleft = true; + bool atboardedge = false; + + if ((leftcol >= 0) && (leftrow >= 0)) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol)) && QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(leftrow, leftcol))) { + roomtoleft = false; + } + + if (pos < -m_leftlimit) { + roomtoleft = false; + } + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(leftrow, leftcol))) { + emptyleft = false; + } + } + else { + atboardedge = true; + } + + if (node->isTerminal() && (roomtoleft) && (m_laid > 0)) { + // UVcout << "found a word or something " << word << " at " << pos << endl; + Move move; + move.action = Move::Place; + move.setTiles(newWord); + if (m_gordonhoriz) { + move.startrow = m_anchorrow; + move.startcol = m_anchorcol + pos; + } + else { + move.startrow = m_anchorrow + pos; + move.startcol = m_anchorcol; + } + + move.horizontal = m_gordonhoriz; + move.score = board().score(move, &move.isBingo); + move.equity = equity(move); + + if (m_recordall) { + m_moveList.push_back(move); + } + + if (MoveList::equityComparator(best, move)) { + best = move; + } + // UVcout << "found a move: " << move << " score: " << move.score << ", equity: " << move.equity << + // " outputted by leftmoving loop" << endl; + } + + if (roomtoleft && pos != -m_leftlimit && !atboardedge) { + gordongen(pos - 1, newWord, node); + } + + // UVcout << "looking for the delimiter" << endl; + + node = node->child(QUACKLE_GADDAG_SEPARATOR); + + // UVcout << "after all that, delimiter's newarc is " << newarc << endl; + int rightrow = m_anchorrow; + int rightcol = m_anchorcol; + + if (m_gordonhoriz) { + rightcol++; + } + else { + rightrow++; + } + + bool atrightedge = false; + + if ((rightrow > board().height() - 1) || (rightcol > board().width() - 1)) { + atrightedge = true; + } + + if ((node != 0) && emptyleft && !atrightedge) { + gordongen(1, newWord, node); + } + } + else { + // UVcout << "looking to the right" << endl; + + int currow = m_anchorrow; + int curcol = m_anchorcol; + int rightrow = m_anchorrow; + int rightcol = m_anchorcol; + + if (m_gordonhoriz) { + curcol += pos; + rightcol += pos + 1; + } + else { + currow += pos; + rightrow += pos + 1; + } + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol))) { + word += QUACKLE_PLAYED_THRU_MARK; + } + else { + word += L; + } + + bool roomtoright = true; + bool atboardedge = false; + + // UVcout << "rightsquare: " << (char)(rightcol + 'A') << rightrow + 1 << endl; + + if ((rightcol <= board().width() - 1) && (rightrow <= board().height() - 1)) { + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rightrow, rightcol))) { + roomtoright = false; + // UVcout << "can't record " << word << " here because of the " << board().letter(rightrow, rightcol) << endl; + } + else { + // UVcout << "yay! " << (char)(rightcol + 'A') << rightrow + 1 << " is empty!" << endl; + // UVcout << board() << endl; + } + } + else { + // UVcout << "at board edge so i can maybe record " << word << endl; + atboardedge = true; + } + + if (node->isTerminal() && (roomtoright) && (m_laid > 0)) { + // UVcout << "found a word or something " << word << " at " << pos << endl; + + Move move; + move.action = Move::Place; + move.setTiles(word); + + if (m_gordonhoriz) { + move.startrow = m_anchorrow; + move.startcol = m_anchorcol - word.length() + pos + 1; + } + else { + move.startrow = m_anchorrow - word.length() + pos + 1; + move.startcol = m_anchorcol; + } + + move.horizontal = m_gordonhoriz; + move.score = board().score(move, &move.isBingo); + move.equity = equity(move); + + if (m_recordall) { + m_moveList.push_back(move); + } + + if (MoveList::equityComparator(best, move)) { + best = move; + } + // UVcout << "found a move: " << move << " score: " << move.score << ", equity: " << move.equity << + // " outputted by rightmoving loop" << endl; + } + + // UVcout << "newarc is " << newarc << endl; + if (!atboardedge) { + gordongen(pos + 1, word, node); + } + else { + // UVcout << "didn't go ahead because we were at board edge" << endl; + } + } +} + +void Generator::gordongen(int pos, const LetterString &word, const GaddagNode *node) +{ + // UVcout << "gordongen(" << pos << ", " << word << ", " << i << ")" << " horiz: " << m_gordonhoriz << endl; + + int currow = m_anchorrow; + int curcol = m_anchorcol; + + if (m_gordonhoriz) { + curcol += pos; + } + else { + currow += pos; + } + + int cross; + if (m_gordonhoriz) { + cross = board().vcross(currow, curcol); + } + else { + cross = board().hcross(currow, curcol); + } + + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol))) { + // UVcout << "gordongen sez a letter (" << board().letter(currow, curcol) << ") already on this square" << endl; + + Letter boardc = QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(currow, curcol)); + + const GaddagNode *child = node->child(boardc); + if (child) { + gordongoon(pos, board().letter(currow, curcol), word, child); + } + } + + else { + for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { + Letter childLetter = child->letter(); + + if ((m_counts[childLetter] <= 0) + || !(cross & Utility::Bits[(int)(childLetter - QUACKLE_FIRST_LETTER)])) { + continue; + } + + if (childLetter == QUACKLE_GADDAG_SEPARATOR) { + // UVcout << "ran into a delimiter" << endl; + break; + } + + m_counts[childLetter]--; + m_laid++; + // UVcout << " yeah that'll work" << endl; + gordongoon(pos, childLetter, word, child); + m_counts[childLetter]++; + m_laid--; + + } + if (m_counts[QUACKLE_BLANK_MARK] >= 1) { + for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { + Letter childLetter = child->letter(); + // UVcout << "childLetter is " << (char)(arcc + 'A') << endl; + + if (childLetter == QUACKLE_GADDAG_SEPARATOR) { + // UVcout << "ran into a delimiter" << endl; + break; + } + + if (cross & Utility::Bits[(int)(childLetter - QUACKLE_FIRST_LETTER)]) { + m_counts[QUACKLE_BLANK_MARK]--; + m_laid++; + // UVcout << " yeah that'll work" << endl; + gordongoon(pos, QUACKLE_ALPHABET_PARAMETERS->setBlankness(childLetter), word, child); + m_counts[QUACKLE_BLANK_MARK]++; + m_laid--; + } + } + } + } +} + +void Generator::extendright(const LetterString &partial, int i, + int row, int col, int edge, int righttiles, bool horizontal) +{ + if (i == 0) { // is this really correct? + return; + } + + unsigned int p; + Letter c; + bool t; + bool lastchild; + bool british; + int playability; + + readFromDawg(i, p, c, t, lastchild, british, playability); + + int rowpos = row; + int rownext = row; + int colpos = col; + int colnext = col; + int dirpos; + int edgeDirpos; + + if (horizontal) { + colpos = col + righttiles; + colnext = col + righttiles + 1; + dirpos = colpos; + edgeDirpos = board().width() - 1; + } + else { + rowpos = row + righttiles; + rownext = row + righttiles + 1; + dirpos = rowpos; + edgeDirpos = board().height() - 1; + } + +#ifdef DEBUG_GENERATOR + UVcout << "extendright(" << QUACKLE_ALPHABET_PARAMETERS->userVisible(partial) << ", " << i << ", " << counts2string() << ", " << rowpos << ", " << colpos << ", " << horizontal << ")" << endl; +#endif + + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rowpos, colpos))) { + if (m_counts[c] >= 1) { + int cross; + if (horizontal) { + cross = board().vcross(rowpos, colpos); + } + else { + cross = board().hcross(rowpos, colpos); + } + if (cross & Utility::Bits[(int)(c - QUACKLE_FIRST_LETTER)]) { + if (t) { + bool couldend = true; + if (dirpos < edgeDirpos) { + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rownext, colnext))) { + couldend = false; + } + } + if (couldend) { + Move move; + move.action = Move::Place; + move.setTiles(partial + c); + if (horizontal) { + move.startrow = row; + move.startcol = col - (partial.length() - righttiles); + } + else { + move.startrow = row - (partial.length() - righttiles); + move.startcol = col; + } + move.horizontal = horizontal; + move.score = board().score(move, &move.isBingo); + move.equity = equity(move); + + // i added this because m_laid is wrong and i don't want to break anything by fixing it :) + // will need to remember to add this bit to the DAGGAD code when we start using it again + + int laid = move.wordTilesWithNoPlayThru().length(); + bool onetilevert = (!move.horizontal) && (laid == 1); + bool ignore = onetilevert && (board().hcross(row, col) != Utility::Max); + + if (1 || !ignore) + { + if (m_recordall) { + m_moveList.push_back(move); + } + + if (MoveList::equityComparator(best, move)) { + best = move; + } + +#ifdef DEBUG_GENERATOR + UVcout << "found a move: " << move << " laid: " << m_laid << ", score: " << move.score << ", equity: " << move.equity << endl; +#endif + } + } + } + if (dirpos < edgeDirpos) { + m_counts[c]--; + m_laid++; + extendright(partial + c, p, row, col, + 0, righttiles + 1, horizontal); + m_counts[c]++; + m_laid--; + } + } + } + if ((m_counts[QUACKLE_BLANK_MARK] >= 1)) { + int cross; + if (horizontal) { + cross = board().vcross(rowpos, colpos); + } + else { + cross = board().hcross(rowpos, colpos); + } + if (cross & Utility::Bits[(int)(c - QUACKLE_FIRST_LETTER)]) { + if (t) { + bool couldend = true; + if (dirpos < edgeDirpos) { + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rownext, colnext))) { + couldend = false; + } + } + if (couldend) { + Move move; + move.action = Move::Place; + move.setTiles(partial + QUACKLE_ALPHABET_PARAMETERS->setBlankness(c)); + if (horizontal) { + move.startrow = row; + move.startcol = col - (partial.length() - righttiles); + } + else { + move.startrow = row - (partial.length() - righttiles); + move.startcol = col; + } + move.horizontal = horizontal; + move.score = board().score(move, &move.isBingo); + move.equity = equity(move); + + int laid = move.wordTilesWithNoPlayThru().length(); + bool onetilevert = (!move.horizontal) && (laid == 1); + bool ignore = onetilevert && (board().hcross(row, col) != Utility::Max); + + if (1 || !ignore) + { + if (m_recordall) { + m_moveList.push_back(move); + } + + if (MoveList::equityComparator(best, move)) { + best = move; + } +#ifdef DEBUG_GENERATOR + UVcout << "found a move: " << move << " laid: " << m_laid << ", score: " << move.score << ", equity: " << move.equity << endl; + +#endif + } + } + } + if (dirpos < edgeDirpos) { + m_counts[QUACKLE_BLANK_MARK]--; + m_laid++; + extendright(partial + QUACKLE_ALPHABET_PARAMETERS->setBlankness(c), p, row, col, + 0, righttiles + 1, horizontal); + m_counts[QUACKLE_BLANK_MARK]++; + m_laid--; + } + } + } + + if (!lastchild) { + extendright(partial, i + 1, row, col, edge + 1, righttiles, horizontal); + } + } + else { + Letter boardc = QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(rowpos, colpos)); + + if (c == boardc) + { +#ifdef DEBUG_GENERATOR + UVcout << "We're playing with " << QUACKLE_ALPHABET_PARAMETERS->userVisible(partial) << " through a letter (" << boardc << ") or trying to" << endl; +#endif + + bool endofthrough = false; + + if (dirpos < edgeDirpos) { + extendright(partial + (Letter)QUACKLE_PLAYED_THRU_MARK, p, + row, col, 0, righttiles + 1, horizontal); + +#ifdef DEBUG_GENERATOR + UVcout << " next square is " << board().letter(rownext, colnext) << endl; +#endif + + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rownext, colnext))) { + endofthrough = true; +#ifdef DEBUG_GENERATOR + UVcout << " woohoo! next square is empty" << endl; +#endif + } + } + else { + endofthrough = true; +#ifdef DEBUG_GENERATOR + UVcout << " woohoo! at the edge of the board" << endl; +#endif + } + + if (!t) { +#ifdef DEBUG_GENERATOR + UVcout << " but " << partial + boardc << " isn't a word" << endl; +#endif + } + + if (endofthrough & t) { + if (m_laid > 0) { + Move move; + move.action = Move::Place; + move.setTiles(partial + (Letter)QUACKLE_PLAYED_THRU_MARK); + if (horizontal) { + move.startrow = row; + move.startcol = col - (partial.length() - righttiles); + } + else { + move.startrow = row - (partial.length() - righttiles); + move.startcol = col; + } + move.horizontal = horizontal; + move.score = board().score(move, &move.isBingo); + move.equity = equity(move); + + int laid = move.wordTilesWithNoPlayThru().length(); + bool onetilevert = (!move.horizontal) && (laid == 1); + bool ignore = onetilevert && (board().hcross(row, col) != Utility::Max); + + if (1 || !ignore) + { + + if (m_recordall) { + m_moveList.push_back(move); + } + + if (MoveList::equityComparator(best, move)) { + best = move; + } + +#ifdef DEBUG_GENERATOR + UVcout << "found a move: " << move << " which has equity " << move.equity << endl; +#endif + } + } + } + + } + else if (!lastchild) + // else if ((c < boardc) && (!lastchild)) + { + extendright(partial, i + 1, row, col, + edge + 1, righttiles, horizontal); + } + } +} + +void Generator::leftpart(const LetterString &partial, int i, int limit, + int row, int col, int edge, bool horizontal) +{ +#ifdef DEBUG_GENERATOR + UVcout << "leftpart(" << QUACKLE_ALPHABET_PARAMETERS->userVisible(partial) << ", " << i << ", " << counts2string() << ", " << row << ", " << col << ", " << edge << ")" << endl; +#endif + + if (edge == 0) { + extendright(partial, i, row, col, 0, 0, horizontal); + } + if (limit > 0) { + if (i == 0) { // is this right at all? + return; + } + + unsigned int p; + Letter c; + bool t; + bool lastchild; + bool british; + int playability; + + readFromDawg(i, p, c, t, lastchild, british, playability); + + if (m_counts[c] >= 1) { + m_counts[c]--; + m_laid++; + leftpart(partial + c, p, limit - 1, row, col, 0, horizontal); + m_counts[c]++; + m_laid--; + } + + if (m_counts[QUACKLE_BLANK_MARK] >= 1) { + m_counts[QUACKLE_BLANK_MARK]--; + m_laid++; + leftpart(partial + QUACKLE_ALPHABET_PARAMETERS->setBlankness(c), p, limit - 1, row, col, 0, horizontal); + m_counts[QUACKLE_BLANK_MARK]++; + m_laid--; + } + + if (!lastchild) { + leftpart(partial, i + 1, limit, row, col, edge + 1, horizontal); + } + } +} + +void Generator::setupCounts(const LetterString &letters) +{ + String::counts(letters, m_counts); +} + +double Generator::equity(const Move &move) const +{ + return QUACKLE_EVALUATOR->equity(m_position, move); +} + +Move Generator::generate() +{ +#ifdef DEBUG_GENERATOR + UVcout << "generate called" << endl; +#endif + + for (int row = 0; row < board().height(); row++) { + for (int col = 0; col < board().width(); col++) { + + // generate horizontal plays + + // what defines an anchor square? + + bool anchor = false; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().vcross(row, col) != Utility::Max)) { + if (col == 0) { + anchor = true; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col - 1))) { + anchor = true; + } + } + else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + if (col == 0) { + anchor = true; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col - 1))) { + anchor = true; + } + } + + if (anchor) { + int k = 0; + for (int i = col - 1; i >= 0; i--) + { + // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; + + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && (board().vcross(row, i) == Utility::Max)) { + if (i == 0) { + k++; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i - 1))) { + k++; + } + } + else { + i = -1; + } + } + +#ifdef DEBUG_GENERATOR + UVcout << "looking horizontally with the " << QUACKLE_ALPHABET_PARAMETERS->userVisible(board().letter(row, col)) << " at " << row + 1 << (char)(col + 'A') << endl; + UVcout << "Apparently there are " << k << " empty spots to our left" << endl; +#endif + + m_laid = 0; + leftpart(LetterString(), 1, k, row, col, 0, true); + } + + // generate vertical plays + + // what defines an anchor square? + + anchor = false; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().hcross(row, col) != Utility::Max)) { + if (row == 0) { + anchor = true; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row - 1, col))) { + anchor = true; + } + } + else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + if (row == 0) { + anchor = true; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row - 1, col))) { + anchor = true; + } + } + + if (anchor) { + int k = 0; + for (int i = row - 1; i >= 0; i--) { + // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && (board().hcross(i, col) == Utility::Max)) { + if (i == 0) { + k++; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i - 1, col))) { + k++; + } + } + else { + i = -1; + } + } + +#ifdef DEBUG_GENERATOR + UVcout << "looking vertically with the " << board().letter(row, col) << " at " << row + 1 << (char)(col + 'A') << endl; + UVcout << "Apparently there are " << k << " empty spots to our left" << endl; +#endif + + m_laid = 0; + leftpart(LetterString(), 1, k, row, col, 0, false); + } + } + } + + return best; +} + +// TODO GET RID OF CODE DUPLICATION +Move Generator::gordongenerate() +{ + for (int row = 0; row < board().height(); row++) { + for (int col = 0; col < board().width(); col++) { + + // generate horizontal plays + // what defines an anchor square? + bool anchor = false; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().vcross(row, col) != Utility::Max)) { + if (col == 0) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) { + anchor = true; + } + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col - 1))) { + if (col == board().width() - 1) { + anchor = true; + } + else { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) { + anchor = true; + } + } + } + } + else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + if (col == board().width() - 1) { + anchor = true; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) { + anchor = true; + } + } + + if (anchor) { + int k = 0; + for (int i = col; i >= 0; i--) { // skip over filled sqs + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { + k++; + } else { + i = -1; + } + } + for (int i = col - k - 1; i >= 0; i--) { + // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && (board().vcross(row, i) == Utility::Max)) { + if (i == 0) { + k++; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i - 1))) { + k++; + } + } + else { + i = -1; + } + } + // UVcout << "Apparently there are " << k << " empty spots to our left" << endl; + // leftpart("", 1, k, row, col, 0, true); + + // UVcout << "looking horizontally with the " << board().letter(row, col) << + // " at " << row + 1 << (char)(col + 'A') << endl; + + m_anchorrow = row; + m_anchorcol = col; + m_gordonhoriz = true; + m_laid = 0; + m_leftlimit = k; + gordongen(0, LetterString(), QUACKLE_LEXICON_PARAMETERS->gaddagRoot()); + } + + // generate vertical plays + // what defines an anchor square? + + anchor = false; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().hcross(row, col) != Utility::Max)) { + if (row == 0) { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) { + anchor = true; + } + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row - 1, col))) { + if (row == board().height() - 1) { + anchor = true; + } + else { + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) { + anchor = true; + } + } + } + } + else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { + if (row == board().height() - 1) { + anchor = true; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) { + anchor = true; + } + } + + if (anchor) { + int k = 0; + for (int i = row; i >= 0; i--) { + if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { + k++; + } else { + i = -1; + } + } + for (int i = row - k - 1; i >= 0; i--) { + // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; + if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && (board().hcross(i, col) == Utility::Max)) { + if (i == 0) { + k++; + } + else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i - 1, col))) { + k++; + } + } + else { + i = -1; + } + } + + // UVcout << "Apparently there are " << k << " empty spots to our left" << endl; + // leftpart("", 1, k, row, col, 0, false); + + // UVcout << "looking vertically with the " << board().letter(row, col) << + // " at " << row + 1 << (char)(col + 'A') << endl; + + m_anchorrow = row; + m_anchorcol = col; + m_gordonhoriz = false; + m_laid = 0; + m_leftlimit = k; + gordongen(0, LetterString(), QUACKLE_LEXICON_PARAMETERS->gaddagRoot()); + + } + } + } + + return best; +} + +void Generator::spit(int i, const LetterString &prefix, int flags) +{ + // UVcout << "spit called... i: " << i << ", prefix: " << prefix << endl; + + unsigned int p; + Letter c; + bool t; + bool lastchild; + bool british; + int playability; + + readFromDawg(i, p, c, t, lastchild, british, playability); + + if (m_counts[c] >= 1) + { + m_counts[c]--; + + if (t) + { + // UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(prefix) << c << endl; + + bool usedAll = true; + if (!(flags & NoRequireAllLetters)) + { + for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) + { + if (m_counts[j] > 0) + { + usedAll = false; + break; + } + } + } + + if (usedAll) { + m_spat.push_back(prefix + c); + if (flags & SingleMatch) { + return; + } + } + } + + if (p != 0) + { + spit(p, prefix + c, flags); + } + + m_counts[c]++; + } + + if (!(flags & ClearBlanknesses && m_counts[c] >= 1)) + { + if (m_counts[QUACKLE_BLANK_MARK] >= 1 || flags & AddAnyLetters) + { + m_counts[QUACKLE_BLANK_MARK]--; + + if (t) { + // UVcout << prefix << QUACKLE_ALPHABET_PARAMETERS->setBlankness(c) << endl; + + bool usedAll = true; + if (!(flags & NoRequireAllLetters)) + for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) + if (m_counts[j] > 0) + usedAll = false; + + if (usedAll) { + m_spat.push_back(prefix + (flags & ClearBlanknesses? c : QUACKLE_ALPHABET_PARAMETERS->setBlankness(c))); + if (flags & SingleMatch) { + return; + } + } + } + + if (p != 0) { + spit(p, prefix + (flags & ClearBlanknesses? c : QUACKLE_ALPHABET_PARAMETERS->setBlankness(c)), flags); + } + + m_counts[QUACKLE_BLANK_MARK]++; + } + } + + if (!lastchild) + { + spit(i + 1, prefix, flags); + } +} + +void Generator::wordspit(int i, const LetterString &prefix, int flags) +{ + // UVcout << "spit called... i: " << i << ", prefix: " << prefix << endl; + + unsigned int p; + Letter c; + bool t; + bool lastchild; + bool british; + int playability; + + //UVcout << "wordspit(" << i << ", " << QUACKLE_ALPHABET_PARAMETERS->userVisible(prefix) << ", " << flags << ")" << endl; + + readFromDawg(i, p, c, t, lastchild, british, playability); + + if (m_counts[c] >= 1) + { + m_counts[c]--; + + if (t) + { + // UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(prefix) << c << endl; + + bool usedAll = true; + if (!(flags & NoRequireAllLetters)) + { + for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) + { + if (m_counts[j] > 0) + { + usedAll = false; + break; + } + } + } + + if (usedAll) + { + WordWithInfo word; + word.wordLetterString = prefix + c; + word.british = british; + word.playability = playability; + m_wordspat.push_back(word); + } + } + + if (p != 0) + { + wordspit(p, prefix + c, flags); + } + + m_counts[c]++; + } + + if (!lastchild) + { + wordspit(i + 1, prefix, flags); + } +} + + +Move Generator::exchange() +{ + map throwmap; + + const int rackSize = rack().tiles().length(); + const int permutations = 1 << rackSize; + + for (int i = 1; i < permutations; i++) + { + LetterString thrown; + for (int j = 0; j < rackSize; j++) + if (i & Utility::Bits[j]) + thrown += rack().tiles()[j]; + + Move move; + move.action = Move::Exchange; + move.setTiles(String::alphabetize(thrown)); + move.score = 0; + move.equity = equity(move); + + if (throwmap.find(move.tiles()) == throwmap.end()) + { + if (m_recordall) + m_moveList.push_back(move); + + if (MoveList::equityComparator(best, move)) + best = move; + + throwmap[move.tiles()] = true; + } + } + + return best; +} + +Move Generator::findstaticbest(bool canExchange) +{ + best = Move::createPassMove(); + m_moveList.clear(); + + setupCounts(rack().tiles()); + + if (QUACKLE_LEXICON_PARAMETERS->hasSomething()) + { + if (board().isEmpty()) + { + anagram(); + } + else + { + // UVcout << rack() << endl; + // UVcout << board() << endl; + + if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) + gordongenerate(); + else + generate(); + + // UVcout << "gaddag says: " << best << " " << best.score << " " << best.equity; + // UVcout << endl; + // UVcout << " dawg says: " << best << " " << best.score << " " << best.equity << endl; + } + } + + if (canExchange) + exchange(); + + if (m_moveList.empty()) + m_moveList.push_back(best); + + return best; +} + +void Generator::gaddagAnagram(const GaddagNode *node, const LetterString &prefix, int flags) +{ + for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { + Letter childLetter = child->letter(); + + if (childLetter == QUACKLE_GADDAG_SEPARATOR) { + break; + } + + if (m_counts[childLetter] <= 0) + continue; + + m_counts[childLetter]--; + + LetterString newPrefix; + newPrefix += childLetter; + newPrefix += prefix; + + if (child->isTerminal()) { + bool usedAll = true; + if (!(flags & NoRequireAllLetters)) { + for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) { + if (m_counts[j] > 0) { + usedAll = false; + break; + } + } + } + + if (usedAll) { + m_spat.push_back(newPrefix); + if (flags & SingleMatch) { + return; + } + } + } + + if (child->firstChild()) { + gaddagAnagram(child, newPrefix, flags); + if (flags & SingleMatch && m_spat.size() > 0) { + m_counts[childLetter]++; + return; + } + + } + + m_counts[childLetter]++; + } + + if (m_counts[QUACKLE_BLANK_MARK] >= 1 || flags & AddAnyLetters) { + for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { + Letter childLetter = child->letter(); + + if (childLetter == QUACKLE_GADDAG_SEPARATOR) { + break; + } + + if (flags & ClearBlanknesses && m_counts[childLetter] >= 1) { + continue; + } + + m_counts[QUACKLE_BLANK_MARK]--; + + LetterString newPrefix; + newPrefix += flags & ClearBlanknesses ? + childLetter : QUACKLE_ALPHABET_PARAMETERS->setBlankness(childLetter); + newPrefix += prefix; + + if (child->isTerminal()) { + bool usedAll = true; + if (!(flags & NoRequireAllLetters)) + for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) + if (m_counts[j] > 0) + usedAll = false; + + if (usedAll) { + m_spat.push_back(newPrefix); + if (flags & SingleMatch) { + return; + } + } + } + + if (child->firstChild()) { + gaddagAnagram(child, newPrefix, flags); + if (flags & SingleMatch && m_spat.size() > 0) { + m_counts[QUACKLE_BLANK_MARK]++; + return; + } + } + + m_counts[QUACKLE_BLANK_MARK]++; + } + } +} + +Move Generator::anagram() +{ + // UVcout << "anagram called" << endl; + + // UVcout << "about to call spit" << endl; + + m_spat.clear(); + if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) { + gaddagAnagram(QUACKLE_LEXICON_PARAMETERS->gaddagRoot(), + LetterString(), NoRequireAllLetters); + } else { + spit(1, LetterString(), NoRequireAllLetters); + } + + // UVcout << "m_spat has " << m_spat.size() << " words in it" << endl; + + WordList::const_iterator end = m_spat.end(); + for (WordList::const_iterator it = m_spat.begin(); it != end; ++it) + { + for (unsigned int k = 0; k < (*it).length(); k++) + { + Move move; + move.action = Move::Place; + move.setTiles(*it); + move.horizontal = true; + move.startrow = QUACKLE_BOARD_PARAMETERS->startRow(); + move.startcol = (QUACKLE_BOARD_PARAMETERS->startColumn() - (*it).length() + 1) + k; + + if (move.startcol < 0) + continue; + + move.score = board().score(move, &move.isBingo); + + move.equity = equity(move); + // UVcout << move << " has equity " << move.equity << endl; + + if (m_recordall) + m_moveList.push_back(move); + + if (MoveList::equityComparator(best, move)) + best = move; + } + } + + return best; +} + +bool Generator::isAcceptableWord(const LetterString &word) +{ + WordList results = anagramLetters(word); + + WordList::const_iterator end = results.end(); + for (WordList::const_iterator it = results.begin(); it != end; ++it) + if ((*it) == word) + return true; + + return false; +} + +WordList Generator::anagramLetters(const LetterString &letters, int flags) +{ + setupCounts(String::clearBlankness(letters)); + m_spat.clear(); + + if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) { + gaddagAnagram(QUACKLE_LEXICON_PARAMETERS->gaddagRoot(), + LetterString(), flags); + } else if (QUACKLE_LEXICON_PARAMETERS->hasSomething()) { + spit(1, LetterString(), flags); + } + + return m_spat; +} + +void Generator::storeWordInfo(WordWithInfo *wordWithInfo) +{ + if (!QUACKLE_LEXICON_PARAMETERS->hasSomething()) + return; + + setupCounts(String::clearBlankness(wordWithInfo->wordLetterString)); + + wordWithInfo->probability = Bag::probabilityOfDrawingFromFullBag(wordWithInfo->wordLetterString); + + m_wordspat.clear(); + wordspit(1, LetterString(), 0); + + vector::const_iterator end = m_wordspat.end(); + for (vector::const_iterator it = m_wordspat.begin(); it != end; ++it) + { + if ((*it).wordLetterString == wordWithInfo->wordLetterString) + { + wordWithInfo->british = (*it).british; + wordWithInfo->playability = (*it).playability; + return; + } + } +} + +void Generator::storeExtensions(WordWithInfo *wordWithInfo) +{ + // TODO(olaugh) +} + -- cgit v1.2.3