Author: Tianyi (Bruce) Chen
In this passage, I’ll use python to code to let AI find all solutions of a boggle game quickly.
Introduction:
If you don’t know the rule of boggle game, here’s a brief explanation of how boggle game works: Boggle is a word game played on a NxN grid of lettered dice. Players search for words by connecting adjacent letters (horizontally, vertically, or diagonally) to form words of three letters or more within a time limit, usually two minutes. Points are awarded based on the length of the words found, and the player with the highest score wins. (For specific rules of boggle games: https://en.wikipedia.org/wiki/Boggle)
Design procedure:
To realize the whole function, like all AI program, we should read the dataset first. So there should be function to read through the board and the dictionary which contains all words. Secondly, we should do design some function to pre-process our data. Thirdly, we should feed the data into the searching functions. Last, there should be a overall function to save the output and concatenate all functions together.
Read the board and dictionary
loadBoard() use the line compression to read through the board. The line is read as type ‘String’, the method ‘split()’ is to separate each letter with space.
printBoard() is just to print out the read board.
def loadBoard(board_path):
return [line.split() for line in open(board_path)]def printBoard(board):
for item in board:
print(" ".join(item)) # use item(list type) to iterate and concatenate with " "
readDictionary() read through the word dictionary. In ‘with’ loop, f will read each letter, and they are concatenated to form a string until a inline (‘\n’) is detected. When ‘\n’ is detected, it will save the string into list.
def readDictionary(filename):
with open(filename) as f:
dictList = []
text = f.read()
str = ''
for i in text:
if i != '\n':
str= str + i
else:
dictList.append(str)
str = ''
return dictList
Basic algorithm functions
In this part, we’ll define few functions to compose the basic function of boggle game.
Firstly, there should be a function to find a list of possible coordinates of any specific position. Here we call it possibleMoves().
Secondly, there should be a function to remove the repeated coordinates and output rest coordinates because one coordinate can only be routed (or passed onece), which we call them illegal coordinates. The function is called legalMoves().
Thirdly, there should be a function to compose the passed coordinates together into a string and another function to check whether the the string is a word in dictionary or not. Here we call them forwWord() and examineState() respectively.
possibleMoves() is to produce the next-movable position of input coordinate. I use the zip packing method and unpack methods here to avoid the specify the axis number.
def possibleMoves(cord,board):
h = len(board)
w = len(board[0])
pos_move = set()
offsets = [-1,0,1]
offset_candidates = [(x_offset,y_offset) for x_offset in offsets for y_offset in offsets] #here the iteration of offset create the offset coordinates list of 8 position.
offset_candidates.remove((0,0))
for candidate in offset_candidates:
x, y = zip(cord, candidate) #pack center cord with one offset
cord_x, cand_x = x
cord_y, cand_y =y
x = cord_x + cand_x # add center cordinate and offset together in x&y
y = cord_y + cand_y
if x >= 0 and x < h and y >= 0 and y<w: #this if statement is to judge the offset + coordinates exceeds the border of boggle or not.
possible_moves.append((x,y))
else:
continue
return possible_moveslegalMoves() is to remove the specified coordinates from possible moves.
def legalMoves(moves,path):
pos = set(moves) - path #set difference
return posformWord() is to locate the corresponding letters according to the coordinates list and concatenate them into string.
def formWord(myBoard, position, path):
x,y = position
word = myBoard[x][y]
for path_item in path:
i,j = path_item
word = word + myBoard[i][j]
return word.lower()examineState() is to look through the input dictionary of the function to check whether the word is inside it and return the result (True/False).
def formWord(myBoard, position, path):
x,y = position
word = myBoard[x][y]
for path_item in path:
i,j = path_item
word = word + myBoard[i][j]
return word.lower()Synthesize of functions and optimization
Now, we have all the required functions. And we can construct the boggle function like this: loadBoard-> readDictionary ->possibleMoves->for loop: {formWord->examineState->legalMoves} until there’s no leagalMoves -> next coordinate-> found words.
But the program will be rather slow if we just look through all whole combination from each coordinate. (More than 1 hour for 1 coordinate look through in 4×4 boggle). So, we must implement some methods to optimize it.
After analysis, I found there are large amount of formed string cannot form word when forming in second/third/forth letter. So, there must be a method to pause the deeper searching if the formed string is not possible to form. Moreover, to reduce the computation cost from start (the first letter), I divide the dictionary into small chunks (sub-dictionary), where the program will only look through words corresponds to the first letter. The code to realize these 2 functions is as follows:
subDictionary() is to divide the dictionary (stored as list type) into a dictionary object, where the key is the first letter, value is words start with this letter.
def subDictionary(dictionary):
"""
#This function is to turn the list into a dictionary
#to let algorithm only search in the first letter are
"""
sub_dictionary = {}
sub_list = []
first_letter = 'a'
for word in dictionary:
if first_letter == word[0]:
sub_list.append(word)
#print(sub_list)
else:
sub_dictionary[first_letter] = sub_list
sub_list = []
first_letter = word[0]
sub_list.append(word)
sub_dictionary[first_letter] = sub_list
return sub_dictionarycheckDictionary() is to judge the possibility of current formed string forming words in the dictionary. The function takes sub-dictionary as input and iterates through it. If there is no word can be formed by input string, it will return False. If there are words can be formed, it will record the position of the first formable word in the dictionary and return at the last formable word with True, first location, last location. So that the latter program can utilize the locations to shrink the search zone, which reduces the computation cost.
def checkDictionary(word,dictionary):
"""
This function is to check current word is a part of words in the dictionary
"""
length = len(word)
i = 0
i_start = -1
i_end = -1
for w in dictionary:
if i_start == -1 and word in w[0:length]:
#print("True")
i_start = i #record the start point of the sub-dictionary
if i_start !=-1 and (word in w[0:length]) == False:
i_end = i+1 #record the end point of the sub-dictionary
return True,i_start,i_end
i = i+1
if i_start != -1:
return True, i_start, i # the situation that word is iterate through til the end
return False,-1,-1findWords() is the function to form paths to look through the formable words with the initial position letter and concatenating above functions.
import pdb
def findWords(board,dictionary,foundWords,moves,availableCords=[],beenCords=[]):
"""
this function is to iterate through possible path (with 'abandom' algorithm) and
then form words to search in the corresponding dictionary index
parameters:
board:board, list
dictionary: the dictionary with first letter index
foundWords: where the found words will be saved, list
moves: the counter to count how many steps the algorithm has gone
"""
possible_moves = possibleMoves(beenCords[-1],board)
legal_moves = legalMoves(possible_moves,set(beenCords))
for move in legal_moves:
moves[0] = moves[0] + 1 #use move to record to steps
availableCords.remove(move) #remove current move from available move
beenCords.append(move)
word = formWord(board,beenCords[0],beenCords[1:])
state, index_start, index_end = checkDictionary(word,dictionary)
temp_dictionary = dictionary[index_start: index_end+1]
status = examineState(word,temp_dictionary)
### add one clever here : function judge the formed word is partial of dictionary or not
#pdb.set_trace()
if state == False :
pre_pos = beenCords.pop()
availableCords.append(pre_pos)
continue
###
else:
#print('into lower level function')
if status == 'YES':
foundWords.append(word.upper())
findWords(board,temp_dictionary,foundWords,moves,availableCords,beenCords)
prev_pos = beenCords.pop() #after iterate through all posible legal moves, it go delete current path and go back.
availableCords.append(prev_pos)
if len(beenCords) == 1:
return "finish one searching"runBoard() is the function to synthesize all function together: read the board, dictionary, feed initial position into findWords iteratively and print out total spending time and found words.
import time
def runBoard(board_filename, dictionary_filename):
start_time = time.time()
board = loadBoard(board_filename)
printBoard(board)
dictionary = readDictionary(dictionary_filename)
## clever
dictionary = subDictionary(dictionary) # create a real dictionary with first letter as index
##
H = len(board) #number of rows
W = len(board[0]) #number of columns
found_words = []
moves = [0]
for h in range(H):
for w in range(W):
position = (h,w)
#print("Searching on :")
#print(position)
available_cords = [(i,j) for i in range(len(board)) for j in range(len(board[0]))]
available_cords.remove(position)
first_letter = board[h][w]
sub_dictionary = dictionary[first_letter.lower()]
findWords(board,sub_dictionary,found_words,moves,availableCords = available_cords,beenCords = [position])
end_time = time.time()
duration_time = end_time - start_time
print("And we're off!\nRunning with cleverness ON\nAll done")
word_dict = {}
for word in found_words:
word_dict[len(word)] = []
for word in found_words:
word_dict[len(word)].append(word)
print("Find words:")
for key in word_dict:
print('%d'%key+' -letter words:' + str(word_dict[key]))
print("The number of find words: ")
print(len(set(found_words)))
print("Searched total of %d"%moves[0] + " moves in %f seconds"%duration_time)
return sorted(set(found_words))
Program running
To run inside python
#add after above code
words_list = runBoard('board.txt','twl06.txt')To run as script in command line: python board_path dictionary_path python_file_name
#add after above code
import sys
script_py, board, dictionary = sys.argv
words_list = runBoard(board,dictionary)
path = board.split('.')[0] + '_words.txt'
file = open(path,'w')
for word in words_list:
file.write(word)
file.write('\n')
file.close()Future possible development:
To let this boggle game becomes faster, we can divide the sub-dictionary into smaller sub-dictionary when the file which saves word dictionary is big enough.
Tianyi Bruce Chen 
