Results

After turn one, the scores of both Richard and Nixon (our Ais' names) are almost equal. But the times each of them took to find a word are 0.03 seconds and 15 seconds respectively.

Turn two. Fun Fact: Our best algorithm is named after the best Scrabble player Nigel Richards.

Turn three

Over four turns, the total scores of Richard and Nixon are pretty close to each other. But the average times taken to compute each turn are 0.032 seconds and 8.187 seconds

The reason why Richard is so fast is the seaching algorithm. The word list is arranged in the form of a tree which cuts down the computation time incredibly. Here is what a part of the tree looks like:

               *

               |

     +----+----+----+----+

     |         |         |
     A         B         C
     |         |         |
  +--+--+      E      +--+--+
  |     |      |      |     |
  P     C    +-+-+    E     A
  |     |    |   |    |     |
  P     T    A   E    L     T
  |          |        |
+-+-+      +-+-+      L
|   |      |   |
E   A      T   N
|   |      |   |
A   L      L   S
|   |
L   L

It has a branch for every letter. Each time Richard chooses a letter branch, the search cuts down because there are 25 branches that need not be searched. Hence, if the Scrabble palyer has A and C tile but no B, the algorithm will not enter the B branch.

Whereas, the slower algorithm has to loop through a list of words. Unlike tree, the list algorithm goes through each of the word, not cutting down the list of words to be searched. That takes time and slows down the search process.

UML Diagram

We used Model_view_control architecture in our code

TOP OF PAGE

Project Proposal

The Big Idea:

The big idea is to create a scrabble game and then create multiple AIs to play each other and determine which one is better. We are thinking of making one AI that plans its moves ahead of time and one that impulsively just chooses the maximum points available at the time.

Learning Goals:

• Paul: I want to learn about more efficient data structures that will allow our team to process huge numbers of words relatively quickly and efficiently. I think that this will be an important skill for this project and for many projects to come. I especially would love to get a better understanding of algorithms for solving puzzles like this.
• Meghan: I would like to learn more about how to better structure my code and how to code with a team (including better use of Github). I also really like the idea of creating an algorithm that solves a problem. Although this project is specific to solving a game of hangman, I think algorithm building is a skill that would be applicable to many other projects.
• Shruti: I would like to learn about the architecture of code and how it affects the efficiency and understanding of the code. I would also like to understand how to approach a new library and parse its syntax.

Implementation Plan:

The goal is to create a Scrabble AI with a smaller dictionary of words (about the size of 1000 words). We then plan to make two AIs to solve and play scrabble in two different ways. Initially, we just want an ASCII output of the board with Scrabble alphabets. We will build and test one working algorithm and then move to the second one.

Project Schedule:

• Design Review (4/2): Have a completed, detailed overview of the code architecture Pseudocode for the algorithms we will be trying
• Code Review (4/13): Working game At least one rough but functioning algorithmz
• Mid-Project Presentation (4/23): Two fully functioning algorithms
• Final Product (5/6): Make presentation look pretty.(GUI/Interactive visual interface?)

Collaboration Plan:

We plan to start out together, pair programming until we have a clear idea about the code architecture and then branch out. We will individually read up on documentation and then get together to pair program. Initially, there won’t be individual parts to work on until we get to the display/GUI portion of the project.

Risks:

It might end up taking a long time to run because our program will have to cycle through such a long list of words. We are trying to combat this risk by first starting with a more limited pool of words. We could also have some risks defining the board and the rules of the game because they may not translate well into code. Also, we may have trouble finding a way to make everything modular, making it difficult to put different AIs simply into the program.

Additional Course Content:

Learn about code efficiency and how to improve the processing speed Tips and tools for creating algorithms

TOP OF PAGE

Design Review

Preparation and Framing

Background and context

Our project consists of a Scrabble solver AI. The game has two different algorithms play against each other. There will also be an option to have the user play against the two algorithms.

Key questions

• Do you have any advice about code architecture? (Is this the best way for us to structure things?)
• Do we have appropriate use of classes?
• How should we keep track of tile locations? (Matrix? List?)
• Should we use two algorithms with equally good features? Or should one of them be reasonably better than the other?
• Do you have any cool algorithm /strategy ideas that we haven’t discussed?

Agenda for technical review session

• Discuss code overview/architecture
• Discuss algorithms being used

Algorithms

1. Permutations: Find all places where words could be made List all permutations with inventory letters Check list for legal words Play word with highest score
2. “Human way”: Search a dictionary for all words that could be made with inventory letters plus any one other letter See if the one letter is on board, if word can be placed there Play word with highest score
3. Thinking ahead: Does all the things that #1 does plus somehow thinks ahead. Saves high score letters for double/triple point spots? Doesn’t play U alone if also has Q in inventory? Etc.
4. “Smart human way”: Makes list of all letters on board that could have a letter added (spatially, not legally) Cycles through list: each time makes new alphabetized list that includes inventory plus the letter from board Searches all combinations of these letters as key in dictionary of all words, element in dictionary is the actual word Play highest scoring legal word

Design Review Reflection and Synthesis

Feedback and Decisions

• Due to feedback given to us, we decided to change Inventory from a class to an attribute of each Player.
• A really important point was brought up that we were looking at different methods of implementing the same strategy.
• From this, we discussed the pros and cons of two options. We have not reached a final conclusion as to which of these two routes we will be taking but have become aware of the options and are continuing research based on this feedback.
  
  1. Creating algorithms that implement different strategies (simple highest point or looking into future, etc.) and seeing which performs better
     
  2. Creating algorithms that implement the same basic strategy (simple highest point) in different ways and comparing their speed.
• A classmate suggested that we use a simple command line interface instead of using pygame. We appreciated this advice but still felt that the time that we were putting into making a decent interface was well worth the ease it would lead to when testing and debugging.

Review Process Reflection

• Our team stuck fairly well to our agenda. This was especially good because we think we did a good job in realizing what our key questions were.
• Not only were our questions answered but we got some answers to questions we didn’t even realize we had (for example the speed vs. strategy concept mentioned above).
• We feel that we made the right choice in not having our classmates look into the algorithms we were using too much because it was more useful to explain them during the review, both because it furthered our own understanding and because it allowed relevant questions to be presented in real time as the others learned about the algorithms.
• We feel that in this design review the format that our team used was appropriate--specifically in not using the projector--but feel that in the code review projector/ computer use will be more appropriate.

TOP OF PAGE

Code Review

Here is what the game looked and functioned with no implementation of the AI

Our goals for this discussion:

We want to know if our code is ready for implementing algorithms, and if you guys have any advice on how to streamline our code so it’s easier to add AI’s into the program. We would also love to have some advice on life.

Background and Context:

As we discussed before, we will be implementing artificial intelligence for the game of Scrabble. After the design review, our team talked about whether we want to focus on the speed of the algorithm or the high score. We decided that we want to focus on the speed. As of now, we have a model-view-controller setup. The Model includes classes for the Inventory, the Letter Tiles, the Bag of unused tiles, Players, and the board’s structure. The view contains the visual elements of the game, including drawing the board. Control takes inputs from three buttons of a mouse.

Key questions:

• What would be an effective strategy for improving the running speed of our code with regards to the inventory and tile draw?
• Should score still be considered at all?
• Is Model-View-Control a good way to structure the code for implementing AI?

Agenda of the technical review:

• We will first talk about the minor changes we made to the code and the design.
• We then want our classmates to review our code structure.
• We will end our discussion with how to implement the artificial intelligence in different ways.

Code Review Reflection and Synthesis

Feedback and Decisions

• One of our major concerns was how good MVC architecture will be with our AI algorithm. From the feedback, we understood that implementing different algorithms will not be very difficult. Our peers also reinforced our belief that it was important to start working on the algorithms as soon as possible. For this reason we have decided to start working on the algorithms and work out some minor bugs and unimplemented features of the game later.
• It was suggested that we take advantage of the tree structure to manipulate the available options given a player’s inventory. We have decided to try this and have begun implementation. We may end up asking Paul for further advice on how to do this.

Review Process Reflection

• Our code review process went as expected, in terms of time allocated to briefing about the code, asking questions and getting feedback.
• We benefitted from using the projector, both to show our current “game” and to highlight some pieces of our code.

TOP OF PAGE