Web Based Version Of A Scrabble Game Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

We present in this paper a web-based version of a Scrabble game, describing its architecture and some implementation details. This architecture makes possible a high degree of interactivity, so that the players perceive the game as being played in real-time. Furthermore, no client-side plug-in or applet is used. These properties are achieved by means of a carefully designed architecture that uses AJAX (Asynchronous JavaScript and XML) for data exchange. This architecture guarantees low load on the server, so complex computations relative to the game logic can be done in realtime.

Moreover, data structures and algorithms were designed to efficiently access a custom Galician dictionary, which supports the game functionalities. We show in this paper how this data structures and algorithms provide an efficient method to create a Scrabble move generation algorithm.

We also show how the combination of these with the architecture proposed provides a fully interactive web application that can handle complex calculations over a very large lexicon with real-time appearance.

1. Introduction

The growing importance of Internet and the World Wide Web has made it one of the most important forums to spread the culture and the language of a nation, to the point that the potential of a culture is known that is related with its presence in Internet. Young people are the most frequently users of the Internet, as well as being the future of any culture.

Therefore, e-entertainment applications (i.e. games through the Internet) must be developed to guarantee the presence of a culture in the World Wide Web.

Furthermore, the maturity of Internet users and the quality of connections and services available are increasing the demand of interactivity in web applications, not only between the user and the system, but also between the users themselves. However, the characteristics of traditional web applications prevent developers from building collaborative applications or games that require real-time interaction between the users [5]. This is due to two main reasons:

• Clients cannot exchange information. Connections in web applications are always established between a client and the server, but never between two clients.

• A web server cannot start data transfers. Web servers can never communicate the information received from one client to the others unless the clients explicitly request it.

Therefore, applications where users collaborate or interact with each other in real-time to perform a task have to be implemented using plug-ins or a similar type of software for the web browser that controls the exchange of messages between the users. The only alternative without this type of software is that each client requests frequent updates from the server to retrieve the data that has changed in any other client. However, if data changes frequently on the clients or the change has to be perceived as real-time, the load on the web server will be very high because many new pages will have to be created and sent constantly. This results in a limitation of the maximum number of users that can interact.

Nevertheless, this approach is better than the previous one in the sense that users do not have to install any plug-in, which is an insuperable restriction in application domains where users do not have the required expertise level. New techniques and technologies have been emerging during the Web 2.0 era. They can help in the development of collaborative web applications. We have developed at the Databases Laboratory of the University of A Coruña asoftware architecture specifically designed to simulate interactivity between users of a collaborative web application [4] using these new techniques. Users perceive their interaction as real-time, just like if they had a direct connection between them. This architecture has been used to implement a virtual version of the classic board game Trivial Pursuit with two important advantages over other applications of this type: it does not require players to install any software for the web browser, and a large number of games can be played simultaneously on an ordinary web server.

This paper presents a web-based version of the popular game Scrabble that has been developed using the same architecture. Furthermore, one of the main objectives in this work was the development of structures to efficiently store and manage a vocabulary for the game. These structures could be used in many other applications.

The rest of the paper is organized as follows. In Sect. 2 the rules of Scrabble.gz are described in order to show the level of interactivity that can be reached with this approach.

Then, in Sect. 3, we present a detailed description of the application architecture and some implementation details. This development allowed us to evaluate and compare our approach with respect to traditional approaches to web application development, which is presented in Sect. 4. Finally, Sect. 5 presents our conclusions and some ideas for future work.

SUMMARY

Appel and Jacobson1 presented a fast algorithm for generating every possible move in a given position in the game of Scrabble using a DAWG, a finite automaton derived from the trie of a large lexicon. This paper presents a faster algorithm that uses a GADDAG, a finite automaton that avoids the non-deterministic prefix generation of the DAWG algorithm by encoding a bidirectional path starting from each letter of each word in the lexicon. For a typical lexicon, the GADDAG is nearly five times larger than the DAWG, but generates moves more than twice as fast. This time/space trade-off is justified not only by the decreasing cost of computer memory, but also by the extensive use of move-generation in the analysis of board positions used by Gordon2 in the probabilistic search for the most appropriate play in a given position within realistic time constraints.

Appel and Jacobson1 presented a fast algorithm for generating every possible move given a set of tiles and a position in Scrabble (in this paper Scrabble refers to the SCRABBLE brand word game, a registered trade mark of Milton Bradley, a division of Hasbro, Inc.). Their algorithm was based on a large finite automaton derived from the trie3,4 of the entire lexicon. This large structure was called a directed acyclic word graph (DAWG).

Structures equivalent to a DAWG have been used to represent large lexicons for spell-checking, dictionaries, and thesauri.5±7 Although a left-to-right lexical represen-tation is well-suited for these applications, it is not the most efficient representation for generating Scrabble moves. This is because, in Scrabble, a word is played by `hooking' any of its letters onto the words already played on the board, not just the first letter.

The algorithm presented here uses a structure similar to a DAWG, called a GADDAG, that encodes a bidirectional path starting from each letter in each word in the lexicon. The minimized GADDAG for a large American English lexicon is approximately five times larger than the minimized DAWG for the same lexicon, but the algorithm generates moves more than twice as fast on average. This faster algorithm makes the construction of a program that plays Scrabble intelligently within realistic time constraints a more feasible project.

Bidirectional string processing is not a novel concept. One notable example is the Boyer±Moore string searching algorithm.8±10 In addition to moving left or right, this algorithm also sometimes skips several positions in searching for a pattern string within a target string.

AIM OF THE PROJECT

The DAWG algorithm is extremely fast. There would be little use for a faster algorithm if the highest scoring move was always the `best' one. Although a program that simply plays the highest scoring play will beat most people, it would not fare well against most tournament players. North American tournament Scrabble differs from the popular version in that games are always one-on-one, have a time limit of 25 minutes per side, and have a strict word challenge rule. When a play is challenged and is not in the official dictionary, OSPD2, 11 the play is removed, and the challenger gets to play next. Otherwise, the play stands and the challenger loses his/her turn. The most apparent characteristic of tournament play is the use of obscure words (e.g. XU, QAT and JAROVIZE). However, the inability of a program which knows every word and always plays the highest scoring one to win even half of its games against expert players indicates that strategy must be a significant component of competitive play.

Nevertheless, there would still be no need for a faster algorithm if expert strategy could be modeled effectively by easily computed heuristic functions. Modeling the strategy of Scrabble is made difficult by the presence of incomplete information. In particular, the opponent's rack and the next tiles to be drawn are unknown, but the previous moves make some possibilities more likely than others. Gordon2 compares the effectiveness of weighted heuristics and simulation for evaluating potential moves. Heuristics that weigh the known factors in the proportions that perform most effectively over a large random sample of games give an effective, but unintelligent, strategy. Simulating candidate moves in a random sample of plausible scenarios leads to a strategy that responds more appropriately to individual situations. Faster move generation facilitates the simulation of more candidate moves in more scenarios within competitive time constraints. Furthermore, in end game positions, where the opponent's rack can be deduced, faster move generation would make an exhaustive search for a winning line more feasible.

NON-DETERMINISM IN THE FAST ALGORITHM

Appel and Jacobson acknowledged that the major remaining source of inefficiency in their algorithm is the unconstrained generation of prefixes. Words can only be generated from left to right with a DAWG. Starting from each anchor square (a square on the board onto which a word could be hooked) the DAWG algorithm handles prefixes (letters before the anchor square) differently to suffixes (those on or after the anchor square). The DAWG algorithm builds every string shorter than a context-dependent length that can be composed from the given rack and is the prefix of at least one word in the lexicon. It then extends each such prefix into complete words as constrained by the board and the remaining tiles in the rack.

When each letter of a prefix is generated, the number of letters that will follow it is variable, so where it will fall on the board is unknown. The DAWG algorithm therefore only generates prefixes as long as the number of unconstrained squares left of an anchor square. Nevertheless, many prefixes are generated that have no chance of being completed, because the prefix cannot be completed with any of the remaining tiles in the rack, the prefix cannot be completed with the letter(s) on the board that the play must go through, or the only hookable letters were already consumed in building the prefix.

They suggest eliminating this non-determinism with a `two-way' DAWG. A literal interpretation of their proposal is consistent with their prediction that it would be a huge structure. The node for substring x could be merged with the node for substring y if and only if {(u,v) u uxv is a word}  {(u,v) u uyv is a word}, so minimization would be ineffective.

A MORE DETERMINISTIC ALGORITHM

A practical variation on a two-way DAWG would be the DAWG for the language L  {REV(x)ey u xy is a word and x is not empty}, where e is just a delimiter. This structure would be much smaller than a complete two-way DAWG and still avoid the non-deterministic generation of prefixes. Each word has as many representations as letters, so, before minimization, this structure would be approximately n times larger than an unminimized DAWG for the same lexicon, where n is the average length of a word.

Each word in the lexicon can be generated starting from each letter in that word by placing tiles leftward upon the board starting at an anchor square while traversing the corresponding arcs in the structure until e is encountered, and then placing tiles rightward from square to the right of the anchor square while still traversing corresponding arcs until acceptance. A backtracking, depth-first search12 for every possible path through the GADDAG given the rack of tiles and board constraints generates every legal move.

Being the reverse of the directed acyclic graph for prefixes followed by the directed acyclic graph for suffixes, it will be called a GADDAG. Reversing the prefixes allows them to be played just like suffixes, one tile at a time, moving away from anchor squares. The location of each tile in the prefix is known, so board constraints can be considered, eliminating unworkable prefixes as soon as possible. Requiring the prefix to be non-empty allows the first tile in the reverse of the prefix to be played directly on the anchor square. This immediately eliminates many otherwise feasible paths through the GADDAG.

The GADDAG algorithm for generating every possible move with a given rack from a given anchor square is presented in Figure 3 in the form of backtracking, recursive co-routines. Gen(0,NULL,RACK,INIT) is called, where INIT is an arc to the initial state of the GADDAG with a null letter set. The Gen procedure is independent of direction. It plays a letter only if it is allowed on the square, whether letters are being played leftward or rightward. In the GoOn procedure, the direction determines which side of the current word to concatenate the current letter to, and can be shifted just once, from leftward to rightward, when the e is encountered.

A GADDAG also allows a reduction in the number of anchor squares used. There is no need to generate plays from every other internal anchor square of a sequence of contiguous anchor squares (e.g. the square left or right of the B in Figure 2), since every play from a given anchor square would be generated from the adjacent anchor square either to the right (above) or to the left (below). In order to avoid generating the same move twice, the GADDAG algorithm was implemented with a parameter to prevent leftward movement to the previously used anchor square.

The GADDAG algorithm is still non-deterministic in that it runs into many dead-ends. Nevertheless, it requires fewer anchor squares, hits fewer dead-ends, and follows fewer arcs before detecting dead-ends than the DAWG algorithm.

Figure 3. The GADDAG move generation algorithm

Computing cross sets

Appel and Jacobson's DAWG implementation uses and maintains a structure for keeping track of which squares are potential anchor squares (horizontally and/or vertically), and for each such anchor square, the set of letters that can form valid crosswords (cross sets). Whenever a play is made, only the squares directly affected by the play need to be updated. The GADDAG implementation uses and maintains the same structure.

Computing a right cross set (i.e. the set of letters for the square to the right of a word or single letter) is easy with a DAWGÐstart in the initial state and follow the arcs associated with the letters of the word. Computing the left cross set of a word is equivalent to generating the set of one-letter prefixes, and thus exhibits the same non-determinism as prefix generation. For each letter of the alphabet, one must follow the arc for that letter from the initial state of the DAWG, and then follow the arcs associated with each letter of the word to see if they lead to acceptance.

A GADDAG supports the deterministic and simultaneous computation of left and right cross sets. Just start in the initial state and follow arcs for each letter in the word (reading from right to left). The left cross set is the letter set on the last arc and the right cross set is the letter set on the e arc from the state that the last arc led to.

There is one rare case where the computation of a cross set is not deterministic. When a square is left of one word and right of another, then one must follow one word through the GADDAG, and then for each letter of the alphabet, follow that letter and then the letters in the other word to see if they lead to acceptance. For example, if PA and ABLE were separated by just one square, this computation would allow a word to be played perpendicular to them if it placed an R or a Y between them.

2. Scrabble.gz

Scrabble.gz is a web-based version of the Scrabble board game for the Galician language. Adaptation of classic games like Scrabble, with great qualities as a pedagogic tool to increase language capabilities, is expected to be a goal in promotion of Galician language. One of our objectives in the development of this web version was that the application could be played on any web browser without having to download any applet or plug-in. We also tried to simulate the normal user interaction in real board game. Another of our main purposes was to develop a complete, efficient dictionary for the Galician language that could store a vocabulary and support complex queries that satisfied the needs of this game and those other applications that could possibly use it.

The original Scrabble board game consists in placing words, made up using tiles, on a 15x15 board. Tiles represent a character or digraph and have an associated score. The goal of the game is to obtain the best score from one's words, which must be placed crossing another word previously played. In his turn, a player can pass, change some of his tiles or play a word. Match finishes when a player uses all the tiles in his rack and there are no more remaining, or when nobody can play a word.

As well as these general rules, we will show also the most important differences between our web version of Scrabble and the original board game:

• Players have information about the state of the match, specifically score, number of tiles left, and last actions of all the participants. This helps the user focusing on the match.

• Players can talk during the match, using a chat window.

This simulates the verbal interaction between players. The sensation of real-time interaction relies mostly on this point and the preceding one.

• The computer automatically validates words played, using a reference dictionary of Galician accepted terms. Current application provides two dictionaries.

Players can access this dictionary during the match to check their words before playing them. The set of valid words is hence well known, so move refutation is not needed.

• Users can suggest new words to be added to the dictionary.

Move refutation, as understood in the classic game, is replaced by this possibility. Currently, suggestions are only allowed for the complete version of the dictionary, as the smaller one is supposed to be a stable reduced version.

• Players can require suggestions from the computer. They will obtain the best moves for them, sorted solely by their total score. Returning a set of words helps the player to select the one that fits his own purposes.

These suggestions imply a loss of points from the score of the turn to keep the match even. The real-time sensation relies here on the ability to find this set of moves in a short time.

• Users can play against the computer. The application will behave like a normal player in these matches, playing a good move in its turn. Efficiency in this calculation is needed to avoid long waits for the user while providing a good level machine player.

• The set of tiles and scores for each one are adapted to Galician. This adaptation was done by finding letters frequencies in a huge corpus, which was also the basis to create the main dictionary.

• Each player turn has a limited time. In the current application, it is set to 45 seconds. This value was empirically determined from the average time to play a word. Configuration of this parameter is very important to avoid long waits while giving the players time enough to move.

• The server keeps track of all the games played, storing information about matches won and points obtainedfor all users. Therefore, players can compete to win one game, but also to be the one with most games won, most points, or the best statistics.

3. Implementation

3.1. Interface design

Figure 1. Screenshot of the game

As we stated before, interactivity of the game was one of our main objectives in the development of the application. Hence, the design of the game page was done very carefully.

All extra features to the original game are shown clearly to ensure a better comprehension of how the game works. In addition, the most important information about the actions of the other players is always being updated so that the user knows perfectly the state of the match. Figure 1 shows a screenshot of the current user interface for the game page. The game page is divided in two main parts. On the one hand, elements needed for the normal game (i.e. the board or the player rack) are placed in the left hand of the screen. These elements are grouped together to make easier the interaction. The board state and the user rack are always updated, including highlighting of last tiles placed.

On the other hand, all other functionalities are placed on the right, grouped to be accessed quickly. Information about the match and about the other players is also updated regularly.

In order to help users to understand the enhancements done in our web-based version of the game, functionalities to request for suggestions or query the dictionary are placed in the central part of the screen, near to the board. The dictionary can be accessed by starting string, and looks like a list of words stored on the client. One more time, efficiency on the information exchange with the server allows a realtime interaction sensation. To provide the communication among players, a chat window is placed in the right part of the window. Communication is supposed to be done mostly out of one's turn, so updates of the chat window and other match information are done independently.

The layout of this interface is designed very carefully to help the player to focus in the match. Regular updates of the interface lead the users to feel like playing at home, around the same table, and chatting with the other players. Moreover, enhancements integrated in the user interface provide a more dynamic game, where players can obtain better solutions in a shorter time and some problems of the normal game (as move refutation) are carried off automatically.

3.2. System architecture

Architecture of traditional web applications follows one of these philosophies:

• Server-side applications. All processing is performed on the web server. Each client request implies creating and sending a complete web page to it. This architecture is not very scalable.

• Client-side applications. As much processing as possible is performed in the client. These applications are usually implemented by means of web browser plugins that have to be downloaded, or Java applets that require the Java Virtual Machine to be installed and

configured. This philosophy requires some level of expertise from the users, which limits its general use.

An intermediate approach uses scripts in the web pages so that the client-side has a certain amount of processing capabilities without having to install a plug-in or the Java Virtual

Machine. AJAX (Asynchronous JavaScript and XML,

see [2]) is a new philosophy based on this. It uses the XMLHttpRequest

API present in all browsers nowadays. This

API allows a web page to request information from the web server without blocking the user activity. The web server returns the information requested using short XML [6], which will be processed by some script function on the client to update the page state. This approach has many advantages. First, users perceive a higher response speed. They do not have to wait for an action to end before invoking another action because the data exchange is performed asynchronously and long operations do not block the user interface. Moreover, in traditional web applications each content update requires a complete reload of the web page, whereas in a web application

using AJAX the information in the XML message is used to redraw the appropriate section of the user interface. Additionally, the processing time in the server and the amount of information exchanged is smaller because the server does not have to create and transfer complete web pages. Hence, in AJAX-based web applications the remaining processing time and bandwidth can be used to handle a higher number of simultaneous requests.

The use of AJAX has been increased a lot in the last years, when many web applications have been adapted to work using this philosophy so that their user interface becomes more user-friendly. Because of this, a high number of tools have appeared around AJAX to make its usage easier.

One of these tools is Direct Web Remoting (DWR), an open source library that simplifies the use of AJAX encapsulating its requests with its own script code. Our application is based on this AJAX philosophy, using DWR to manage asynchronous requests. However, our game requires a high degree of interactivity, so we need to simulate information exchange between clients. The use of AJAX increases the efficiency of data exchange, but does not change the request-response model that is used in all web-based applications. To achieve this sensation of realtime interaction, clients periodically query the match state using AJAX requests, and update the user interface according to the information they receive about the match and the other players. Some client actions require extra information from the server, which is requested using the same method.

Figure 2. System architecture

Figure 2 presents a general view on the architecture of the application. Just like any web application, one can find two different parts: the server-side module and the client-side module. The first one is implemented using Java Server Pages (JSP), and the second one is implemented using JavaScript and Dynamic HTML. There is a part of the application that deals with functionality such as user registration or browsing statistics of the players, whose description

is out of the scope of this paper. Instead, we will focus on the description of the game control and simulation of real-time interactivity.

The server-side module keeps the state of all matches being played and processes client requests according to this state. Submission of words, requests for suggestions, and all the requests related to a proper turn action are only allowed to the user in turn. Some other requests are allowed at any time. Wrong or unsynchronized requests are discarded.

In this way, although most of the control is done on the client-side, the server-side can force some state changes to prevent a possible match lock, for instance, when a client falls down from a match. Server-side control of the matches was developed using a state machine that determines the valid actions for the player in turn and other information about the match.

The client-side module consists of a Dynamic HTML page with JavaScript code. Its operation is based on a JavaScript timer that requests the game state every few seconds and updates the user interface. When a user invokes actions on the user interface, the script code informs the server of the event and modifies the user interface with the information retrieved. This information depends on both the state of the match and the invocated action. As information is periodically synchronized, state control on the clientside works perfectly most of the time. Unsynchronized state changes that might lead to redundant or unsynchronized requests to the server will be quite unusual and will be corrected by the server-side. The time between updates has been empirically chosen to achieve a real-time perception of the game while keeping the low processing load on the server side.

3.3. Data structures and algorithms

Scrabble.gz, like other language-based games, requires an implementation of data structures and algorithms that grant a fast and flexible access to a big list of words. The efficiency of this access will allow our application to do the complex calculations needed in short time. This issue, along with the proposed system architecture, supports the real-time needs that are the main goal of the application. We will discuss in this section some details about these elements. The data structure used for the dictionary is a variant of a GADDAG directed acyclic graph shown in [3]. This is a minimized graph where words are stored in its paths. Each edge of the graph has an associated character, so a path to a final node represents a valid word. Minimization of equivalent states leads to a small structure which can be accessed easily as a normal word trie. The main difference between this graph and a normal word graph is that the vocabulary to be accepted is different from the one inserted in the dictionary.

We can see in the Figure 3 how for each word that should be accepted by the dictionary, the structure holds all of its rotations in a special way. The purpose of doing this is being able to start searching in any position of any word, thus being able to do complex queries efficiently.

This method of construction increases the size of the resulting structure, but we will see in further sections that spatialefficiency of this approach is really high, what makes this problem less important.

Figure 3. Graph structure. Variations for word "arts"

Our implementation is based on this directed acyclic word graph, stored in an array structure, but its design is adapted to ensure a high capacity while keeping the limited search complexity. Figure 4 shows this storage structure. Nodes and their leaving edges are stored consecutively, and edges for each node are lexicographically ordered. Each node and edge is stored in 32 bits, so the size of the array is O(|E| + |N|), where E represents the edges set and N the nodes set. Each node contains a bitmap of characters where bits set to 1 indicate an output edge for the character corresponding to this position. Furthermore, each edge contains the destination node's position in the array and a mark to indicate if the path to that node represents a valid word. Paths to valid words can be marked using just 1 bit, so 31 bits can be used for the array indexing. Thus, our implementation will be able to hold a huge, potentially unlimited, number of words. This is because we minimize on the fly our word graph during construction. Regularity of the language ensures that the growth of the structure will be sub linear in the number of words added.

Figure 4. Graph storage

As we noted, each node contains a bitmap where all possible characters must be coded. This means a limited number of characters can be introduced in our dictionary. However, this limitation has not been considered a problem for us because the number of different characters in our Galician dictionary is assured to be little enough. Hence, the only limitation to our dictionary is the amount of memory needed to build it up from a list of words. We will show later how compression of the structure keeps its size in considerably small values, thus allowing the construction of a dictionary from a big lexicon in a common computer.

The construction method of the structure is an adaptation of the one shown in [1], so we will refer to this article for more details. However, we want to note that this method keeps a permanently minimized uncompressed word graph in memory. This graph is compressed during storage of the final structure. The construction can be done in O(n). The result of this construction is a really small structure that grants efficient O(1) time for single word search and

supports complex queries. In the current application there are two dictionaries, which contain the set of roots or basic Galician words, and a complete set of words and all their valid variations. The second one contains over 11 million terms.

The data structure we designed can be accessed both to retrieve single words or to find some patterns. We have implemented generic algorithms that allow single-word search and search by substrings. Single-word retrieval can be done by searching for a path in the graph corresponding to any of the rotations of the word. Thus, every search for existence of a word can be processed by crossing as many edges as characters it contains. In our vocabulary, composed of real words of strongly limited length, this shall be considered O(1) complexity. Requests for a set of words containing a substring can be done by searching for a particular rotation of the substring and decoding the resulting subgraph, which contains exactly the requested set. Searching the subgraph is immediate, and retrieval time is proportional to the number of words. These algorithms are combined with the Scrabble.gz game restrictions to provide an efficient method to search for available moves in a match. Other specific algorithms were also developed to process other queries required by the application.

4. Evaluation

The application we have presented in this paper is currently in the production phase, so we cannot show here real usage information. However, it has been thoroughly tested for efficiency and usability. Several thousand games were played just to test and adjust the interface, in order to increase the real-time game perception of the users. Some parameters of the application, like the time limit for each turn, have been also adjusted based on results from this tests. The game can currently be played at http://naron.dc.fi.udc.es/scrabble.gz.

Assuming that the communication is a solved problem, the dictionary becomes the application's bottleneck. We have developed a compact data structure to keep the dictionary

in main memory. The dictionary stores 11 million words in 12 MB, one tenth the size of the raw word list. Efficiency of queries against this kind of structures has been proved. The only queries that imply a hard computation are those related to move generation. This procedure is only

needed in games against the computer and when users require help from the computer. During the tests of the move generation algorithm (performed with the application installed in an Intel Core 2 Duo 2.14 GHz, 2 GB RAM) our algorithm obtained the set of all valid moves in an average time of 15 ms, and the computation time was quite stable during all the game. If we consider that this kind of requests are actually unusual in our game, the cost of computing the

request can be perfectly assumed by a normal web server. The processing time is really slow compared to the network latency, so users will never loose the real-time perception. In fact, speed of move generation calculations forced us to slow down the computer's moves to simulate the evaluation time of a real user.

5. Conclusions and future work

We have presented in this paper the architecture and some implementation details of a web application that simulates a Scrabble game where users can play in real-time. This was achieved without using any plug-in or applet, which means that the game can be played without the common problems associated to the installation of these components.

We have described how the AJAX philosophy is used in the implementation for the data exchange and how a state-machine in the server is used to synchronize the interaction.

We have selected two Galician language dictionaries and we have designed the data structures such to represent them, in a way that other applications that need to work with Galician

words may use them. In fact, most applications that need to work with words (of any language) could use these structures. Completeness of the current dictionary, with several millions of terms, and extensibility of the algorithms to look across it, make of it a very useful development. The

architecture of the application allows real-time interaction with the dictionary, including complex queries. Integration of the dictionary with this kind of architecture makes it a powerful tool for its use, for instance, in education, increasing children's language capabilities.

Our lines of future work include an improvement of the game that will allow suggestions to the users to be restricted to a subset of the most common words. This would make the games more understandable, avoiding results that involve complex or very unusual words. Another future development could be the customization of the algorithm for move generation to include heuristics. The current selection method takes the best-scored word, which is enough in most

cases, but advanced players take advantage of strategies that could surpass the program's abilities. A different line of future work is the application of the developed dictionary in some other educational web-based systems, following the same philosophy and purposes exposed here. Finally, we plan on updating the communication protocol of the architecture to support new Reverse AJAX functionalities. Reverse AJAX includes a mechanism for pushing server data

back to the browser and could improve a lot the efficiency of our architecture.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.