This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Computer games are important elements that have significantly approbated our culture, being a primary driving force for social and economic development. One of the most popular and most interesting of these games is Scrabble, a board game in which players compete by forming words on a common 15-by-15 grid.
In Artificial Intelligence (AI) and Computer Games research community, solving games with perfect information, whereby a player has available the information to determine all of the possible game details, such as Chess, checkers and Othello have been predominantly key point of focus. However, with recent developments and studies in AI, games research has drifted into imperfect information, i.e. games like Scrabble, where certain relevant details are withheld from the players. Thus, we take an in-depth look at how Artificial Intelligence is applied in imperfect information game programming, being one of its most preferred uses. As such, NigerScrab, a brand of the popular scrabble game is used as our test-bed in this research.
Accordingly, we studied research efforts that have been made in Scrabble community and discovered ways by which we can improve the game strength. Thus we devised a probabilistic and heuristics model that could be used to implement NigerScrab, a specific variant of Scrabble Game. Performance evaluation NigerScrab revealed that the strength of NigerScrab has actually improved and that the game has increased player's experience, having an overall average point per turn of 26.8 using a dictionary of approximately 80,000 words (Folajimi and Chiemeke, 2010).
Scrabble is a popular crosswords game played and embraced by millions of fans all over the world. Contestants play the game by forming words on a board of 15 x 15 squares, just like in crossword puzzles. Each player at any point in time has a rack containing seven tiles that are randomly picked from a bag that initially contains 100 tiles. To achieve high scoring words, the player has use strategies that strike a balance between maximising his score and managing his tiles for the purpose of achieving high scores in future. Scrabble is clearly a game of imperfect information since a player neither has knowledge of what is contained in the opponent's tiles nor able to identify what tiles he would select next from the bag. It is important to note that Scrabble, unlike chess or checkers, is a proprietary game, the rights of which are owned by Hasbro, Inc. Accordingly, we fully acknowledge the bases of NigerScrab on Scrabble and we shall only use it for academic purposes, being strictly an academic endeavor and not for any commercial purposes.
NigerScrab is a scrabble-like game that follows closely the rules of Scrabble by looking at millions of possible moves each turn, guided by probability with heuristics for an evaluation function that consider a large number of conditional circumstances which it uses to decide on which move to make out of the available numerous options. These considerations are so massive that they cannot all be completely mentioned in this work but more comprehensive details are contained in the complete thesis.
The task of writing a computer program that plays a computer game against a human opponent requires methods that are intelligent, (or at least methods that appear intelligent), as justified in Russell and Norvig (2007) and also discussed in Erik and Robert (1992), and Crawford (1984). The essence is that, we should be able to approximate the model of the game world and the behavior of the opponents within the game engine so as to create actions that will automatically reflect realistic contests and challenge the human opponent into serious mental engagement in the process. Because of the strategy behind Scrabble, playing the highest scoring word is not always the best move to make. Therefore, to create an effective computer opponent, the needed rudiments are algorithms by which we can instruct the computer on the intrigues of the game.
The past successes of AI researchers at scrabble games, the methodologies and techniques used have revealed encompassing values of diverged degree and procedures, such as finding the best word from a seven-tile rack, or computing the most eminent scoring play available from a given game situation have motivated investigations into the workings of these programs, in which research has clearly revealed that the "brute force" algorithms assumed that the highest-scoring play was always the best, and is not in the interest of Scrabble game as a whole (Richards M and Amir E. 2007, Sheppard 1999, Edley 1997). Even though a computer player can freely consult a database of all legal words, the best intrigue is not always by playing the word that gives the highest score, and programming a computer to play well requires knowledge of a number of much more subtle methods. In this regard, our focus is on how we can use Artificial Intelligence techniques to control the behaviour of computer player in a computer versus human Scrabble game-playing program. Thus, we take an in-depth look at how Artificial Intelligence is applied in game programming, being one of its most favoured uses.
It is noteworthy that in the past, researchers have devoted a lot of time and efforts to perfect information board games like chess, Othello and checkers and as such, these games have been developed to a level at which they can contend with, and defeat world rank champions. However, one major feature common to these games is that they their expertise can be achieved by game-theoretic approaches which is merely an implementation of how brute-force search can be applied in perfect information games. In our study, we are interested in how computer games in which brute-force search may not work, can give us new ideas in artificial intelligence. This potential is more common in games in which search is not the primary key to expertise, but rather, ability to simulate real-world decision-making systems that require intelligent or expert actions. Such systems may have features like imperfect information, multiple competing agents, agent modelling, unreliable information etc, which are not exhibited by brute-search force games, or they are merely utilized in minimal ways. Our interest is to inquire into a computer game that can exhibit these features to certain extent; Scrabble is just ideal for this purpose.
To this end, we present efforts that have been made so far in discovering new ideas that can lead us into modeling and simulating a design that uses AI techniques for the implementation of a variant of the popular scrabbleTM game, NigerScrab which can make use of AI tools at its disposal to manipulate all aspects of game-play so well that it is able to defeat competing human opponents. This work is also a justification of the fact that Scrabble is an ideal area to be researched upon in connection with AI systems, the success of which is of enormous relevance to gaming and AI community at large. The current trend in Scrabble research, the efforts being made to improve the game and a report of research openings in this regard are adequately discussed in this thesis. Having identified some problems that may arise from current techniques, and upon affirmation that the brute force technique is not the best approach to Scrabble, we discover the models that can be used to improve computer player's behavior in making decisions about what tiles to play based on the fact that the highest-scoring tiles combination is not always the best. This led us to a model and design that is capable of playing intelligently with human opponents using probabilistic and heuristic techniques, while laying particular emphasis on the evaluation function, simulation and statistical look-ahead.
1.2 BACKGROUND OF THE STUDY
Russel et al (2003) observed Scrabble as a stochastic partially observable game. This is a feature distinguishes Scrabble from games like chess and go, where both players can make decisions based on full knowledge of the state of the game. Littmann (1996) suggests that such stochastic games of imperfect information can be modelled formally by partially observable Markov decision processes (POMDPs). However, at the beginning of scrabble game play, a player can possibly hold as many as over four million possible different combinations of tiles in different racks, though this probability reduces as the number of tiles left in the bag decreases (Richards and Amir 2007) . This makes it difficult to model the game using PODMP.
Scrabble's obvious partial observability makes it comparable to games like poker and bridge, in which researchers have made remarkable achievements in controlling the hidden information and creating computer agents that can compete with intermediate-level human players (Billings et al., 2002, Ginsberg, 1999). Although it is now possible for computers to play better than humans, as affirmed by Sheppard (2002), who insisted that championship-level play is already dominated by computer Scrabble agents, Scrabble is not yet a solved game and the best existing computer Scrabble agents can still be modelled to play better games including knowledge about the unseen letters on the opponent's rack into their decision-making processes. Schaeffer (2009) also noted that improvements in the handling of hidden information in Scrabble could also shed insight into more strategically complex partially observable games such as poker. Furthermore, advanced computer Scrabble agents are of immense benefit to expert human Scrabble players because humans can depend on intelligent computer Scrabble programs for playing better games by studying previous games and analysing how suboptimal decisions were made. Billings et al (2002) indicated that opponent modelling has been one of the strategies that have been successfully applied to games of imperfect information. Opponent modelling involves strategies to identify what game might be contained in opponents' racks and how they might improve their play, based on previous games.
Research has indicated that methods such as alpha-beta search that were successful in other games like checkers have proven more or less useless for Scrabble and its likes such as GO and Poker. In Scrabble and Poker, opponent modeling plays significant role while in most other games opponent modeling can only be of little or no use. It is clear that many programmers choose expert knowledge in some form or other instead of searching even though processing capabilities of the hardware become more and more impressive. Machine learning in general and temporal difference learning and opponent modeling is used more and more often. Generally, researchers are no longer comfortable with brute force approaches and prefer more subtle and intelligent ones instead. It is no longer a tale that computers of today are not just becoming faster or lighter, but they are actually becoming more intelligent in every sense of the word.
1.3 JUSTIFICATION FOR RESEARCH
Although it is now possible for computers to play better than humans, as demonstrated by Sheppard (2002), Scrabble is not yet a solved game and the best existing computer Scrabble agents can still be modelled to play better games including knowledge about the unseen letters on the opponent's rack into their decision-making processes (Richards and Amir, 2007).
A number of authors have supported the fact that Scrabble is a fertile area still open for Artificial Intelligence research (Ballard 1993, Allis 1994, Gordon 1994). Billings et al (2002) and Schaeffer (2009) remarked that enhancements of how hidden information are handled in Scrabble will possibly give an understanding of more strategically complex partially observable games such as poker (Schaeffer 2009). Furthermore, advanced computer Scrabble agents are of immense benefit to expert human Scrabble players because humans can depend on intelligent computer Scrabble programs for playing better games by studying previous games and analysing how suboptimal decisions were made.
Summarily, the following rationales further substantiate why the game of scrabble is a suitable domain for computer representation and supports the reasons why further research should be done in it.
Scrabble is not yet a solved game, hence continuing research in this kind of games could lead to solving them.
If research is continued in a game like scrabble, new ideas which can be practical in weaker games can emerge and these ideas may even be used in Mathematics and Economics, as suggested in the work of Fraenkel (1996).
Researchers are always rationally challenged to have the strongest program in their domains, especially with the Computer Olympiads programs that always compete against each other. This will make researchers to work harder at making a champion out of their programs.
Our scrabble program which is based on Artificial Intelligence could be used by a player to train his skills further for improved performance in the game of scrabble.
1.3.1 Why Scrabble?
Scrabble is a game that significantly demonstrates our research areas of interest (Chiemeke and Folajimi 2008). So far, the primary focus of games researchers has been placed on algorithms to solve games with perfect information. As a result, high-performance systems have been developed for games such as chess, Othello, and checkers. In many of these games, high performance can be achieved by brute-force search. Recently, attention has been given to games with imperfect information, such as bridge poker, and Scrabble, where searching seems not to be the key to success. Since these games offer different algorithmic and conceptual challenges, the successful development of a program capable of playing them well may provide solutions to open problems in computer science.
Scrabble is a game that has several features which make it attractive for AI research. Fistly, there are several factors in determining the score of a move. The computer must build a word using high-scoring letters, place it at a valid location, maximize the value of letters using the various multipliers, etc. Apart from being a strategy game of chance, scrabble is a popular example of game of imperfect information in which a lot of Artificial Intelligence researchers and fanatics have had significance interests in Scrabble for many years. The game is especially interesting to implement because it has an element of randomness and can be broken down into two fundamentally different phases from a computer's point of view. The first phase starts at the beginning of the game until when last tile in the bag is drawn. During this phase, it is not known what the other players' tiles are, At the later phase, known as endgame, when the last tile is drawn and the bag is empty, the computer can deduce from the overall letter distribution what letters must be on the other players' racks.
Additionally, there are several other features of scrabble which make it an attractive domain for AI research. Other features include imperfect information, multiple competing agents, risk management, opponent modeling, deception, and dealing with unreliable information. These characteristics are also present in many real-world applications that require rational behavior and are summarized below:
Imperfect information: This implies that a choice must be made from a set of actions without complete knowledge. The relative desirability of each action depends on the state of the world, but the agent does not know exactly which state prevails. In Scrabble, a player does not know the opponents' tiles. Without knowing the complete state of the world, how can the player find which actions are, ``optimal'', in some sense?
Multiple competing agents: Having multiple competing agents exponentially increases the complexity of the computations required to play Scrabble by enlarging the game tree, hence the need for more intensive research in this area.
Risk management: This requires making a decision to gain a profit while considering how much one can afford to lose. Making a good decision based on the evidence available and ``cost-benefit'' considerations is a skill required in many real-world activities. For instance, a player can estimate the probable tiles the opponents might have in their racks based on the tiles that are already played on the board.
Opponent modeling: This involves identifying patterns in the opponents' play and exploiting any weaknesses in their strategy. For example, opponent modeling is extensively applied in political campaigns. In Scrabble, it can be done by observing the opponents' playing habits, and determining likely probability distributions for their tiles. If a player can predict the opponents' actions, then this player will be capable of making much better decisions.
Deception and the ability to deal with undependable information are traits of a strong Scrabble player. In fact, these activities are also necessary in real-world situations. For example, assume one wants to acquire a used car. How much shall one believe from all the wonders the salesman says about the car? How can one get a reduction on the price of the car? Good Scrabble players have to be unpredictable by bluffing and varying their playing style, and must also be able to deal with their opponents' deceptive plays. For example, if a player is known to play only the highest score possible each time, without giving consideration to tiles that are left in the bag (a predictable player), the opponents are likely to fold in such cases, he may occasionally play tiles with lower scores, giving the impression that he does not have any high score tile. This player will either profit from a successful bluff, or will implant doubt that will result in greater scores for high values. Hence, it is necessary to mislead the opponents by letting them know that an occasional play of smaller values is possible, even with high values in the rack.
It is no longer a tale that today's machines are not just becoming faster but they are actually becoming more intelligent in every sense of the word. Players are seriously looking for these characteristics that can encourage them to see the computer as a realistic opponent. The research into board and card games is, in some sense, throughout the times past, motivated because these gainsays were arousing a lot of attention at the beginning of the computing age. The early efforts of Shannon, Samuel, Turing, Allan Newell, Herbert Simon, and others have brought forth appreciable interest in researching computer performance at games (Schaeffer et al, 2002). For many reasons, we are also motivated to join this crew and embark on a related research, which shall be an addition to knowledgewe. We are thus motivated to contribute our quota into the Artificial Intelligence and Games Community through a popular game like scrabble. As a result, we list below some of the motivating factors that impel our absorption of this research.
Games are fascinating, thrilling and exhilarating, and the idea of conducting research on the computer version of such a popular and world-known game is fascinating.
Conducting a research on the intelligence behind a computer program that can defeat a human player that declares himself champion by beating a fellow human is an interesting idea. Watching people get excited as they play with such a computer agent, and understanding the Science and technology behind the game makes us proud.
Putting so many resources to conduct an in-depth research of this nature is a challenging initiative that gives an opportunity to improve existing knowledge in Artificial Intelligence and thus gives us recognition in the AI community.
As immense fanatic of the game of scrabble, we feel strongly motivated to join the community of scrabble researchers and find ways by which the game can be made more fun and stronger.
1.5 AIM AND OBJECTIVES
Scrabble is a well-liked game all over the world played by two to four players. In this research, we shall consider a two player game; one human and the other an intelligent machine, courtesy of our Artificial Intelligence. The essence is to make the computer engage human players in skilful tactics that will eventually make the human a better player in the game of scrabble.
As aforementioned and would further be explained later, the way by which human players find high-scores is different from the programming problem of generating them. The aim of this research is to take an in-depth look at existing AI methods that mimic human cognitive methods of playing strategy games to obtain high scores, making use of Scrabble as out test-bed and propose an improved model which shall take us to implementing a game of Scrabble, coined NigerScrab. To achieve our aim, the overall objectives are thus:
To study specific features of Scrabble which makes it an attractive domain for AI research
To conduct an in-depth research on AI efforts at game-playing programs and extend the development of the basic methods that have earlier been used in AI-based designs, to the making of an intelligent Scrabble game.
To identify some problems with previous methods and suggest AI strategies that can further enhance and improve machine versus human game play in Scrabble.
To propose an improved model for computer actions that will lead to a winning goal using probabilistic and heuristics techniques.
To develop NigerScrab, an intelligent computer program that is capable of comfortably defeating human opponents in a computer-human contest.
To ascertain that our algorithms have indeed improved the game experience through in-depth analysis to evaluate its performance.
To substantiate the fact that NigerScrab is indeed a strong engine by compiling statistical information about NigerScrab games played against human opponents and compare these results with other existing Scrabble engines.
1.6 STATEMENT of THE PROBLEM
Research studies have shown that consumer expectations are extremely high and players are looking for new experiences which are substantially beyond what they've enjoyed in the past. (Rabin 2006). They are longing for challenges that would engage them in serious thinking before they can overcome. This may not be possible unless they are faced with more skilled opponents. Playing with intelligent program creates a grand challenge to skilled players since it engages them in very serious thinking if they must overcome the machine. In this context, the problem of making the game design and Artificial Intelligence work hand-in-hand toward creating completely new game-playing experiences is a huge challenge, as noted by Rabin (2006), because it requires the game designer to understand what is possible with AI and to closely work with the AI programmer.
Though game playing research has traditionally focussed mainly on games like chess, checkers, backgammon, and Othello programs that are capable of defeating the best human players (Billings et al 2002), subsequently benefitting the Artificial Intelligence community as a result of the positive publicity generated by these games and resulting in many years of research that have produced some powerful techniques, mostly geared at the efficient traversal of large game trees and some notable victories; humans have been surpassed by programs in games such as checkers (Schaeffer, 1997) and Othello (Buro, 1997), while other games such as Connect-4 (Uiterwijk, van den Herik and Allis 1989, Nine Men's Morris (Gasser, 1990), and Go-Moku (Aliis 1994) have even been solved.
With more inscrutable research into computer Games, researchers started to realize that the techniques that drive these programs had been more or less exhausted. However, these methods may also be of little use in other classes of when it comes to constructing programs that can play on par with the strongest hurnans. These classes include the imperfect information games, where not all of the information is available to each player, or stochastic games where the player's options are partially determined by chance. The branching factor of these games are so large that traditional methods like brute force tree search algorithms are impracticable. The problem of dealing with imperfect information and stochastic feature of Scrabble is the main reason that solving Scrabble programs has lagged behind the advances in perfect information games. More importantly, this is also the reason why this game promises greater potential research benefits.
Table 1.1 shows the position of Scrabble as compared with other popular board games. The table indicates that Scrabble has attained over-champion performance, according to the 1990 prediction for the year 2000 concerning the expected playing strength of computer programs (Jaap et al 2002). Scrabble has attained over-champion level as predicted but the game is yet to be solved and we believe that there is a strong need to do further research on it.
Table 1.1: Predicted strengths for the Computer Olympiad in the year 2000
Solved or cracked
Nine Men's Morris
Source: Jaap et al, 2002
The past successes of AI researchers at scrabble games, the methodologies and techniques used have revealed notable results, such as giving the best word from a seven-tile rack, or computing the highest-scoring play available from a given game are not in the interest of Scrabble game as a whole and lead us to the following statement of the problem that incites this research and impels the design of NigerScrab:
"Brute force" algorithms assume that the highest-scoring play is always the best, and does not constitute the best action (play) in a Scrabble turn, given a game situation
1.7 RESEARCH QUESTIONS
Games raise the question of whether computers can make good decisions by estimating the present and possible future situations. If it is impossible for computers to solve decision-making problems in games domains where the rules are fixed, then how can we be sure that they can make good decisions in more complex domains where rules are ill-defined, or there are high levels of uncertainty? In such an instance, what then is the best action given a game situation?
To address these problems, this research shall further seek to find solution to the following research questions:
What are the existing efforts in making a computer Scrabble program defeat human opponents in game play?
To what extent has Artificial Intelligence techniques be used in the game of scrabble
Which techniques are best suited for improving the strength of the machine in a computer versus human game play of Scrabble?
How can we implement a workable Scrabble engine using improved techniques and evaluate the workability of the improved engine?
Can the newly identified techniques actually help in improving the strength of the game engine?
A number of efforts are expended to achieve these. However, for the purpose of this research, we lay particular emphasis on the move generation, evaluation function, simulation and statistical look-ahead. How these methods are employed, and the justifications of using them are clearly revealed in subsequent chapters.
1.8 SIGNIFICANCE OF THE STUDY
In recent times, we observed that role-playing, adventure, and sport games have become progressively more popular domains for AI research. This is partly because these games propose new challenges and partly because there are more prospects in them in the area of generating more resources, financially and otherwise for the researcher. No matter what is the motive, games will continue to linger as an interesting field for AI research in times to come.
Games is a suitable domain for supporting experimentation in different fields of computer science like algorithms, data structures, machine learning, knowledge engineering, tree search, and reasoning. They are representation of real world situations, in which hostile agents compete to reduce each other's drive. Thus, they can be used to design and analyze situations with multiple interacting agents having competing goals. For this reason, if a method solves a game successfully, it may be applied to solve problems in other areas. This is justifiable by the statement of Von Neumann and Morgenstern (1944), that a study of ``games of strategy'' is required in order to develop a theory for the foundations of economics and for the main mechanisms of social organization, because games are analogous to a variety of behaviors and situations that occur in these two areas. As a matter of fact, games are already used to model certain economic problems. (Zyda, 2005)
Additionally, improving a program to play a strategic game like scrabble shall involve the application of theoretical concepts to practical situations. Programs that implement different theories can be played against each other to provide a comparison of the effectiveness of these theories in a practical domain. Therefore, NigerScrab can be used as an experimental environment to obtain supporting or refuting evidence for new ideas, and to stimulate discussion on different approaches to solve a particular problem
1.9 RESEARCH CONTRIBUTIONS
Scrabble is already at over champion level as predicted in the year 2000 and indicated on table 1.3 but the game is not yet solved, thus there is need to conduct more research to into the possibility of solving this game. Heuristics and probabilistic functions are interesting objects of research in AI that has good practical applications to game playing. Therefore, in studying how AI techniques can be used to improve game-play in the game of scrabble, we focus on heuristics and probabilistic techniques in the field of Artificial Intelligence and how these techniques can be used improve the performance of Scrabble programs. Our scrabble agent, NigerScrab is used as test bed for this research.
Listed below are the contributions of the thesis towards the discovery of workable solutions to improving the strength of Scrabble engine:
Formulation of a model for evaluation function for move generation in a turn of Scrabble game using probabistic and heuristics techniques.
Improvement of the move generation algorithm by changing the termination condition for finding a legal move, in the generation of suffixes as published by Appel and Jacobson (1988).
Development of architecture for evaluating the rack contents and generating the best move out of the available options when it is computer turn.
Design and development of an extensible infrastructure for a computer application, coined NigerScrab, that allows a computer to challenge human being in scrabble contest as proven in our analysis.
Experimental analysis to validate the fact that the implemented model has led to a game pattern of play that exhibit intelligent features with demonstrated ability to defeat casual human players and engage strong human players in challenging contests.
making the basis for future work of other Scrabble engines, through additional models and strategies suggested in this work.
Every study, no matter how well it is conducted, has one limitation or the other. In the case of this research, we encounter a number of challenges though we were able to work around a good number of them. However, the following limitations were prominent in the course of the research:
Lack of detailed technical evaluation of computer Scrabble methods for many aspects of Scrabble programming was a critical factor that gave us some difficulties in adjudging our evaluation.
Most scrabble bots research encountered in our research were privately published play-finders and fortune seekers whose comprehensive architecture are not made publicly available. As such this limited our ability to evaluate the rudiments of most of the Scrabble engines we discovered and also made it a little difficult to do qualitative study with the literature that would otherwise have been made publicly available.
It was difficult for us to generalize the results to people with respect to situations and conceptualizations of the parameters. In the human side of the experiments; attaining larger and more varied test groups as play-testers and being able to define specifically what they are looking for, in order to hold some level of standardization was difficult. Sometimes, personal perception of individual play-testers was actually different from the truth because the descriptions of their own playing strength were actually inaccurate. This also complicated our ability to adjudge the strength of play-testers based on personal perception.
Below are some Scrabble terminologies, majority of which were provided courtesy of Hasbro (www.hasbro.com) and http://www.reocities.com/, as well as other terms used generally in this thesis
Bingo (plural bingos): A play using all seven tiles on the rack simultaneously that scores a bonus of fifty points in addition to the regular score of the word or words played.
Bonus Play: The First print usage of this word was by Mike Senkiewicz. Consequently, when Bingo is used as a verb, it implies playing all seven tiles from the rack on a single play. (First verb usage in print was by John Turner.)
Letterati: Collective name for club and tournament Scrabble® Crossword Game players.
OWL: The Official Tournament and Club Word List.
OWL2: The Official Tournament and Club Word List, Second Edition.
Blocking: The act of playing a word on the board that stops the opponent from making a potentially large score. It also refers to the act of playing words that make it harder for either player to score many points.
Bluffing: The act of deliberately playing a phoney word. This is completely ethical and is a weapon used by many experts, even against other experts.
Challenge : An opponent calls "CHALLENGE" when s/he thinks a play is not acceptable (i.e. not in the OWL or Merriam-Webster Collegiate Dictionary, Eleventh Edition). A Word Judge is called to verify which words are acceptable or not. Whenever there is a challenge, someone loses exactly one turn.
Closed Board: The opposite of an open board: when there are few places to play either bingos or other high-scoring plays.
Double-Double: When a player makes a play with letters that cover two Double-Word Squares. The bonus for covering two DWSs one play: quadruple the sum of the value of the letters of the "Double-Double" word. The sum should include that extra values earned form any DLS covered that turn only.
Endgame : The portion of a SCRABBLE game when there are less than seven tiles left to draw from the bag.
Exchanging Tiles: Instead of playing a word on the board, the player may use his/her turn to exchange any number of tiles in the rack for new tiles. These are drawn from the bag, as long as there are at least 7 tiles in the bag.
Hook Letter : A letter that will spell a new word when it is played with in the front of or at the end of a word already on the board. Example: With HARD on the board, the letter Y is a hook letter since HARDY is acceptable. Likewise, the letter C can be "hooked: since CHARD is acceptable.
Hot Spots : These are either specific squares or areas on the board that have excellent bonus-scoring opportunities. Players will do well to identify these areas before looking for words on their rack. Example: Triple Letter Squares or Double-Word Squares adjacent to vowels; a single letter placed between two Triple Word Squares; words that take a variety of hook letters (i.e. ARE, ON, CARE).
Leave: The leave is the group of tiles left on a player's rack after making a play and before drawing new tiles.
Open Board : An arrangement of words on the SCRABBLE® game board is said to be "open" when there are many places to play either bingos or other high-scoring words.
OSPD4: The Official SCRABBLE Players Dictionary, Fourth Edition.\
OWL: Since March 1998 the Official Tournament and Club Word List (OWL) published by Merriam-Webster, Inc.) was the official word source for all sanctioned NSA Clubs and Tournaments. As of March 1, 2006 the 2nd Edition is the official word source.
Parallel Play: A word played parallel to another word. Example: With MAR on the board, LATE is a parallel play M A R L A T E
Passing : A player may pass his/her turn by not exchanging tiles and not making a play on the board. The player scores zero and says "Pass!" and starts opponent's timer. It is now opponent's turn. Note that when there are 6 consecutive scores of zero in a game, the game is finished.
Phoney : Any unacceptable word. An unacceptable word is one that is not found in the OWL. Or, if it has more than nine letters and the word is not found in the Merriam Webster's Collegiate Dictionary, Eleventh Edition. If a phoney is not challenged when it's played, however, it will stay on the board for the remainder of the game.
Power Tiles : There are ten power tiles. They are the two blanks, the four Ss and the J, Q, X and Z.
Rack Balance/ Balancing your Rack : Making a play that allows you to save the letters on your rack that will most likely help you score well next turn. This often means leaving an equal number of vowels and consonants.
Rack Management : Good "Rack Management" is the policy of managing your leave each turn to be as flexible as possible. In this case "flexible" means your leave will combine with as many draws as possible to form seven-letter racks that score well.
Rating : For every sanctioned National SCRABBLE Association tournament a new rating is computed for each of the contestants. The rating represents how well an entrant is playing in relation to other players. The higher the rating, the more skillful the player. Ratings currently range from 400-2100.
Rounds : In club or tournament play, one game is one round. There are five or six rounds (games) per day at most tournaments.
Simulation: Using a specific computer program that can play out positions thousands of times very quickly
Spread: The difference between the winning and losing score of a game. Example: If the score of a game is 350-280, then the spread is +70pt for the winner and -70pt for the loser.
Tracking : The process of keeping rack of the letters played on the board. This can give the astute player an advantage as the game progresses. Careful trackers can deduce opponent's rack after there are no letters left to draw. By tracking the player can often block opponent's best plays or set high-scoring plays that an opponent can't block. Players are allowed to play with their own Preprinted Tracking Sheet alongside their Score Sheet. See " PREPRINTED TRACKING SHEET".
Turnover : Players are going for "turnover" when they play as many tiles as possible in order to draw as many new tiles as possible.
1.13 THESIS OUTLINE
The structure of this thesis is as follows:
Chapter one : Introduction and Background Information, presenting the research motivation, objective, problem statement and justification
Chapter two: Literature Review, providing an overview of past and current AI research into scrabble games as well as the successes and what is yet to be done in this regard.
Chapter 3: Building an Intelligent Scrabble player; shows how AI methods have been used to develop Scrabble engines that behave intelligently and gave a formal description and logic of the computer game NigerScrab as well as the game model. Existing Scrabble engines is also analysed.
Chapter 4: Methodology and Design explains the interdependencies in tasks of designing the game engine and also justifies the choice of the methodologies used used. The structure of a strategy plan is developed and its developments analysed.
Chapter 5: the proposed model implementation and testing presents how acquired plans are implemented into concrete actions in the game. Discussion and results of experiments that were carried out in substantiating the development process and evaluating the performance of program is further presented.
Chapter 6: Summary, Conclusion and Recommendations summarises the achievements of the project and outlines limitations and future work.