CS298 Proposal

Scrabble Artificial Intelligence Game

Priyatha Joji Abraham (priyathajoji@gmail.com)

Advisor: Dr. Chris Pollett

Committee Members: Dr. Robert Chun, Dr. Philip Heller

Abstract:

The primary objective of this project is to build two intelligent AI players for Scrabble game that have different move generation and end - game strategies and evaluate both in terms of different statistics like the quality of moves, highest score, and memory consumption. The first AI player will be a version of Maven, the most notable Scrabble AI player that combines a one - ply search that evaluates the candidate moves and selects the most promising moves based on optimal decision making and has a Q - sticking end - game strategy. The Q - sticking strategy plays out the unplayable tiles that produce an awkward rack during end game. The second AI player would be implemented differently and contains a static evaluation function that selects best-first move and a slow-play end - game strategy with the intent of maximizing score. The main challenge of this game is it is a game of imperfect information as each rack of tiles is hidden from the opponent and the consumption of time to calculate most promising moves. Moreover, playing out the unplayable tiles like Q, Z, J during end - game is crucial and challenging.

CS 297 Results:

  • Implemented the Scrabble Notation System.
  • Implemented the Human Scrabble Player that can perform a legal play.
  • Implemented the straightforward strategy used for the discovery of the most promising words using a trie data-structure.
  • Implemented a simple AI player.

Proposed Schedule

Week 1, 2: August 29, 2017 - September 12 2017Build a program that evaluate candidate moves
Week 3: September 13, 2017 - September 19, 2017 Deliverable 1: Develop an intelligent computer player, version of Maven, that selects the most promising move from the set of candidate moves using using one-ply search
Week 4: September 19, 2017 - September 25, 2017Work on the Q - sticking end - game strategy that play out un-playable tiles like Q, Z during end - game
Week 5: September 26, 2017 -October 3, 2017Deliverable 2: An AI player that focuses on Q - sticking end - game strategy
Week 6, 7: October 3, 2017 - October 16, 2017Build another AI that can play a slow - endgame strategy
Week 8: October 17, 2017 - October 23, 2017 Deliverable 3: Compare AI players with Q - sticking end - game strategy and slow - end game strategy
Week 9, 10: October 24, 2017 - November 6, 2017Work on the static evaluation function that selects best first move
Week 11: November 7, 2017 - November 13, 2017Deliverable 4: Comparisons of both AI players
Week 12, 13: November 14, 2017 - November 27, 2017Deliverable 5: CS298 Report
Week 14: November 28, 2017 - December 5, 2017Deliverable 6: Presentation

Key Deliverables:

  • Software
    • Develop an intelligent computer player that selects the most promising move from the set of candidate moves using using one - ply search
    • An AI player that focuses on Q - sticking end - game strategy
    • Compare the AI players with Q - sticking end - game strategy and slow - end game strategy
    • Comparisons of both AI player in terms of quality of moves, score and memory consumption
  • Report
    • CS298 Report
    • CS298 Presentation

Innovations and Challenges

  • Comparisons of AI which is a version of Maven with another AI with different move selection and end-game strategy is worth investigating to learn about the potential of AI in Scrabble game.
  • Evaluation of possible future moves in limited time and memory.
  • Playing out the unplayable tiles during end-game is crucial and challenging to win this game.

References:

[1] S. Russell and P. Norvig, Adversarial search, in Artificial Intelligence: A Modern Approach, 3rd ed. New Jersey: Pearson, 2010, Ch. 5, pp. 161-189.

[2] F. Di Maria and A. Strade, An artificial intelligence that plays for competitive scrabble, in Proc. AI*IA Workshop, Bologna, Italy, 2012, Vol. 860, pp. 98-103. [Online].Available: http://ceurws.org/Vol-860/paper16.pdf

[3] C. Browne et al., A survey of Monte Carlo Tree Search methods, in IEEE Trans. Comp. Intelligence and AI in Games, Vol. 4, no. 1, pp. 1-43, Mar. 2012. [Online]. Available: http://www.cameronius.com/cv/mcts-survey-master.pdf

[4] M. Richards and E. Amir, Opponent modeling in Scrabble, in Proc. 20th International Joint Conf. Artificial Intelligence, Hyderabad, India, 2007, pp. 1482-1487. [Online]. Available: http://reason.cs.uiuc.edu/mdrichar/my_papers/IJCAI07-239.pdf

[5] B. Sheppard, World-championship-caliber Scrabble, Artificial Intelligence, Vol. 134, pp. 241- 275, Jan. 2002. [Online]. Available: http://ac.elscdn.com/S0004370201001667/1-s2.0-S0004370201001667-main.pdf?_tid=490191b6-2168-11e7-91f6- 00000aacb35e&acdnat=1492211924_4ed8a733c08936feace8b1ad2aab9c37