Jolie’s Status Report for 9/28

Throughout the course of this week, I delved deeper into the understanding of finding the best possible scrabble words given the state of the board and the player’s hand. I found an article by Andrew Appel and Guy Jacobson (from CMU SCS) written in 1988 where they implemented such algorithm. Here they used a DAWG (directed acyclic word-graph) to keep track of valid words and easily search for possible words. I plan on implementing a similar algorithm but also include functionality for searching from the anchor square looking right (the article only included an explanation of searching from left of an anchor square). An anchor square is defined as an empty square adjacent (horizontally or vertical) from a filled square. Additionally, I learned how to “cross check” newly placed letters. If a word is being placed horizontally, the cross checking occurs vertically on each newly placed tile. Each empty tile on the board is assigned a list of letters that can be placed there given the letters already placed near them. When a tile is placed, we check to see if it’s in the cross check list. If not, the move is not valid. This makes the search for possible new words shorter by taking out all references to invalid cross-check letters. Next week, I will continue to look into this method and start modularizing the algorithm.