A Scrabble game

0. What is Scrabble game
For example, if you had the letter tiles "P", "A", "L", "P", and "O" (note that you can possess repeated letters), and the board looked like this:

_	_	_	_	_	_
_	_	_	_	_	_
_	_	T	_	_	_
_	_	E	_	_	_
G	R	A	P	E	_
_	_	R	_	_	_

There would be a large number of possible moves, or words to place. Here are a few of the possibilities (indicated by bold letters) :

_ _ _ _ _ _ _ _ _ _ _ _ _ _ T A P _ _ _ E _ _ _ G R A P E _ _ _ R _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ L O T _ _ _ _ _ E _ _ _ G R A P E _ _ _ R _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ L _ T _ _ _ A _ E _ _ _ G R A P E _ _ _ R _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ _ _ T _ _ _ _ _ E _ _ _ G R A P E _ O _ R _ _ _

_ _ _ _ A _ _ _ _ _ P _ _ _ T _ P _ _ _ E _ L _ G R A P E _ _ _ R _ _ _

As you can summarize from the above, rules are as follows: 

1. More than one letter

2. Placing position is valid

3. word exists in the dictionary

4. Crossword-style

5. No additional new word is created

0.5 Logic

1. A dictionary to store all the valid word
-Constructor: init in Game class to load all words into dictionary
-Function: allow add word
-Function: allow search a word exist or not in  the dictionary, including pattern matching
- Leetcode: add and search word


2. A board to hold all the characters or tiles
-Constructor: a DS to store all the characters, A-Z (Upper case), '_'(Empty character)
ScrabbleBoard(int numrows, int numcols, ScrabbleMove move) 
the board is initialized with the word represented by move (unless it is null)
-Function: update the new move on the board, which means place legal word onto the board
-Function: isLegal(ScrabbleMove, Trie) 


3. Move
-Constructor: a move contains start location, direction,
ScrabbleMove(int row, int column, boolean direction, String word) intended word 
-Function: search a move, find all available characters on the board and choose the one with no character on the column or row where it locate(could be vertical or horizontal) and make sure only one character next to it
-Function:search a word and form a move ("T." and length >=4, ".T" and length <=3, ".G" and length 5, "G." and  length 2) 
-Function: calculate score for a legal move


4. Game
-Constructor:
- init board(int rows, int columns), init dictionary(filename)
- distribute letter tiles (String letterBag)
- whose turn (double[] players)
- scores, points(int[] letterValues)
- (int rows, int columns, String filename, double[] players, String letterBag, int numTiles, int[] letterValues, int seed)
-filename: the filename of a file containing the vocabulary of the game
-letterBag: a String representing all of available letter tiles for the game. There is one character for each available tile - thus, characters may be repeated.
-numTiles: the maximum number of letter tiles available to a player at any time
-letterValues: a 26-element int array indicating the points value of every letter
-seed: used to seed a single number generator
-Function: run game to make turns and no any move=> Game Over
-Function: currentLetters(): returns a string, representing the letter tiles available to current human player


5. AI 
-Constructor
-bestMove( ScrabbleBoard board, Trie vocabulary, int[] points, String letters)
static method which returns the highest-scoring legal move
-Move: search a best move
-Function: allMoves(ScrabbleBoard board, Trie vocabulary, String letters)
static method which returns all legal moves (as an array of ScrabbleMoves), given the parameters(same as bestMove). Return null if no moves are available

1. Trie.java
The vocabulary of all allowable words in your game will be represented by a trie.

Trie(String filename)
void addWord(String)
String[] getAllWords(String)
String[] getMatches(String)
"TR.E" => "TRIE" and "TREE"
Not "TRE" or "STREET"
boolean hasWord(String)
int size()

Method	Description
Trie(String filename)	The constructor, which reads a word list from the filename provided as a parameter, and builds a trie containing those words.
addWord(String)	Store the specified word in the trie. If the word exists in the trie already, then do nothing.
getAllWords()	Returns an array of Strings, containing all the words in the trie in sorted order.
getMatches(String)	Returns an array of Strings, containing all the words in the trie which match the given pattern, in sorted order.
hasWord(String)	Returns a boolean indicating whether the given word is contained within the trie.
size()	Returns an int count of the number of words in the trie.

2. ScrabbleMove.java
A move consists of a large amount of information: where the word is placed, the direction that it's placed in, and the actual word to be placed.

ScrabbleMove(int row, int column, boolean direction, String word)
direction = true when horizontal and direction = false when vertical
word means intended word
int getRow()
int getColumn()
boolean getDirection()
String getWord()

Method	Description
ScrabbleMove(int row, int column, boolean direction, String word)	Constructor, with parameters indicating the move's row, column, direction ( true = horizontal, false = vertical), and intended word.
getRow(), getColumn(), getDirection(), getWord()	These methods return (respectively) the move's row, column, direction, and intended word.

3. ScrabbleBoard.java
you must implement the rules of the game, so that only legal moves are permitted. Exactly how you implement theScrabbleBoard is up to you, including how you represent the board. You should decide which data structures or classes are most appropriate in order to implement the class according to the specifications.

ScrabbleBoard(int numrows, int numcols, ScrabbleMove move)
int numRows()
int numColumns()
charAt(int row, int column)
'_' if unoccupied
toString()
" " first row (each column start)
"\n" first column (each row start)
makeMove(ScrabbleMove, Trie)
update the board
isLegal(ScrabbleMove, Trie)

Method	Description
ScrabbleBoard(int numrows, int numcols, ScrabbleMove move)	The constructor, which creates a Scrabble board with numrows rows and numcols columns. The board is initialized with the word represented bymove (unless it is null). Precondition: move only occupies valid board locations. (Modified July 22)
numRows(), numColumns()	Return an int representation of the board's number of rows and columns, respectively.
charAt(int row, int column)	Returns the character (as a char) at positions (row, column), or an underscore ('_') if the position is unoccupied.
toString()	Return a String representation of the board, with each column preceded by a blank space (" ") and each row followed by a newline ("\n"). Empty positions are represented by an underscore ("_").
makeMove(ScrabbleMove, Trie)	Make the specified move and update the board as appropriate. Throws an IllegalMoveException if the move is illegal. Precondition: any words already on the board are in the given vocabulary.
isLegal(ScrabbleMove, Trie)	Returns a boolean indicating whether the specified move is legal, given a vocabulary in trie form. Precondition: any words already on the board are in the given vocabulary.

4. ScrabbleAI.java
bestMove(ScrabbleBoard board, Trie vocab, int[] points, string letters)
allMoves(ScrabbleBoard board, Trie vocab, String letters)

Method	Description
bestMove(ScrabbleBoard board, Trie vocab, int[] points, String letters)	static method which returns the highest-scoring legal move given: board: the current board state. vocab: a vocabulary in trie form. points: a 26-item array of ints, indicating the point value of each letter in the alphabet. letters: the letter tiles available to the AI to place. This may be the empty string, and it may contain repeated characters. However, the order of the characters should not matter. Returns null if no moves are available.
allMoves(ScrabbleBoard board, Trie vocab, String letters)	static method which returns all legal moves (as an array of ScrabbleMoves), given the parameters (same as bestMove). Returns null if no moves are available.

5.ScrabbleGame.java
Everything is tied together by the "front end" class, ScrabbleGame. This class is created with all of the parameters of the game, manages the AI players, keeps score, and distributes letter tiles.

Method	Constructor
ScrabbleGame(int rows, int columns, String filename, double[] players, String letterBag, int numTiles, int[] letterValues, int seed)	Constructor, which creates a Scrabble game with the following parameters: rows: the number of rows on the board. columns: the number of columns on the board. filename: the filename of a file containing the vocabulary of the game. players: an array of doubles, with one entry for each player, in order. The entries are either -1 (indicating a human player) or a value between 0 and 1 (indicating the skill of an AI player). letterBag: a String representing all of the available letter tiles for the game. There is one character for each available tile - thus, characters may be repeated. numTiles: the maximum number of letter tiles available to a player at any time. letterValues: a 26-element int array indicating the points value of every letter. seed: used to seed a single random number generator.
isOver()	Returns a boolean, indicating whether the game is finished or not.
getScores()	Returns an array of ints, representing the current score of each player.
currentPlayer()	Returns an int, representing the player # of the human player whose move is required.
currentLetters()	Returns a String, representing the letter tiles available to the current human player.
makeMove(ScrabbleMove)	Makes the specified move, for the current human player. A null parameter indicates a "pass". If the move is illegal, throws an IllegalMoveException and play does not advance to the next player.
getBoard()	Returns a String representation of the current board.

6. Order of play
when the game is started, the following occurs:

1. The game vocabulary is loaded.
2. Each player is given random letter tiles from the bag, one player at a time. for example, Player 0 gets a tile, then Player 1 , and so on. This continues until all players have the maximum number of tiles, or there is only one letter tile remaining in the bag.
3. One of the remaining letter tiles is selected, and is placed at a random position - that is, a random row and a random column. If only one tiles remains, it is chosen automatically without a random number being generated.
4. Play begins with Player 0, and continues with each player in order , repeating in order once the last player's turn is over. Players may either make a legal move, or pass. Players with no remaining letter tiles automatically pass.
       - when a player makes a legal move by placing n letter tiles, they are given n randomly-selected tiles from the bag to maintain same number of letter tiles. If fewer than n tiles remain, then the palyer is given all remaining tiles (which may be none) without a random number being generated.
      - when a player make a legal move, their score is modified by the total points value of every letter in the word that was created.
Note: this means that points are awarded for letters which the player did not place, but are part of the word they created.
      - if current turn is an AI player, their move is determined according to their skill level (see below), and play continues to the next player.

5. If all players has passed in a row (for example, Player 1 passed, Player 2 passed, ....and then Player ) passed), then the game is over.

6. AI
Each AI player is represented by a "skill value" between 0 and 1. On its turn, an AI player with a skill value of s will determine its action according to the following algorithm:

 1. A random number r, between 0 and 1, is generated.
 2. If r < s, the AI player makes the best legal move, or passes if no moves are available.
 3. Otherwise, the AI player randomly makes one of all the available moves, or passes if no moves are available.

7. Move Legally

     1. More than one letter

     2. Placing position is valid

     3. word exists in the dictionary

     4. Crossword-style

     5. No additional new word




_
_
_
_
_
_
E
_
_
_
A
_
_
_
T
_

After placing "CAR" horizontally at (2, 1):

_
_
_
_
_
_
E
_
_
C
A
R
_
_
T
_




While the following move is illegal because "RC" and "ER" were created. Even if these words were in the game's vocabulary, this move would still be illegal.


_
_
_
_
T
R
E
E
_
_
A
_
_
_
T
_

After placing "CAR" horizontally at (2, 1):

_
_
_
_
T
R
E
E
_
C
A
R
_
_
T
_




This move would also be illegal, because "BEAT" was created, even though it may be in the game's vocabulary:


_
_
_
_
_
_
E
_
_
_
A
_
_
_
T
_

After placing "CAB" horizontally at (0, 0):

C
A
B
_
_
_
E
_
_
_
A
_
_
_
T
_




(Added July 22) At least one of the move's letters corresponds to a board position already occupied for that letter. This means that new words must be placed "crossword-style" (attached to each other) and not just anywhere on the board. For example, the following is illegal:


_
_
_
_
_
_
_
_
_
_
_
_
R
A
T
_

After placing "CAR" horizontally at (1, 0):

_
_
_
_
C
A
R
_
_
_
_
_
R
A
T
_



However, the word could be placed legally this way:


_
_
_
_
_
_
_
_
_
_
_
_
R
A
T
_

After placing "CAR" vertically at (1, 0):

_
_
_
_
C
_
_
_
A
_
_
_
R
A
T
_










Random Numbers

Like in Assignment 3, your ScrabbleGame should use a single object of class Random to generate all of its random numbers, and the Random should be seeded with the value provided to theScrabbleGame constructor. When generating a random number between 0 and 1, use the nextDouble method as in Assignment 3. However, in many cases you have to make a random selection from a particular number of elements. In these situations, use the nextInt(int n) method, which generates a random int between 0 (inclusive) and n (exclusive).

Simplifying Assumptions

Because this assignment involves a substantial amount of design, both for classes and algorithms, you may assume "resonable" input for each method described here. This means that you may make the following assumptions:

All Strings provided as parameter, consist only of upper-case letters, or the empty string. The only exception to this is Trie.getMatches, whose input String may also contain periods (".").
All filenames will be valid.
No null values will be provided as parameters. The only exception to this is ScrabbleGame.makeMove.
The board will have at least two rows and two columns. Otherwise, that would be silly.
There will be at least one player.







References:

http://www.dgp.toronto.edu/~karan/courses/148/148/assignments/a4/a4handout.html


https://github.com/marineb/scrabble/blob/master/src/Gameplay.java


http://www.java-forums.org/new-java/29100-scrabble-like-game.html

http://cs.stanford.edu/people/eroberts/courses/cs106a/handouts/32a-section-4-solutions.pdf