Development of a Windows Based Scrabble Game

Abstract

A windows-based scrabble game is developed and implemented, which has having advanced features for the game. The game can be played between human against computer. Human can check the word before placing a word on to the board. There is a functionality to check the words in dictionary. The tools required for the game design are explained below. The game designed must be a good looking, user must understand clearly about the game of scrabble.

During the design phase, an algorithm has been developed for the computer player. The computer player can play the game based on the algorithm by combining dictionary to it. When computer wants to play the game, it will search the word and place the word in the standard dictionary order, by checking the maximum score. When the bag is emptied, the player who posses maximum score is declared as the winner of that respective game.

Introduction

In everyday life millions of people are using internet in worldwide to search data, upload documents and playing games and so on, due to which internet has been a part of daily routine life. Now a day internet has been exposed to all kind of people. Especially internet has been a source of entertainment of all kinds of ages. In which games are the most prominent ones, out of which Chess, Sudoku puzzle, Scrabble etc.

The present report deals with Scrabble game. Scrabble is one of the most popular crosswords games played by millions of people web world. Scrabble game was invented by Alfred M. Butts during 1930s. He used letter frequent counts from newspapers crossword puzzles to distribute the tile and relative point’s values. From common vowels they used 9-12 tiles for less common letter single tile was used [1]. It is usually played by the different age group starting from eight. Opponents’ make play by forming of words on 15 x15 grid board. This game can be played between 2 to 4 players at a time, in present project we deal with two players only. Initially a bag consisting of 100 tiles out of which 98 tiles posses’ letters and two tiles are empty this acts as wild cards; as it is a substitution of any letter, in which seven tiles are randomly selected for each player. Points are subsequently divided respective tiles according to tile points (Tile point figure number). The player who acquires maximum points in total is declared as winner.

The probability of playing game may be either human-human, human-computer. In this report we deal with two players only, that is human and computer. The most essential part of the game is predefining dictionary, as this plays a key role in Scrabble games.Algorithm should be implemented for computer player which will be discussed in later stages.

1.1 Motivation

The motivation for doing this thesis was to understand the gaming concept. It gave me an opportunity to be a part of game technology in web world. I am interested in doing a real time and technical coding project. This gave me an opportunity to learn in detail study of algorithm and gaming concepts. As such games have been a new trend to strengthen our vocabulary. Today, vocabulary plays a major role in carrier opportunities.

1.2 Aim

The aim of the scrabble project is to write a computer program that can play against the human or a computer. We are going to implement a program that supports two types of game formats: human-human and human-machine. “One advantage of playing game with a machine, rather than a person is that the opponent responds immediately with the best possible word, so there is absolutely no waiting time” [2]. After playing a game against the machine, there is a human advantage. Human can say which letters are still remaining and it can hold back letters for further use. For example, while machine is playing the game that can place the words which is having highest number of points. But the human can hold the letter for the future use.

1.3 Objectives

The main objective of the project is to develop a programming code for a game which plays with human- computer interface and machine interface.

The game is designed as follows:

Creating a good gaming environment for the players.

Compile the code so that it is enable to check the score and declare the winner at last.

The following are the essential requirements:

Implementing the code and efficient game playing algorithm for computer player like GADDAG.

Implementing the code and efficient dictionary words storage. Lists concept is been used for dictionary technology to retrieve the words from the text document to GADDAG algorithm to verify the words in dictionary words.

Producing of good GUI’s for this game.

1.4 Challenges

The main challenge of the project is to understand the algorithm and implement in scrabble game. This is a challenging task as the logic of the computer scrabble should be correctly planned. Improper design would lead to expensive process of implementation, as we need to track back to algorithm.

Despite of many games developed, our game developed must be a high quality one which provides a good user interface.

The starting word formed should pass from star tile which gives the points acquired, if not place correctly a dialog box appears saying “word must pass the centre star” which was a prominent challenge I faced.

Other challenging task was to drag and drop the tile on the scrabble board, if not correctly drag and drop the letter restores to rack.

Another key factor is to drag and drop the letter tile to the appropriate cell. When it is not been drag to the appropriate cell it might occupy any surrounding cells.

To know the location of the letter placed on the board was one of the key challenges which I have faced, for which a program was been defined to know the location of the letter.

Another challenge that I faced is to store a dictionary words in the GADDAG algorithm.

In order to know the score of the word formed a separate code was been prepared which was one of the challenges I faced.

Literature Survey

In this section we are go in detail background material and technical specification that we are going to use in our scrabble project. We will start the scrabble history in Section 2.1. In section 2.2 will read the scrabble game and rules. In section 2.2.1 we can know the letter points in Tile points. In section 2.2.2 we will know the game description of scrabble how to play. In section 2.2.3 we will know the game points and the scoring to respective words. In section 2.2.4 will know the game play. In section 2.3 we will know the concepts of algorithms that we can use in our project. Section 2.3.1 will know the concept of anchor square. Section 2.3.2 will know the concept of cross checks. Section 2.3.3 there will be three types of algorithms which we can use any one in our scrabble game for computer player.

2.1 Scrabble History

Scrabble is a game first invented by Alfred Butts. Butt gave an initial idea of the game by the end of year 1931 and named it as a Lexico. This Lexico game was played without a board and players score the points on basis of length of the word. In 1938 butts gave a big breakthrough for game crosswords. He started the idea of combining the letters to the board. Design the board with 15 by 15 square and 7-tiles in each player rack. The same procedure is using from 1938 onwards to till this day. At last the name scrabble for the game and managed to register the trademark on 16th December 1948. In 1991 first world championship take place in London and 2nd takes place in New York City on 1993 [3].

board.png

Figure 2.1: Board of Scrabble game

2.2 Game details and rules

The scrabble board consists of 15-by-15 squares (225 squares) and Single Square is filled with a letter tile. The board consists of Double Word Score (DWS), Double Letter Score (DLS), Triple Word Score (TWS) and Triple Letter Score (TLS). The middle of the board consists of initial Anchor point. The starting word must be placed vertically or horizontally so that the anchor point is included in it. Initially, the game is started by placing a word and is further completed by placing the remaining words across the board.

Initially the bag consists of 100 tiles. Amongst them only 98 tiles consist of letters and two are empty tiles; out of which each letters have scoring in the range of 1-10. Alphabets like vowels are rapidly used ones and thus they have a scoring point of one and the rarely used letters like Q and Z has a scoring of ten. In this way the scores are assigned to each & every letter in the bag. When a player gets an empty tile he selects any alphabetical letter which he requires and gives the chance to his opposition to play the game.

2.2.1 Tile points

Each and every letter has different points, the points are given below:

0 point – Blank Tile.

1 point – A, E, I, L, N, O, R, S, T, U.

2 points – D, G.

3 points – B, C, M, P.

4 points – F, H, V, W, Y.

5 points – K.

8 points – J, X.

10 points – Q, Z. [4]

2.2.2 Game description:

The game is played in the real time as follows:

At the beginning of the game each player is given 7 tiles in which 7 letters are given at random by a bag.

Each player is supposed to pick a meaningful word from the given 7 tiles and placed them on the board. The same is repeated by the 2nd player.

Depending up on the scores assigned to the letters every word will give a specific score for each player.

Depending on the Double Letter, Triple Letter, Double Word, Triple Word scores are assigned to the words at that respective tiles. The player who acquires maximum score at the end is the winner.

Double Letter score: The letter placed on the Double Letter score (DLS) block will be assigned double score for that particular letter placed on it.

For example: TAP

In the above example tile “T” consist of point 1, tile “A” consist of point 1, tiles “P” consist of point 3. If any tiles of the word go in DLS block the score of that tile becomes double. If a tile A=1*2=2 will go on DLS will get score as 2 for that particular tile. Now the overall word score become 6.

Double Word score: The word placed on the Double Word score (DWS) block will be assigned double score for a particular word placed on it.

For example: TAPE

In the above example tile “T” consist of point 1, tile “A” consist of point 1, tiles “P” consist of point 3 and tile “E” consist of point 1. If any tiles of the word go in DWS block the score of that word becomes double. If a word “TAPE” will get a score as 6 by adding the actual score of the tiles. The word “TAPE” goes in DWS, now the overall word score becomes 12.

Triple Letter score: The letter placed on the Triple Letter score (TLS) block will be assigned triple score for that particular letter placed on it.

For example: TAP

In the above example tile “T” consist of point 1, tile “A” consist of point 1, tiles “P” consist of point 3. If any tiles of the word go in TLS block the score of that tile becomes triple. If a tile A=1*3=3 will go on TLS will get score as 3 for that particular tile. Now the overall word score become 7.

Triple Word score: The word placed on the Triple Word score (TWS) block will be assigned triple score for a particular word placed on it.

For example: TAPE

In the above example tile “T” consist of point 1, tile “A” consist of point 1, tiles “P” consist of point 3 and tile “E” consist of point 1. If any tiles of the word go in TWS block the score of that word becomes triple. If a word “TAPE” will get a score as 6 by adding the actual score of the tiles. The word “TAPE” goes in TWS, now the overall word score becomes 18.

2.2.3 Game points

The player gains score to a word only if it is in the dictionary words. This score is generated only by the sum of the scores of the letters in a word.

For example: TREASURE

In the above example the tile “T” consist of point 1, tile “R” consist of point 1, tile “E” consist of point 1, tile “A” consist of point 1, tile “S” consist of point 1, tile “U” consist of point 1, tile “R” consist of point 1, tile “E” consist of point 1. By adding all the scores we will get a general word score as 8.

2.2.4 Game play

C

A

R

E

A

R

E

Initially when a Human-Computer game is started, the first playing chance always goes to human. And on a Human-Human game, the chance of playing first can be selected randomly according to the players wish. After the game is started, each player is assigned with 7 tiles each. The first player will start the game, by placing a meaningful word at the centre of the board according to the standard dictionary words. The word must go through the initial anchor point in the horizontal or vertical direction.

The 2nd player will start the game, by checking the 1st player’s word at the anchor point and he can place the word any where connecting the 1st player’s word. The game proceeds in this way and all the words which are being placed (while playing) on the board acts as anchor points and thus the game leads to an end by spreading all the words across the board connecting their anchor points. The player should mainly consider the letters with high scores to form a word such that he can gain more score from each word. Finally, the highest scorer is declared as a winner of the game.

Every game is equipped with a dictionary to check correctness of a word which is being placed on the board. Once the 1st player gets a score for the word he placed on the board, the opponent player gets a chance to play the game only after the 1st player clicks the “pass” button and vice versa.

2.3 Algorithms

The algorithms that are used in the scrabble game for computer player to play. If a computer must play the scrabble game, it must search the whole board where the tiles are connected. After searching the word on the board it must check the anchor points and the crosswords for the game. Then the computer can place the word in left part of anchor point or right part of the word by continuing the previously placed word. Each and every time the computer player wants to keep a highest scoring word on the board by checking the anchor and crossword.

2.3.1 Anchor squares

A square is an anchor in the board, if it is empty and else if it is not empty, at least one adjacent non-empty square should exist [5].

For example: HE

T {N, SE, M}

Anchor squares

In the above example the 1st player kept a word “HE” from his rack. After searching the word by the computer, then started checking the anchor squares left and right of the word placed by the 1st player to form a highest score from computer’s rack. The computer can place the words like THEN, THESE and THEM.

2.3.2 Cross-Checks

The cross-checks of a square imply the set of all playable letters that can be inserted in a column wise between existing words on the board to form a new word as shown in the below example [5].

For example: CABLE {G, N, R}

GOAL

{A, S, T, M, H}

In the above example CABLE by checking the cross-checks we can keep the words perpendicularly as downwards like from A we can keep the words like AA, AS, AT, AM and AH. From the letter E we can keep the letters by connecting to another word in downward direction as EGG, ENG and ERG.

2.3.3 Algorithms

There are three types of algorithms which are best related to our project. There are as follows:

Trie.

DAWG.

GADDAG.

1.Trie

All the words in the dictionary are represented in form of a tree. The edges of tree are labelled with letters. All the words that begin with the same letters share a common path and the ending letter in that word is called as terminal node. They are represented in double circles as shown in the below example. Some of the examples like CAR, CARS, CATS, DOG, DOGS, etc, will show in below figure 2.2.

A R S

C T

S

D

O G S

Figure 2.2: structure of trie in Lexicon

As shown in the above figure 2.2, referring to the words CARS and CATS, the letters “CA” is shared between these two words, the letters R-S forms a terminal node and the letters T-S forms another terminal.

The capacity of the dictionary used here is 94,240. These 94,240 words are divided into 117,150 nodes and 179,618 edges to form a trie. The memory size of a trie occupies half a megabyte space on a normal computer [6].

2.DAWG

DAWG is abbreviated as Directed Acyclic Word Graph. Appel and Jacobson first introduced a fast move generation algorithm. This algorithm is implemented in the computer end for the games which are played human against computer like Chess, Scrabble, etc. This algorithm is a fast move generator. This algorithm is integrated with a huge dictionary and plays against a human by placing the words which as high scores compared to the human words. The dictionary words in DAWG are represented in graph structure. Let us take some examples in DAWG dictionary as CAT, CATS, CAN, CANS, DOG, DOGS and DONE are shown in below figure 2.3.

A T

C N S

D G E

O N

Figure 2.3: structure of DAWG in Lexicon

In the above figure 2.3 the dictionary words of DAWG are represented in graph structure. Equivalence sub trees in a trie are merged to form a DAWG. In this way the number of nodes is reduced from 117,150 to 19,853 minimizing the memory space. DAWG can be represented as a raw word list of only 175 Kbytes where as lexicon is represented in 780 Kbytes. This compact size allows us to use it on any modest computer [6].

Backtracking

We perform this operation in two parts.

When a human place a word on the board, the computer checks the left anchor for this word and fills it if a word extension exists.

After doing this, computer also checks the right anchor of the same word if there is any further extension of the word.

Explanation:

When a human place a word on the board, the computer searches the word from left to right to check if it can fill the left anchor square or the right anchor square of the word.

The left anchor square can be filled by adding prefix to that word by checking in the lexicon (dictionary).

If the computer finds that it cannot fill the left anchor, it searches the right anchor to check if it can extend the word by checking from the DAWG dictionary.

Else, it also checks the crosschecks to place a word.

DAWG algorithm searches for important anchors which produces high score by forming a word.

3.GADDAG:

GADDAG is a fast move generation algorithm compare to any other algorithm. GADDAG was introduced by A. Gordon. GADDAG is a finite automaton, avoids non-deterministic prefix generation of the DAWG. GADDAG implements a bi-directional search unlike any other algorithms. GADDAG is five times larger than DAWG in implementing a lexicon of any size. Using the GADDAG algorithm computer place a move two times faster than DAWG algorithm. GADDAG algorithm tries to minimize the usage of anchor squares and plays in the crosscheck format to maximize the score for the word place.

/S5 A/S9 R/S12

C/S1 C/S6 R/S12

A/S2 /S9

R/S3 A/S7 C/S10 /S12

E/S4

R/S8 A/S11

Figure 2.4: Sub graph for unminimized GADDAG for CARE word

In the above figure 2.4 CARE have 4 distinct paths, C ARE, AC RE, RAC E, ERAC. The 4 distinct paths are explained in the below example with taking CARE with ABLE word [7].

Figure 2.5: Four ways to play the words CARE with ABLE

In the above figure 2.5 it is shown how a word ABLE is placed in different ways across the word CARE after searching the left and right anchor squares.

As shown in the figure a), computer first searches the left anchor square and right anchor square of the word CARE and since could not find a chance to place a word to the right or left of the word CARE, it placed a word ABLE by doing crosscheck below the letter C.

As shown in the figure b), computer placed a word below the letter A using the crosscheck method after searching the left and right anchor square.

As shown in the figure c), computer placed a word above the letter R using the crosscheck method after searching the left and right anchor square and formed a word ABLER.

As shown in the figure d), computer placed a word adjacent the letters R and E using the crosscheck method after searching the left and right anchor square.

GADDAG algorithm will use the concept of important anchor squares which produces high score by forming a word. This is similar to DAWG algorithm.

Unlike the DAWG algorithm, GADDAG algorithm places a word in a different pattern. That is, when a human place a word across the board, GADDAG algorithm places its word anywhere (to get a maximum score) across the word placed by human.

GADDAG will see the fewer dead ends, anchor squares and use of fewer arcs rather than the DAWG. In GADDAG we use the concept of left cross set and right cross set. In the left cross set it adds a letter to the word placed by human to form a word. Whereas in the right cross set computer places a word by extending the word placed by human.

2.4 Technical Specification

In this technical specification section we will discuss about the project tools, programming technology and Integrated Development Environment (IDE) that used in this scrabble project. With the help of these tools our project can do easier and faster to develop the code and design with more efficiency.

2.4.1 Project Tools

To run the applications of our project, the below tools are must and stood install and store in our computer.

.NET 3.5

.NET is an acronym for “.” extendable Network Enable Technology. It is a technology or a platform. This was introduced by Microsoft. It will support nearly 24+ languages in that. It is the good technology. “.NET” language will support basic CLR (common language runtime). Microsoft .NET 3.5 consist of many several features building incrementally .Net 2.0, .Net 3.0 and includes .Net framework 2.0 and 3.0 service packs 1. In this consist of Windows forms applications [8].

Microsoft Visual Studio 2008

The visual studio is an IDE from Microsoft. It can support different programming languages, and it allows code editor and debugger to support any language. Visual studio consists of windows projects and website projects. Windows projects consist of windows forms, console, smart device, etc.., like that projects can do. Website projects consist of Website, Web Service, etc.., like that we can do [9]. Visual Studio 2008 will provide platform for developer. Default visual studio 2008 will support C# .NET and Vb .NET.

Dic.txt

It is a text document and consists of dictionary words of TW106. There is having 1,78,691 words in this text document. Each and every word is stored in a separate line. This file is to check the word in dictionary words after placing a word across the board. This text file is read by stream reader and put those words in list by using data structures of arrays concept, the words will be searched one by one. By using the GADDAG algorithm, the words are searched and place a word by the computer.

2.4.2 Programming Technologies

C# with Windows Forms

The programming language I am using in this project is C# language. The C# language using in windows forms application. Our project is done in windows forms, and then there is no server is required in our project. It will load the project in the client side.

3. System Design

Designing is the most important concept. Identifying the main blocks of the system and designing them by using tools. The design concepts are helpful for implementation purpose. Section 3.1 describes the requirements of the project. Section 3.2 describes the System Architecture.

3.1 Requirements

The output of our project should satisfy almost all requirements. Every project should consist of two types of requirements.

Functional requirements.

Non-Functional requirements.

1.Functional Requirements

Functional requirements define a set of inputs, behaviour, and output of a software system. The requirements may be calculations, data manipulation and processing some other specific functionalities of the system.

Some of the functional requirements are as follows:

The game logic should be implemented by indentified with the presentation.

There is a functionality to check the words that are in dictionary words before placing the word across the board.

Score calculations take place at each and every word placed on the board.

2.Non-Functional Requirements

Non-Functional Requirements are the requirements that are used to judge the operations of the system, rather than functional requirements. It is also called as quality of the system.

Some of non-functional requirements are as follows:

Quality: The end product of the scrabble game will be in good look.

Reliability: The windows should be able to manage errors and perform consistently.

Maintainability: The logic of the game should be done in well organised way. In future any functionality can be manipulated in the game.

Performance: The performance of windows should run as per the programme which should be made sure.

Understand ability: The design of the game should be user friendly

Some of the user requirements are define below:

Moving the tiles across the board.

Submitting the word.

Swapping the players.

Check the words in dictionary words.

Cancel the check words window.

Exit the game.

Moving the tiles across the boardThe above user requirements are shown in a use case diagram below.

Exit Game

Submitting the word

Cancel the Check Word window

Swapping the players

Check word in dictionary words

Figure 3.1: Use Case of Scrabble Game

3.2 System Architecture

System Architecture is a design and explains the structure or behaviour of system. In system architecture we can define system components or basic building blocks, will get a plan by which products using we can develop a system. Here we are using 2-tier architecture in our project based on our objectives and requirements. 2-tier architecture consists of GUI layer, logical layer, data layer.

Logical

Layer

Data (Dictionary)

Front

END

Figure 3.2: System Architecture

Let us see the components of system architecture:

Front end layer is a windows application, in which scrabble game is designed as an application.

The middle layer is the logical layer, which consist of game logic and presentation logic. It combines with the data layer and GADDAG algorithm and connected with the front end.

The third layer is the data layer, which the dictionary words are stored.

3.2.1 Front End

Front end layer is a windows forms application. As per the requirements of the user, the operations performed are:

Moving the tiles across the board.

Submitting the word.

Swapping the players.

Check words in dictionary.

Cancel the check words window.

Exit the game.

3.2.2 Back End

Back end layer is a data layer.

Dictionary words storage.

Back End

Dictionary words

Storage

Figure 3.3: Architecture of Back End

We will see in detail of Back End Architecture.

Dictionary words storage: Based on the requirement, we should able to store the dictionary words with the algorithm in the game.

3.2.3 Logical layer

Logical layer consist of two parts:

Game logic.

Logical Layer

Presentation logic.

Game Logic

Presentation Logic

Figure 3.4: Architecture of Logical Layer

We will see in detail of logical layer:

Game logic: Logic for the game will be implemented in this layer. The algorithm of the game is also implemented in game logic.

Presentation logic: The logic required for the functionality of the front end is implemented in this layer. Example design of the game form.

4. Implementation

In this section we are dealing with the implementation of several phases of design in scrabble. Below will we discuss of classes and their methods in detail. In section 4.1 we will know the system implementation. In section 4.1.1 we will know user interface of the game. In section 4.1.2 we will know the game logic concept by using the class diagram. In section 4.1.3 we will know the GADDAG algorithm concept by using the class diagram for it. In section 4.1.4 we use the concept of Check Words concept and the class diagram for it.

4.1 System Implementation

System Implementation is taken from system design. How the Scrabble designed is discussed in Section 3. Now the implementation of the scrabble will see in this. There are 4 parts that are to implement. They are:

4.1.1 User Interface

4.1.2 Game Logic

4.1.3 GADDAG

4.1.4 Check words

4.1.1 User Interface

The user interface of the project is main screen of the scrabble.

Figure 4.1: Main screen of scrabble

As soon as the scrabble game is opened, a form containing the game will be open. The logic for the game are shown in the below class diagram and methods are also explained briefly.

There are three classes being used in this project namely: Game, GADDAG, Check Word. The classes like GADDAG and Check Word are depending on the Game class. The below figure 4.2 shows the dependency of Game class. The GADDAG algorithm code and the Check Word code will use in the game. Thus the GADDAG class and Check Word class are depending on the Game class.

Figure 4.2: Dependency of Game class

4.1.2 Game Logic:

The game logic consists of how the logic of the game is implemented. Based on the logic the user can play the game. The game class are explained below by the methods which we are using with their functionality. The figure 4.3 shows the class diagram for Game class.

Figure 4.3: Class of Game

The methods in game class are explained in table 4.1

Method

Functionality

AddScore

Generates a score with a word in the ListViewItem whenever a word is placed on board by a human or computer.

AreTilesConnected

When a word is placed by a human, computer should place another word adjacent to it and vice versa.

btnDone_Click

Player clicks the done button after placing a word on the board and gets score after dictionary verification.

btnPass_Click

If a player is unable to form a word from the letters in rack, he clicks the pass button so that the opponent player gets a chance to play.

CheckExtraScore

Displays extra scoring cells on the board.

CheckLocation

When a letter is dragged from rack and if it is placed elsewhere other than the board it is carried back to its position in rack.

checkWordToolStripMenuItem_Click

A player can check the word with the backend dictionary before placing it on the board.

ColPlay

A player uses this method to place a word in a column.

DrawText

This method is used to d