summaryrefslogtreecommitdiff
path: root/generator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'generator.cpp')
-rw-r--r--generator.cpp1883
1 files changed, 1883 insertions, 0 deletions
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 <fstream>
+#include <iostream>
+#include <math.h>
+
+#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<int, bool> 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<int> 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<int> hrows;
+ vector<int> hcols;
+ vector<int> vrows;
+ vector<int> 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<LetterString, bool> 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<WordWithInfo>::const_iterator end = m_wordspat.end();
+ for (vector<WordWithInfo>::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)
+}
+