Author: jwasserm

This week, I began coding some of the hint module. In the paper which we are basing the algorithm off of, they use something called cross-checks (possible letters that can fit in a word vertically if a horizontal word is played and vice versa), and I wrote a function that takes in the state of the board and updates the cross check set for each square. I also wrote a function to find anchor squares (empty squares directly adjacent to filled squares), which will be a starting place for word generation.

I got the Raspberry Pi camera set up and took a picture of our Scrabble board to start with initial testing with our cv. It was hard to get a great angle with the Pi camera so making some sort of intermediary rig might be helpful for the future. Here are the pictures I took:

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.

This week I gave the Proposal presentation for my team on Monday 9/16. Most of my weekend before the presentation was spent fixing up the presentation and practicing my delivery. Also, began looking into the most efficient algorithms for hint word generation. One way would be to make a tree-like structure and traverse through the tree with the words in the player’s rack and the words on the board. To make the problem more manageable, I will break it down to only thinking about words that can go horizontally and then tackle the vertical direction. I looked through the ECE Inventory list and requested a camera for our project based on our needs for resolution. Next week, I will continue to look into word generation algorithms for hint logic and possibly start the code if I find an algorithm that I deem is the best way out there.