Automated Words with Friends and Scrabble move generator
playInSelenium.py uses the computer vision library OpenCV to read the board and tile rack from the WordsWithFriends messenger app. Simply run playInSelenium.py, login to facebook messenger in the google chrome window that opens and navigate to the game you would like to play. (if not working try: brew upgrade chromedriver or: brew install chromedriver)
The underlying backtracking algorithm is a python implementation of 'The World's Fastset Scrabble Program - Appel and Jacobson (1988)'
The major components of the algorithm are Anchors and Cross Sets.
The anchor of a newly place world is the left-most, newly placed tile that is adjacent to an existing tile.
Therefore the potential anchors, i.e. the candidate places where new words could be placed, are all the tiles adjacent tiles already on the board.
The algorithm reduces the problem to one dimension by using Cross Sets.
A Cross Set for a tile is the set of letters that can form a valid word when considering the letters vertically adjacent to the tile.
By only considering the letters in the Cross Set of each tile when forming rows horizontally we can simply consider forming horizontal words. The board can then be transposed to find the vertical words.
Once the anchors and cross sets are known the backtracking algorithm is used to form words from the anchors. The algorithm extends left from the anchor considering all combinations of the rack. Each left part is then extended right into all possible valid words by traversing the lexicon pruned by the cross sets.
The Original Lexicon used is the Enhance North American Baseline Lexicon (ENABLE) The lexicon is adjusted whenever previously unencountered words are found. The lexicon is currently stored in a trie data structure. This means lookups are O(k) instead of O(N). Where N is the size of the lexicon and and k the length of the word.
See log.txt for plans for future improvements