2
$\begingroup$

I'm working on an algorithm which is permitted to use a training set of approximately 250,000 dictionary words.

I have built and providing here with a basic, working algorithm. This algorithm will match the provided masked string (e.g. a _ _ l e) to all possible words in the dictionary, tabulate the frequency of letters appearing in these possible words, and then guess the letter with the highest frequency of appearence that has not already been guessed. If there are no remaining words that match then it will default back to the character frequency distribution of the entire dictionary.

This benchmark strategy is successful approximately 10% of the time. I aim to design an algorithm that significantly outperforms this benchmark.

class HangmanAPI(object):
    def __init__(self, access_token=None, session=None, timeout=None):
        self.hangman_url = self.determine_hangman_url()
        self.access_token = access_token
        self.session = session or requests.Session()
        self.timeout = timeout
        self.guessed_letters = []

        full_dictionary_location = "words_250000_train.txt"
        self.full_dictionary = self.build_dictionary(full_dictionary_location)
        self.full_dictionary_common_letter_sorted = collections.Counter("".join(self.full_dictionary)).most_common()

        self.current_dictionary = []

        # Initialize the decision tree, random forest, and SVM models along with the vectorizer
        self.decision_tree_model = DecisionTreeClassifier()
        self.random_forest_model = RandomForestClassifier(n_estimators=100, random_state=42)
        self.svm_model = SVC(kernel='linear', probability=True, random_state=42)
        self.vectorizer = CountVectorizer(analyzer='char', lowercase=False, binary=True)
        self.target_labels = [chr(ord('a') + i) for i in range(26)]

        # Fit the decision tree model with the full dictionary once during initialization
        X = self.vectorizer.fit_transform(self.full_dictionary)
        y = np.array([word[-1] for word in self.full_dictionary])
        self.decision_tree_model.fit(X, y)

        # Add Q-table to store Q-values for state-action pairs
        self.q_table = {}

        # Hyperparameters for Q-learning
        self.learning_rate = 0.1
        self.discount_factor = 0.9
        self.epsilon = 0.1  # Probability of exploration during action selection

    def update_q_table(self, state, action, reward, next_state):
        # Q-learning update rule
        current_q_value = self.q_table.get((state, action), 0.0)
        next_q_values = [self.q_table.get((next_state, next_action), 0.0) for next_action in self.target_labels]
        max_next_q_value = max(next_q_values)
        new_q_value = current_q_value + self.learning_rate * (reward + self.discount_factor * max_next_q_value - current_q_value)
        self.q_table[(state, action)] = new_q_value

    def extract_features(self, word_pattern):
        # Extract features from the word pattern
        features = []

        # Word Length
        features.append(len(word_pattern))

        # Vowel and Consonant Counts
        vowel_count = sum(1 for letter in word_pattern if letter in 'aeiou')
        consonant_count = sum(1 for letter in word_pattern if letter in 'bcdfghjklmnpqrstvwxyz')
        features.append(vowel_count)
        features.append(consonant_count)

        # Common Letter Count
        common_letters = set("etaoinsrhldcumfpgwybvkxjqz")
        common_letter_count = sum(1 for letter in word_pattern if letter in common_letters)
        features.append(common_letter_count)

        # Letter Position Features
        features.append(1 if word_pattern.startswith('a') else 0)  # Check if starts with 'a'
        features.append(1 if word_pattern.endswith('e') else 0)  # Check if ends with 'e'
        features.append(1 if 'qu' in word_pattern else 0)  # Check if contains 'qu'

        # Character N-grams
        n_grams = [word_pattern[i:i + 2] for i in range(len(word_pattern) - 1)]
        for n_gram in ['th', 'er', 'in', 'ou', 'an']:  # Example: Consider the presence of common letter pairs
            features.append(1 if n_gram in n_grams else 0)

        # Part-of-Speech (POS) Features - Not implemented here, requires external NLP tools

        # Syllable Count - Not implemented here

        # Letter Frequency Distribution - Not implemented here

        return features

    def hyperparameter_tuning(self):
        # Define the hyperparameter search spaces for each model using hyperopt
        dt_space = {
            'criterion': hp.choice('criterion', ['gini', 'entropy']),
            'splitter': hp.choice('splitter', ['best', 'random']),
            'max_depth': hp.choice('max_depth', [None, 10, 20, 30]),
            'min_samples_split': hp.choice('min_samples_split', [2, 5, 10]),
            'min_samples_leaf': hp.choice('min_samples_leaf', [1, 2, 4])
        }

        rf_space = {
            'n_estimators': hp.choice('n_estimators', [100, 200, 300]),
            'criterion': hp.choice('criterion', ['gini', 'entropy']),
            'max_depth': hp.choice('max_depth', [None, 10, 20, 30]),
            'min_samples_split': hp.choice('min_samples_split', [2, 5, 10]),
            'min_samples_leaf': hp.choice('min_samples_leaf', [1, 2, 4]),
            'bootstrap': hp.choice('bootstrap', [True, False])
        }

        svm_space = {
            'C': hp.loguniform('C', -3, 1),  # Search space for C in log scale
            'kernel': hp.choice('kernel', ['linear', 'poly', 'rbf', 'sigmoid']),
            'gamma': hp.choice('gamma', ['scale', 'auto'])
        }

        # Perform Bayesian optimization for Decision Tree
        dt_best = fmin(fn=self.hyperopt_objective, space=dt_space, algo=tpe.suggest, max_evals=50, verbose=0)
        self.decision_tree_model = DecisionTreeClassifier(
            criterion=dt_best['criterion'],
            splitter=dt_best['splitter'],
            max_depth=dt_best['max_depth'],
            min_samples_split=dt_best['min_samples_split'],
            min_samples_leaf=dt_best['min_samples_leaf']
        )

        # Perform Bayesian optimization for Random Forest
        rf_best = fmin(fn=self.hyperopt_objective, space=rf_space, algo=tpe.suggest, max_evals=50, verbose=0)
        self.random_forest_model = RandomForestClassifier(
            n_estimators=rf_best['n_estimators'],
            criterion=rf_best['criterion'],
            max_depth=rf_best['max_depth'],
            min_samples_split=rf_best['min_samples_split'],
            min_samples_leaf=rf_best['min_samples_leaf'],
            bootstrap=rf_best['bootstrap']
        )

        # Perform Bayesian optimization for SVM
        svm_best = fmin(fn=self.hyperopt_objective, space=svm_space, algo=tpe.suggest, max_evals=50, verbose=0)
        self.svm_model = SVC(
            C=svm_best['C'],
            kernel=svm_best['kernel'],
            gamma=svm_best['gamma']
        )

    def hyperopt_objective(self, params):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        model = DecisionTreeClassifier(**params)
        cv_score = cross_val_score(model, X, y, cv=5).mean()
        return -cv_score

    def genetic_algorithm_tuning(self):
        # Define the hyperparameter search spaces for each model
        dt_space = {
            'criterion': ['gini', 'entropy'],
            'splitter': ['best', 'random'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4]
        }

        rf_space = {
            'n_estimators': [100, 200, 300],
            'criterion': ['gini', 'entropy'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4],
            'bootstrap': [True, False]
        }

        svm_space = {
            'C': [0.1, 1, 10],
            'kernel': ['linear', 'poly', 'rbf', 'sigmoid'],
            'gamma': ['scale', 'auto']
        }

        # Perform Genetic Algorithm optimization for Decision Tree
        dt_genetic_algorithm = ga(function=self.genetic_algorithm_objective, dimension=len(dt_space), variable_type='int', variable_boundaries=[(0, len(dt_space[key]) - 1) for key in dt_space])
        dt_best_idx = dt_genetic_algorithm.run()
        dt_best = {list(dt_space.keys())[i]: dt_space[list(dt_space.keys())[i]][idx] for i, idx in enumerate(dt_best_idx)}
        self.decision_tree_model = DecisionTreeClassifier(
            criterion=dt_best['criterion'],
            splitter=dt_best['splitter'],
            max_depth=dt_best['max_depth'],
            min_samples_split=dt_best['min_samples_split'],
            min_samples_leaf=dt_best['min_samples_leaf']
        )

        # Perform Genetic Algorithm optimization for Random Forest
        rf_genetic_algorithm = ga(function=self.genetic_algorithm_objective, dimension=len(rf_space), variable_type='int', variable_boundaries=[(0, len(rf_space[key]) - 1) for key in rf_space])
        rf_best_idx = rf_genetic_algorithm.run()
        rf_best = {list(rf_space.keys())[i]: rf_space[list(rf_space.keys())[i]][idx] for i, idx in enumerate(rf_best_idx)}
        self.random_forest_model = RandomForestClassifier(
            n_estimators=rf_best['n_estimators'],
            criterion=rf_best['criterion'],
            max_depth=rf_best['max_depth'],
            min_samples_split=rf_best['min_samples_split'],
            min_samples_leaf=rf_best['min_samples_leaf'],
            bootstrap=rf_best['bootstrap']
        )

        # Perform Genetic Algorithm optimization for SVM
        svm_genetic_algorithm = ga(function=self.genetic_algorithm_objective, dimension=len(svm_space), variable_type='int', variable_boundaries=[(0, len(svm_space[key]) - 1) for key in svm_space])
        svm_best_idx = svm_genetic_algorithm.run()
        svm_best = {list(svm_space.keys())[i]: svm_space[list(svm_space.keys())[i]][idx] for i, idx in enumerate(svm_best_idx)}
        self.svm_model = SVC(
            C=svm_best['C'],
            kernel=svm_best['kernel'],
            gamma=svm_best['gamma']
        )

    def genetic_algorithm_objective(self, idxs):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        dt_space = {
            'criterion': ['gini', 'entropy'],
            'splitter': ['best', 'random'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4]
        }

        rf_space = {
            'n_estimators': [100, 200, 300],
            'criterion': ['gini', 'entropy'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4],
            'bootstrap': [True, False]
        }

        svm_space = {
            'C': [0.1, 1, 10],
            'kernel': ['linear', 'poly', 'rbf', 'sigmoid'],
            'gamma': ['scale', 'auto']
        }

        dt_best = {list(dt_space.keys())[i]: dt_space[list(dt_space.keys())[i]][idx] for i, idx in enumerate(idxs)}
        rf_best = {list(rf_space.keys())[i]: rf_space[list(rf_space.keys())[i]][idx] for i, idx in enumerate(idxs)}
        svm_best = {list(svm_space.keys())[i]: svm_space[list(svm_space.keys())[i]][idx] for i, idx in enumerate(idxs)}

        dt_model = DecisionTreeClassifier(
            criterion=dt_best['criterion'],
            splitter=dt_best['splitter'],
            max_depth=dt_best['max_depth'],
            min_samples_split=dt_best['min_samples_split'],
            min_samples_leaf=dt_best['min_samples_leaf']
        )
        dt_cv_score = cross_val_score(dt_model, X, y, cv=5).mean()

        rf_model = RandomForestClassifier(
            n_estimators=rf_best['n_estimators'],
            criterion=rf_best['criterion'],
            max_depth=rf_best['max_depth'],
            min_samples_split=rf_best['min_samples_split'],
            min_samples_leaf=rf_best['min_samples_leaf'],
            bootstrap=rf_best['bootstrap']
        )
        rf_cv_score = cross_val_score(rf_model, X, y, cv=5).mean()

        svm_model = SVC(
            C=svm_best['C'],
            kernel=svm_best['kernel'],
            gamma=svm_best['gamma']
        )
        svm_cv_score = cross_val_score(svm_model, X, y, cv=5).mean()

        return -(dt_cv_score + rf_cv_score + svm_cv_score) / 3

    def train_all_models(self):
        X = self.vectorizer.transform(self.full_dictionary)
        y = np.array([word[-1] for word in self.full_dictionary])

        # Fit all models with the full dictionary
        self.decision_tree_model.fit(X, y)
        self.random_forest_model.fit(X, y)
        self.svm_model.fit(X, y)

        # Perform hyperparameter tuning for Decision Tree, Random Forest, and SVM models
        self.hyperparameter_tuning()

        # Train the neural network model and perform fine-tuning
        self.train_neural_network()
        self.fine_tune_neural_network()
        
    def word_to_numeric(self, word):
        # Convert word pattern to a binary sequence of guessed (1) and not guessed (0) letters
        return [1 if letter in self.guessed_letters else 0 for letter in word]

    def ensemble_guess(self, word_pattern):
        numeric_word_pattern = self.word_to_numeric(word_pattern)
    
        # Get predictions from all three models
        dt_guess = self.decision_tree_model.predict([numeric_word_pattern])[0]
        rf_guess = self.random_forest_model.predict([numeric_word_pattern])[0]
        svm_guess = self.svm_model.predict([numeric_word_pattern])[0]

        # Create a list of all model predictions
        ensemble_guesses = [dt_guess, rf_guess, svm_guess]

        # Use voting to determine the final prediction
        guessed_letter = max(set(ensemble_guesses), key=ensemble_guesses.count)

        return guessed_letter
        
    @staticmethod
    def determine_hangman_url():
        links = ['https://trexsim.com', 'https://sg.trexsim.com']

        data = {link: 0 for link in links}

        for link in links:
            requests.get(link)

            for i in range(10):
                s = time.time()
                requests.get(link)
                data[link] = time.time() - s

        link = sorted(data.items(), key=lambda x: x[1])[0][0]
        link += '/trexsim/hangman'
        return link

    def train_neural_network(self):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        # Convert the word patterns to images (2D arrays)
        X_images = self.patterns_to_images(X.toarray(), self.vectorizer.vocabulary_)

        # Initialize and configure the convolutional neural network model
        neural_net_model = Sequential()
        neural_net_model.add(Conv2D(32, kernel_size=(3, 3), activation='relu', input_shape=(X_images.shape[1], X_images.shape[2], 1)))
        neural_net_model.add(MaxPooling2D(pool_size=(2, 2)))
        neural_net_model.add(Flatten())
        neural_net_model.add(Dense(128, activation='relu'))
        neural_net_model.add(Dense(64, activation='relu'))
        neural_net_model.add(Dense(26, activation='softmax'))
        neural_net_model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])

        # Convert labels to one-hot encoding
        y_onehot = np.zeros((y.shape[0], 26))
        for i, letter in enumerate(y):
            y_onehot[i, ord(letter) - ord('a')] = 1

        # Train the neural network model
        neural_net_model.fit(X_images, y_onehot, epochs=50, batch_size=32, verbose=0)

        # Store the trained model in the HangmanAPI object
        self.neural_net_model = neural_net_model

    def patterns_to_images(self, patterns, vocabulary):
        # Convert the patterns to images (2D arrays) with 0s and 1s
        max_pattern_length = max(len(pattern) for pattern in patterns)
        images = []
        for pattern in patterns:
            image = [0] * max_pattern_length
            for i, letter in enumerate(pattern):
                if letter in vocabulary:
                    image[i] = 1
            images.append(image)

        # Reshape the images to (num_samples, pattern_length, 1)
        images = np.array(images)
        return images.reshape(images.shape[0], images.shape[1], 1)
    
    def fine_tune_neural_network(self):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        # Initialize and configure the neural network model
        neural_net_model = Sequential()
        neural_net_model.add(Dense(128, input_dim=X.shape[1], activation='relu'))
        neural_net_model.add(Dense(64, activation='relu'))
        neural_net_model.add(Dense(26, activation='softmax'))

        # Compile the model with the 'adam' optimizer
        neural_net_model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])

        # Convert labels to one-hot encoding
        y_onehot = np.zeros((y.shape[0], 26))
        for i, letter in enumerate(y):
            y_onehot[i, ord(letter) - ord('a')] = 1

        # Fine-tune the neural network model
        neural_net_model.fit(X.toarray(), y_onehot, epochs=100, batch_size=32, verbose=0)

        # Store the fine-tuned model in the HangmanAPI object
        self.neural_net_model = neural_net_model

    def guess(self, word):
        # Clean the word so that we strip away the space characters
        # Replace "_" with "." as "." indicates any character in regular expressions
        clean_word = word[::2].replace("_", ".")

        # Find length of the passed word
        len_word = len(clean_word)

        # Grab current dictionary of possible words from self object, initialize a new possible words dictionary to empty
        current_dictionary = self.current_dictionary
        new_dictionary = []

        # Iterate through all of the words in the old plausible dictionary
        for dict_word in current_dictionary:
            # Continue if the word is not of the appropriate length
            if len(dict_word) != len_word:
                continue

            # If dictionary word is a possible match, then add it to the current dictionary
            if re.match(clean_word, dict_word):
                new_dictionary.append(dict_word)

        # Update Q-table state for the current word pattern
        current_state = clean_word

        # With probability epsilon, explore by choosing a random letter
        if random.random() < self.epsilon:
            # Randomly select a letter from the target labels
            guessed_letter = random.choice(self.target_labels)
        else:
            # With probability (1 - epsilon), exploit by choosing the letter with the highest Q-value
            # Choose the letter with the highest Q-value for the current state
            q_values_for_state = {action: self.q_table.get((current_state, action), 0.0) for action in self.target_labels}
            guessed_letter = max(q_values_for_state, key=q_values_for_state.get)

        # Update Q-table state for the next word pattern after making the guess
        next_word_pattern = word.replace("_", guessed_letter)
        next_state = next_word_pattern[::2].replace("_", ".")

        # Update the Q-table based on the observed reward and the next state
        # We don't have access to the actual reward in this implementation, so set it to 0 for now
        reward = 0
        self.update_q_table(current_state, guessed_letter, reward, next_state)

        # Overwrite old possible words dictionary with the updated version
        self.current_dictionary = new_dictionary

        # If there are no remaining words that match, default back to the ordering of the full dictionary
        if not new_dictionary:
            sorted_letter_count = self.full_dictionary_common_letter_sorted
        else:
            # Update the current dictionary with the new_dictionary
            self.current_dictionary = new_dictionary

            # Get the count of each letter at each position in the current dictionary
            letter_counts = [{letter: sum(1 for word in self.current_dictionary if word[i] == letter) for letter in self.target_labels}
                            for i in range(len(clean_word))]

            # Choose the character with the highest count at the next position
            next_position = len(self.guessed_letters)

            # If all letters have been guessed, use fallback guess from full dictionary ordering
            if next_position >= len(letter_counts):
                return self.ensemble_guess(clean_word)

            guessed_letter = max(letter_counts[next_position], key=letter_counts[next_position].get)

            # Remove the guessed letter from the possible letters in current_dictionary
            self.current_dictionary = [word for word in self.current_dictionary if guessed_letter not in word]

            return guessed_letter

        # Return the letter with the highest information gain that hasn't been guessed yet
        for letter, info_gain in sorted_letter_count:
            if letter not in self.guessed_letters:
                return letter

        # If all letters have been guessed, revert to ordering of full dictionary (fallback)
        return self.ensemble_guess(clean_word)

    def make_decision(self, word_pattern, models=['dt', 'rf', 'svm'], use_neural_net=True):
        # Clean the word pattern so that we strip away the space characters
        # Replace "_" with "." as "." indicates any character in regular expressions
        clean_word = word_pattern[::2].replace("_", ".")

        # Filter the full dictionary to get the current dictionary of possible words
        self.current_dictionary = [word for word in self.full_dictionary if re.match(clean_word, word)]

        # If there are no remaining words that match the pattern, return the fallback guess
        if not self.current_dictionary:
            return self.ensemble_guess(clean_word)

        # Extract features from the clean word pattern
        features = self.extract_features(clean_word)
        # Convert the features to a 2D array (samples x features) to use with the neural network
        pattern_features = np.array(features).reshape(1, -1)

        # Initialize a list to store the predictions from different models
        predictions = []

        # Initialize a list to store the classifiers for the ensemble
        classifiers = []

        # Add the desired models to the ensemble classifiers list
        if 'dt' in models:
            classifiers.append(('DecisionTree', self.decision_tree_model))
        if 'rf' in models:
            classifiers.append(('RandomForest', self.random_forest_model))
        if 'svm' in models:
            classifiers.append(('SVM', self.svm_model))

        # Create a VotingClassifier with the selected models
        voting_classifier = VotingClassifier(estimators=classifiers, voting='hard')

        # Train the ensemble classifier with the current dictionary
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])
        voting_classifier.fit(X, y)

        # Use the trained ensemble model to make a prediction
        ensemble_prediction = voting_classifier.predict(pattern_features)

        # Get the count of each letter at each position in the current dictionary
        letter_counts = [{letter: sum(1 for word in self.current_dictionary if word[i] == letter) for letter in self.target_labels}
                        for i in range(len(clean_word))]

        # Choose the character with the highest count at the next position
        next_position = len(self.guessed_letters)

        # If all letters have been guessed, use fallback guess from full dictionary ordering
        if next_position >= len(letter_counts):
            return self.ensemble_guess(clean_word)

        # Calculate the conditional probabilities of each letter given the word pattern
        letter_probabilities = {}
        total_letter_count = sum(letter_counts[next_position].values())
        for letter in string.ascii_lowercase:
            if letter not in self.guessed_letters:
                matching_words_count = letter_counts[next_position].get(letter, 0)
                conditional_probability = matching_words_count / total_letter_count
                # Calculate the information gain using entropy (log2)
                information_gain = -conditional_probability * math.log2(conditional_probability) if conditional_probability > 0 else 0
                letter_probabilities[letter] = information_gain

        # Choose the letter with the highest information gain as the next guess
        guessed_letter = max(letter_probabilities, key=letter_probabilities.get)

        return guessed_letter

    def compute_conditional_probabilities(self, word_pattern):
        # Count the occurrence of each letter in the possible words
        full_dict_string = "".join(self.current_dictionary)
        c = collections.Counter(full_dict_string)

        # Calculate the total count of letters in the possible words
        total_letter_count = sum(c.values())

        # Calculate the conditional probabilities of each letter given the word pattern
        letter_probabilities = {}
        for letter in string.ascii_lowercase:
            if letter not in self.guessed_letters:
                pattern_with_letter = word_pattern.replace(".", letter)
                matching_words_count = sum(1 for word in self.current_dictionary if re.match(pattern_with_letter, word))
                conditional_probability = matching_words_count / total_letter_count
                # Calculate the information gain using entropy (log2)
                information_gain = -conditional_probability * math.log2(conditional_probability) if conditional_probability > 0 else 0
                letter_probabilities[letter] = information_gain

        return letter_probabilities

    def build_dictionary(self, dictionary_file_location):
        text_file = open(dictionary_file_location, "r")
        full_dictionary = text_file.read().splitlines()
        text_file.close()
        return full_dictionary
        
  1. init(self, access_token=None, session=None, timeout=None): The constructor initializes the HangmanAPI object. It sets up the API URL, access token, and session for making HTTP requests to the Hangman game server. It also loads a full dictionary of words and initializes machine learning models (Decision Tree, Random Forest, SVM) and a Q-table for reinforcement learning.
  2. update_q_table(self, state, action, reward, next_state): This function updates the Q-values in the Q-table using the Q-learning update rule.
  3. extract_features(self, word_pattern): Extracts features from the given word pattern to be used by machine learning models for making guesses.
  4. hyperparameter_tuning(self): Performs hyperparameter tuning for the Decision Tree, Random Forest, and SVM models using Bayesian optimization.
  5. genetic_algorithm_tuning(self): Performs hyperparameter tuning for the Decision Tree, Random Forest, and SVM models using a genetic algorithm.
  6. train_all_models(self): Trains all the machine learning models, performs hyperparameter tuning, and trains a convolutional neural network (CNN) model.
  7. word_to_numeric(self, word): Converts a word pattern to a binary sequence of guessed (1) and not guessed (0) letters.
  8. ensemble_guess(self, word_pattern): Makes a guess for the given word pattern using an ensemble of Decision Tree, Random Forest, and SVM models.
  9. determine_hangman_url(self): Determines the Hangman game server URL to be used based on response times to different server URLs.
  10. train_neural_network(self): Trains a convolutional neural network (CNN) model using features extracted from the current dictionary of words.
  11. fine_tune_neural_network(self): Fine-tunes the neural network model using features extracted from the current dictionary of words.
  12. guess(self, word): Makes a guess for the given word pattern using the Q-learning algorithm and the current state of the game.
  13. make_decision(self, word_pattern, models=['dt', 'rf', 'svm'], use_neural_net=True): Makes a guess for the given word pattern using an ensemble of machine learning models and the Q-learning algorithm.
  14. compute_conditional_probabilities(self, word_pattern): Computes the conditional probabilities of each letter given the word pattern.
  15. build_dictionary(self, dictionary_file_location): Loads a full dictionary of words from a text file.

I am trying to improve the accuracy above 10% to atleast 50%. I tried implementing multiple techniques together and choosing the one that works best based on scoring mechanism and then hyper-tuning the parameters. I also tried reinforcement learning, yet the result is abysmally low.

All suggestions will be helpful.

$\endgroup$
1
  • 4
    $\begingroup$ What is the statistics question here? $\endgroup$ Jul 24, 2023 at 21:36

1 Answer 1

1
$\begingroup$

First time answering a question on Stack Exchange so bear with me. I haven't worked on this problem before but I worked on something similar with Wordle. Assuming that you implemented your code correctly, you are trying to break down a door with a battering ram when you could just try turning the nob. I think we kind of implicitly assume that ML/neural nets/Medium-blog-post-buzzword-technique will figure out what information and approach is required to solve a given problem, but in cases where we know what kind of method will be needed, we should just use that method.

In this problem, we want to guess a letter that is going to provide us with the most information about what the word is going to be. Your benchmark approach works on this logic, but there are slight differences better "guess the most frequent letter" and "guess the letter with the most information." Consider this fictitious example. Let's say we have one more letter and then we have to guess the word. We currently have

Q _ _ C _

The most frequent letters would probably be U or K in this situation, but that actually tells you very little about what the word is since there are several valid options:

Q U I C K

Q U A C K ...

If we guessed U or K and then had to guess the word, we basically might as well have not guessed either letter: we practically knew a U or K had to be there. However, if we guessed I, even if I wasn't there, we could reasonably assume that this implies that the word must be QUACK. Thus in this case guessing I actually contains more information about what the word is than U or K, even if they are more frequent. As you might have guessed, this toy example shows that an approach based on Information Theory will lead to better results than your benchmark algorithm. More importantly, since this kind of approach is designed to maximize the information of a guess, it should theoretically provide the most informative guesses possible and thus can (and I predict will) outperform your ML solution. Check out this 3Blue1Brown video for the Wordle example.

The key metric you need to find will be the entropy of each guess which will look like

$$ \text{Entropy of guess } X = \mathbb{E}[-\log_2(X)] $$

You want to do this for all possible guesses (so each remaining letter) until you find the best letter to guess. Read the wikipedia page to get the details about why we use this formula.

To sum up, while I like the ML approaches that you have tried, I think it is always best to pick the best tool for the job. Here, since we know what kind of criteria we should be selecting our guesses on (how much they help us figure out what the word is), we should use an approach (Entropy) that allows us to find the criteria and make the best choice. Notice how this is different than something like AlphaGo where the criteria for what makes the move "the best" is wildly unclear: we actually need the ML algorithm to tell us what is best. In a situation where we know what is best, solve for what is best. Only use black box methods when you don't know what should be in the box! Hope this helps :)

$\endgroup$
7
  • 2
    $\begingroup$ Your example is not entirely clear because guessing the most frequent letter does not lead to worse performance. The point of hangman is not to have the least number of guesses (which requires to have guesses with lots of information) but to have the least number of errors (which requires to have guesses with least probability of error).... $\endgroup$ Jul 25, 2023 at 7:50
  • 1
    $\begingroup$ ... A different example might work better, I imagine cases where guessing the most frequent letter is initially good, but not in the long run. I thought I could make an example with three letters where the two least frequent have less overlap, but that does not work, it needs to be more complex (and possibly there is not much gain possible with a different strategy). $\endgroup$ Jul 25, 2023 at 8:08
  • $\begingroup$ @SextusEmpiricus is correct, the example does not accurately portray the rules of hangman since guessing U would not hurt you (you do not loose guesses for correctly guessing letters). However, we could modify this example to be something like Q _ _ _ _. Here, U is still the most frequent letter, but there are some valid scrabble words that so not use a U, for example, QANAT(its valid for scrabble, good enough for me). Since 99% of words will have a U, guessing a U is not very informative. So you might expect more information from A or I. $\endgroup$
    – varkmiti
    Jul 25, 2023 at 12:45
  • $\begingroup$ Guessing 'U' might be less informative, but it will also be less likely to get you closer to being hanged. If 'U' is correct then you don't loose anything, if 'U' is false then you lost a turn, but you greatly eliminated the possibilities. $\endgroup$ Jul 25, 2023 at 16:26
  • 1
    $\begingroup$ An example could be the set ABD ABE ABF ABG ACH ACI CJK LMN. Say one hangs after making three mistakes, then guessing the highest frequency letter will give a success of 87.5% (the only potential failure occurs when the word is one of the first four). Guessing the highest entropy would start with B, and potentially A if B was wrong, leading to a success of 75% if the word is one of the first four, 100% if the word is the fifth or sixth, 50% if the word is the seventh or eight, and hence the entropy approach will perform worse (75% success on average). $\endgroup$ Jul 25, 2023 at 16:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.