Creating a scrabble AI

Help and Feedback Scripting Support
#1

so lets say i’m trying to create a bot to play scrabble.i have an array of valid words and i have four functions to manipulate the board. (resetLetter changes it to what it was before setLetter was called)

setLetter: (position: Vector2, letter: string) => void
getLetter: (position: Vector2) => void
resetLetter: (position: Vector2) => void
checkValid: () => boolean – checks if letters placed on the board are valid and follow scrabble rules

i also have an array containing the letters the bot can place as strings. so like [“a”,“b”,“c”,“d”…]

my idea was to loop through the board like this:

for x = 0, 20 do
    for y = 0, 20 do
        local letter = getLetter(Vector2.new(x,y))
        -- find a valid word you can build off of
    end
end

but i’m not sure how i’d go about finding the valid words or placing them correctly. thanks for any help, i know its a lot

1 Like
#2

Here’s an idea I came up with, the only downside is you need to create a pre-existing dictionary of valid words.

  1. Starting with the letter already placed on the board as the first letter of the new word, add a letter from the array of letters the bot can use.
  2. Recursively, keep adding letters to the generated word until all letters are used up, then check if this newly generated word is valid by checking a pre-existing dictionary you created.
  3. If the word is valid, add it to a dictionary of words that can be used and return this dictionary
  4. Have the AI select the longest word created or have it randomly select one, it’s up to you

So something along the lines of this

-- this doesn't account for if the letter is lower or upper case
-- so make sure EVERYTHING is lower case, or add a feature to account for it yourself

wait(2)
local matches = {}

local function find_words(dictionary, characters, word)
	if dictionary[word] then
		if not table.find(matches, word) then
			table.insert(matches, word)
		end
	end

	for _, char in ipairs(characters) do
		local new_characters = {}
		for _, v in ipairs(characters) do
			--[[
				This is bad practice, avoid nested loops
				if theres a better way of doing something
				this nested loop has a Big-O of n^2
				so if you increase the number of letters in
				characters dictionary, youll notice
				it takes WAY longer to return this function
				
				fortunately, scrabble only has 7 letters anyway
				so the time taken is unnoticeable 
			]]
			if v ~= char then
				table.insert(new_characters, v)
			end
		end

		find_words(dictionary, new_characters, word .. char)
	end
end

local dictionary = {
	['l'] = {'lorem', 'love', 'labyrinthine'}
}

local characters = {'e', 'o', 'v', 'a', 'm', 'r', 'v'}

-- this is assuming the bot can only create words
-- using an already placed letter as the start of the word

local starting_letter = 'l'

-- Convert the list of words to a table for faster lookup
local dictionaryTable = {}
for _, word in ipairs(dictionary[starting_letter]) do
	dictionaryTable[word] = true
end

local a = tick()
find_words(dictionaryTable, characters, starting_letter)
local b = tick()

print(matches, '\n\ntime taken: ' .. tostring(b - a))

Screenshot 2023-11-23 150930

1 Like