Author: jwasserm

Last week, I worked on getting pictures of the Scrabble board using our RPi camera that will be useful for testing the computer vision. Cody and I took these pictures together; he held a phone flashlight for appropriate lighting and I held the RPi camera in place. The set of pictures we took includes one valid word horizontally, one valid word vertically, one horizontal and one vertical word crossing each other, words on the edges of the board, and multiple words intertwining on the board with some invalid words. Having a variety of pictures with a better angle and better lighting than last time will be better representative of when we get the gooseneck mount and ring light. I also worked on the design report, writing the first five sections of it. Timing wise, I’d say I’m a little behind on my work with the hint generation, so next week, I will focus more time dedicated to coding the hint module. Last week I did a bunch of work with cv image capture and I wasn’t able to do as much as I wanted to with hints.

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.