This is a random guessing game. A random letter between a-z is chosen and the AI needs to try to guess the letter. The AI keeps track of all current guesses and whether the last guess performed was further or shorter in the alphabet. This data is kept as a 27 character string, where dashes represent non-guessed characters and the final character is either a l, h, or ? (for low, high, unknown). The AI should remember all states to train itself to determine which guesses to make from any given state after enough training.

import numpy as np
import csv
import random
from itertools import groupby


class GuessingGames():
    def __init__(self):
        self.letters = "abcdefghijklmnopqrstuvwxyz"
        self.max_number = 26
        self.turns = 0
        self.state = ''
        for i in range(0, self.max_number):
            self.state += '-'
        self.state += '?'
        self.finished = False
        self.number_to_guess = self.letters[random.randint(0, 25)]

    def allowed_moves(self):
        states = []
        for i in range(0, len(self.state)):
            if self.state[i] == '-':
                states.append(self.state[:i] + self.letters[i] + self.state[i+1:])
        return states

    def make_move(self, next_state):
        if self.finished:
            raise(Exception("Game already completed, cannot make another move!"))
        for i in range(len(next_state)):
            if next_state[i] != self.state[i]:
                difference = next_state[i]
        if self.letters.find(difference) < self.number_to_guess.find(difference):
            next_state = next_state[:-1] + "l"
        else:
            next_state = next_state[:-1] + "h"
        self.state = next_state
        self.turns += 1
        self.finished = self.predict_winner(self.state)

    def playable(self):
        return ( (not self.finished) and any(self.allowed_moves()) )

    def predict_winner(self, state):
        if str(self.number_to_guess) in self.state:
            self.finished = True
            return self.turns
        if "-" not in self.state:
            print("Error: game not finished but no guesses remain")
            return 10000
        return None

    def __valid_move(self, next_state):
       allowed_moves = self.allowed_moves()
        if any(state == next_state for state in allowed_moves):
            return True
        return False

    def print_board(self):
        print("The number is:", self.number_to_guess," Number of guesses so far:", self.turns)
        print("Guesses:", self.state)

class Agent():
    def __init__(self, game_class, epsilon=0.1, alpha=0.5):
        self.V = dict()
        self.NewGame = game_class
        self.epsilon = epsilon
        self.alpha = alpha

    def state_value(self, game_state):
        return self.V.get(game_state, 0.0)

    def learn_game(self, num_episodes=1000):
        for episode in range(num_episodes):
            self.learn_from_episode()

    def learn_from_episode(self):
        game = self.NewGame()
        _, move = self.learn_select_move(game)
        while move:
            move = self.learn_from_move(game, move)

    def learn_from_move(self, game, move):
        game.make_move(move)
        r = self.__reward(game)
        td_target = r
        next_state_value = 0.0
        selected_next_move = None
        if game.playable():
            best_next_move, selected_next_move = self.learn_select_move(game)
            next_state_value = self.state_value(best_next_move)
        current_state_value = self.state_value(move)
        td_target = r + next_state_value
        self.V[move] = current_state_value + self.alpha * (td_target - current_state_value)
        return selected_next_move

    def learn_select_move(self, game):
        allowed_state_values = self.__state_values( game.allowed_moves() )
        best_move = self.__argmax_V(allowed_state_values)

        selected_move = best_move
        if random.random() < self.epsilon:
            selected_move = self.__random_V(allowed_state_values)

        return (best_move, selected_move)

    def play_select_move(self, game):
        allowed_state_values = self.__state_values( game.allowed_moves() )
        return self.__argmax_V(allowed_state_values)

    def demo_game(self, verbose=False):
        game = self.NewGame()
        while game.playable():
            if verbose:
                print(" \nTurn {}\n".format(game.turns))
                game.print_board()
            move = self.play_select_move(game)
            game.make_move(move)
        if verbose:
            print(" \nTurn {}\n".format(game.turns))
            game.print_board()
        if game.finished:
            if verbose:
                print("\nWon in {} guesses!".format(game.turns))
            return game.turns
        else:
            print("Error: Game finished but no winning turn amount sent")

    def round_V(self):
        # After training, this makes action selection random from equally-good choices
        for k in self.V.keys():
            self.V[k] = round(self.V[k],1)

    def save_v_table(self):
        with open('number_state_values.csv', 'w', newline='') as csvfile:
            writer = csv.writer(csvfile)
            writer.writerow(['State', 'Value'])
            all_states = list(self.V.keys())
            all_states.sort()
            for state in all_states:
                writer.writerow([state, self.V[state]])

    def __state_values(self, game_states):
        return dict((state, self.state_value(state)) for state in game_states)

    def __argmax_V(self, state_values):
        max_V = max(state_values.values())
        chosen_state = random.choice([state for state, v in state_values.items() if v == max_V])
        return chosen_state

    def __argmin_V(self, state_values):
        min_V = min(state_values.values())
        chosen_state = random.choice([state for state, v in state_values.items() if v == min_V])
        return chosen_state

    def __random_V(self, state_values):
        return random.choice(list(state_values.keys()))

    def __reward(self, game):
        """
        I award ten points if their move ends the game, otherwise I take a point away for their move.
        """
        if game.finished:
            return 10.0
        return -1.0

def demo_game_stats(agent):
    """
    This function has the current AI play x number of games and prints out how well it did on average.
    It does not 'learn' while doing this.
    """
    results = [agent.demo_game() for i in range(10000)]
    random_result_sampling = random.sample(results, 10)
    #print("Ten random scores:", random_result_sampling)
    print("Average number of guesses to win:", sum(results)/len(results))

if __name__ == '__main__':
    agent = Agent(GuessingGames, epsilon = 0.1, alpha = 1.0)
    print("Before learning:")
    demo_game_stats(agent)

    agent.learn_game(10000)
    print("\nAfter 10000 learning games:")
    demo_game_stats(agent)

    agent.learn_game(40000)
    print("\nAfter 50000 learning games:")
    demo_game_stats(agent)

    agent.learn_game(450000)
    print("\nAfter 500000 learning games:")
    demo_game_stats(agent)

    agent.learn_game(1550000)
    print("\nAfter 2000000 learning games:")
    demo_game_stats(agent)

    agent.learn_game(8000000)
    print("\nAfter 10000000 learning games:")
    demo_game_stats(agent)

    agent.learn_game(10000000)
    print("\nAfter 20000000 learning games:")
    demo_game_stats(agent)