CS297 Proposal

Scrabble AI game

Priyatha Joji Abraham (priyathajoji@gmail.com)

Advisor: Dr. Chris Pollett

Description:

Scrabble is a well-known cross-word board game which requires an efficient strategy to win. In this project, we are aiming to design a human opponent scrabble game that can generate intelligent behaviors using the methods of Artificial Intelligence (AI). Monte Carlo Simulation which takes the average of random repeated samples in the decision space and then creating a search tree is found to be a good approach to AI games. In this two player game, between human and machine,one player can hold only seven tiles on his / her shelf. Each tile, which has an associative point, is used to construct words on the board and win points. Consequently, word strategy plays an important role here as longer words can be risky as it exposes larger area. The next player, should horizontally or vertically connect to the initial word. Penalty is imposed on the player, if the word formed is invalid. Player with the maximum score wins the game. Generation of human-like judgements have to be addressed in the project in addition to the quick dictionary search.

Schedule:

Week 1: 07 Feb 2017 - 13 Feb 2017 Research on papers based on board-games and read relevant chapters from AIMA.
Week 2: 14 Feb 2017 - 20 Feb 2017 Presentation on AI game algorithms based on chapter 5 of Reference[3]
Week 3: 21 Feb 2017 - 27 Feb 2017Deliverable 1: Find or design a simple notation system for scrabble game
Week 4: 28 Feb 2017 - 6 March 2017Analyze suitable searching algorithms
Week 5: 7 March 2017 - 13 March 2017Develop a way to view current board states and maintain rack of each player
Week 6: 14 March 2017- 20 March 2017 See how to store words using a trie data-structure
Week 7: 21 March 2017 - 27 March 2017Investigate on strategies to move the tiles efficiently.
Week 8,9: 28 March 2017 - 10 Apr 2017 Deliverable 2: Design a human player version of Scrabble that uses a trie to store dictionary
Week 10,11: 11 Apr 2017 -18 Apr 2017 Create JUnit test cases for Trie and research on ways to implement AI strategies
Week 12: 19 Apr 2017 - 2 May 2017Deliverable 3: Design an ordinary computer player with no intelligence
Week 13: 3 May 2017- 8 May 2017 Learn about Monte Carlo simulation and Figure out ways to implement Monte Carlo Simulation
Week 14,15 : 9 May 2017 -22 May 2017 Deliverable 4: CS 297 first report Develop a simple Monte Carlo simulation game engine
Week 16: 23 May 2017- 29 May 2017 Deliverable 5: CS 297 final Report

Deliverables:

The full project will be done when CS298 is completed. The following will be done by the end of CS297:

1. Design or find a simple notation system suitable for scrabble game.

2. Design a human player version of Scrabble that uses a trie to store dictionary

3. Design an ordinary computer player with no intelligence.

4. Develop a simple Monte Carlo simulation game engine. .

5. CS297 Report.

References:

[1] An Artificial Intelligence that plays for competitive Scrabble. Fulvio Di Maria, Alberto Strade. Research Gate. 2012. Available url: An Artificial Intelligence that plays for competitive Scrabble

[2] Analytics-driven dynamic game adaption for player retention in Scrabble. Brent Harrison, David L. Roberts. IEEE. 2013. Available url:Analytics driven dynamic game adaption for player retention in Scrabble

[3] Artificial Intelligence: A Modern Approach (3rd Edition) 3rd Edition. Stuart Russell (Author), Peter Norvig (Author)

[4] A Survey of Monte Carlo Tree Search Methods. Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener , Diego Perez, Spyridon Samothrakis and Simon Colton. IEEE. 2012. Available url:A Survey of Monte Carlo Tree Search Methods