Category: Jolie Status Report

The past week, I’ve been working on the game state tracker and some integration tasks such as getting the camera to take pictures within our python program as opposed to just from the command line. Cody and I spent a good amount of time on this task that shouldn’t have taken so long. We were getting an error that the camera was busy and couldn’t take the picture. We ended up earning this was because we had initialized a cv2 camera instance we were thinking of using and forgot to comment it out.

I had already written the functions for most of the intricacies of the game state tracker, so the rest was just interfacing with the MQTT protocol that Denis set up. Today, we tested the whole system together and it went quite well. I found a couple bugs in the check_board function I had written in terms of calculating the start and end column for a horizontal word. But after fixing that, when we pressed the “Check” button on the individual player touch screen, we got the point total and validity back! We are still deciding the convention we put in place for submitting words, whether we should require a check beforehand or not.

I am glad at the place we are in now, and hopefully we can finish up the home stretch in a relatively smooth manner. I’ve been working on the final report for the past three weeks, editing from the design report, so I think we should get that done soon.

These past couple weeks, Denis and I put a lot of work into the user interface with the individual touch displays. It took some trial and error with the driver to get the desktop of out RPi 0s to show up on the lcd display (which was quite frustrating) but we ultimately got the desktop to show. The touch portion was touch and go (no pun intended) for a while where it would randomly work or not work on boot. We think we found the problem with a race condition on boot up that would sometimes permit the touch functionality and sometimes  not. Denis and I laser cut a box for the battery pack and buck converter to fit in. The display then rests on top of the box for a clean wireless look.

I made the front end of the user facing app user tkinter graphics where I made a keyboard, tile display box, player scores, “check”, “submit”, and “hint” buttons, and then ultimately a page for hint results. This will be how players interact with our system.

For this upcoming week, we really need to finish integration, mostly of the cv with the rest of the system. I think we are in a good place to have everything done by the demo.

It’s safe to say I gained a lot of new skills throughout my Capstone experience this semester. First off, I was able to write the hint generation algorithm from help from the article https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf. I spent many hours rereading this to understand how the backtracking algorithm worked and researched more into the ins and out of the directed acyclic word graph. Furthermore, I had no prior experience with tkinter graphics so I read specs and watched videos on how to make a simple app and then expanded on it from there.  Finally, when debugging the issues we were having with the RPi 0s, I read many posts from Raspberry Pi Forums from people who were having similar issues to us. Often times, it would take many iterations of Forums to find a possible fix, which gave me good experience of dealing with this type of hardware.

This past week I wrote and debugged functions for validating a new board and calculating the score for that new move. The check_board function takes in the board with the possible new word placed in it and a list of the squares that tiles were just placed (should be in order left to right or up to down). The function find the new board made, looks it up in the dawg (much quicker look up time than a simple linear search in the dictionary). If it’s not in the dawg, the function returns a tuple of (False, 0), meaning it’s not a valid word and scores 0 points. If it is a word, the new board, start and end position of the word, and tiles added are passed into the calculate_score function I wrote which only includes the score and letter multipliers for tiles that are newly placed (accoding to official Scrabble rules). The total score for the new word is updated in check_board. If the placed word is horizontal, the function goes through each letter and does word validation and score updating on the new word made vertically if there is one, and vice versa for a vertical main word.

Denis has been able to refactor my hint logic and put it on the Pi for communication with the Pi 0s. This will be used for our demo next week.

I completed my tasks on time so far, and in the coming weeks, I will pick up some integration tasks in terms of interfacing with the LCD displays and interfacing the output of Cody’s cv with the input of the check_board function.

Verification:

For the scoring, I ran tests where I placed different words (horizontal and vertical) on the board (2D list) and verified that the computed score was correct. I also varied the “tiled_added” list so make sure that letter and word multipliers weren’t added to already filled in squares. I did a similar practice with the check_board function.

For the hints algorithm, I used a unit testing approach where I tested each function on it’s own before testing the whole hint generation since it is a complex algorithm. Timing wise, the hint generation takes about 0.05 seconds on my computer. On the Pi, processes seem to run 8 times slower, but this is still well within our time allotted of 1.4 seconds (design requirement).

Last week, I finished up the hint logic, fixing some of the last little bugs as well as generalizing the algorithm to the vertical direction. Denis is now able to run the hint logic on the main RPi and can send receive hints with the RPi0s.. Also, I set up the gooseneck camera mount. I laser cut a platform (rectangle with four holes in it so that I could zip tie  it to the top of the camera mount we bought). I then was able to clip the ring light onto the platform. The RPi and RPi camera rest on the platform and the camera is looped through the ring light. The picture below is what the mount + platform looks like (without the RPi on it). The other picture is what I took from my phone camera. Just from that, we can see how the ring light really helps eliminate shadows that we were seeing before.

Last week, I wrote a preliminary scoring function where letter and word multipliers are taken into account (but haven’t tested it yet). This upcoming week, I plan on testing the scoring function as well as writing the function that takes in the newly placed tiles and validates/scores all the newly created words.

After this week, I feel more confident that we are running on schedule, but we must not let up and finish strong this last month of the semester.

 

This week I made a lot of progress with the hint generation. Right now, we can find all the horizontal words possible given the state of the board and rack. There is still one bug that I need to fix dealing with anchor squares which also have a filled square to the left. I just need to remove those anchor squares from the anchor list so that invalid words don’t propagate through, which shouldn’t be hard to fix. I also need to generalize the algorithm to the vertical direction. The hard part was already done in the horizontal direction, so the vertical functions should be easy to implement as they are just the transpose of the horizontal functions. Shown below is a snippet of the list of valid words, along with there start and end square, that the backtracking function returns.

 

Last week, I mentioned I was a bit behind on hint generation. I was able to catch up this week and made some good progress. Shown in the attached file, I added a function which updates cross-checks after a word is played. The next step is to implement finding prefixes and suffixes given an anchor square. I need the data structure of the language for that. The article we are basing the algorithm off uses a Directed Acyclic Word Graph. I found an open source implementation of the DAWG and will discuss will discuss with the team tomorrow when we meet what the think of using it.

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.