Developing an Artificial Intelligence to Play the Board Game ...

UNIVERSITY COLLEGE DUBLIN TRINITY COLLEGE

DISSERTATION MAI IN ELECTRONIC & COMPUTER ENGINEERING

Developing an Artificial Intelligence to Play

the Board Game Scrabble

Author: Carl O'CONNOR

Supervisor: Dr. Carl VOGEL

Submitted to the University of Dublin, Trinity College, May, 2015

Declaration

I, Carl O'Connor, declare that the following dissertation, except where otherwise stated, is entirely my own work; that it has not previously been submitted as an exercise for a degree, either in Trinity College Dublin, or in any other University; and that the library may lend or copy it or any part thereof on request.

Wednesday 20th May, 2015 Carl O'Connor

i

Permission to Lend

I agree that the Library and other agents of the College may lend or copy this dissertation upon request.

Wednesday 20th May, 2015 Carl O'Connor

ii

Summary

This project uses a data structure called a GADDAG for lexicon storage and a weighted heuristics method for word evaluation in a computer based game of Scrabble. The GADDAG structure is assessed for its speed and performance in generating words. It was found to be well suited for this purpose facilitating rapid word generation. It required quite a large amount of system memory to be constructed however which is highlighted to be a possible flaw. Weighted heuristics proved to be a fast and reliable method for move evaluation for the most part. However, it was prone to some strategic errors is judgement. An alternative method to address this is also discussed. Weighted heuristics could also be used to introduce other game elements such as realism to the game. A method for doing this using a word frequency data source is proposed.

iii

Abstract

This project describes a Java implementation of the well known board game Scrabble. The application was written to be played by a human and computer controlled player. It takes a look back at previous attempts to implement such a system and draws on these. Lastly, an implementation of a more realistic computer controlled opponent is proposed.

iv

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download