# Simple Number Game with AI

I have created a simple game and AI in Python.

Rules of the game:

• There are 11 spaces for digits, 9 that are used and 2 that are discarded
• On each turn, a digit (0 - 9) is chosen and placed in a space.
• When all spaces are filled, the number formed by the concatenation of all used spaces is the score.
• The goal is to get the highest score (or lowest, depending).

Example game:

State: _________ | __

Digit: 5

Where to go? 5

State: _____5___ | __

--------------------

Digit: 6

Where to go? 7

State: _____5_6_ | __

--------------------

Digit: 1

Where to go? 2

State: __1__5_6_ | __

--------------------

Digit: 5

Where to go? 0

State: 5_1__5_6_ | __

--------------------

Digit: 5

Where to go? 1

State: 551__5_6_ | __

--------------------

Digit: 4

Where to go? 4

State: 551_45_6_ | __

--------------------

Digit: 2

Where to go? 3

State: 551245_6_ | __

--------------------

Digit: 5

Where to go? 6

State: 55124556_ | __

--------------------

Digit: 9

Where to go? 8

State: 551245569 | __

--------------------

Digit: 4

Where to go? 9

State: 551245569 | 4_

--------------------

Digit: 0

Where to go? 10

State: 551245569 | 40

--------------------

Final score: 551245569


Code:

import random
import abc

DIGITS = list(range(10)) # 0 - 9
BASE_DIGIT_WEIGHT = 5.5
DIGIT_WEIGHT_CHANGE = 0.5 # farther left digits worth more

USED_DIGITS = 9
DISCARD_DIGITS = 2

LOW_BETTER = False

DEPTH = 3

class Game():
"""
A class representing a game state.
"""
def __init__(self, used, discard, digits = None, weights=None):
self.used = used
self.discard = discard
self.mid = (self.used + self.discard) / 2

if digits is None:
digits = [None] * (used + discard)

self.digits = digits

if weights is None:
weights = (
[
BASE_DIGIT_WEIGHT + DIGIT_WEIGHT_CHANGE * (self.mid - ind)
for ind in range(used + discard)
])

self.weights = weights

def empty_spaces(self):
"""
Find and yield the empty spaces in the game.
"""
for ind, digit in enumerate(self.digits):
if digit is None:
yield ind

def over(self):
"""
Check if the game has ended.
"""
return None not in self.digits

def score(self):
"""
Calculate a hueristic score for the game.
"""
digits = [
empty_score
if digit is None else
digit
for digit, empty_score in zip(self.digits, self.weights)
]

digits = digits[:self.used]

result = 0
mul = 1
for digit in reversed(digits):
result += mul * digit
mul *= 10

return result

def move(self, digit, pos):
"""
Return a copy of the game with digit added in index pos.
"""
if self.digits[pos] is None:
new_digits = self.digits[:]
new_digits[pos] = digit
new_game = Game(self.used, self.discard, new_digits, self.weights)
return new_game
else:
raise ValueError("Moved in filled space ")

def __str__(self):
"""
Convert a game into a human-readable string.
"""
result = []

for ind in range(self.used):
digit = self.digits[ind]
if digit is None:
result.append("_")
else:
result.append(str(digit))

result.append(" | ")

for ind in range(self.used, self.used + self.discard):
digit = self.digits[ind]
if digit is None:
result.append("_")
else:
result.append(str(digit))

return "".join(result)

class DigitPicker(abc.ABC):
"""
Template for a digit picker
"""
@abc.abstractmethod
def get_digit(self):
raise TypeError("DigitPicker can't choose a digit")

class RandomDigitPicker(DigitPicker):
"""
A random digit picker.
"""
def get_digit(self):
"""
Pick a random digit.
"""
return random.choice(DIGITS)

class UserDigitPicker(DigitPicker):
"""
Digit picker using user input.
"""
def get_digit(self):
"""
Pick a digit with user input.
"""
return int(input("What digit?"))

class GamePlayer():
"""
Template for a game player.
"""
@abc.abstractmethod
def get_pos(self, game, digit):
raise TypeError("Player doesn't know how to move")

class UserPlayer(GamePlayer):
"""
A game player that uses user input.
"""
def get_pos(self, game, digit):
"""
Get a position to move from the user.
"""
pos = int(input("Where to go?"))
print()
return pos

class AIPlayer(GamePlayer):
"""
An AI game player.
"""
def __init__(self, depth):
self.depth = depth

def score(self, game, digit, depth):
"""
Get the max score and optimal move for a game and digit.
"""
if depth == 0 or game.over():
return game.score(), None

best_score = float("-inf")

for pos in game.empty_spaces():
curr_sum = 0

for new_digit in DIGITS:
score, _ = self.score(game.move(digit, pos), new_digit, depth - 1)
curr_sum += score

avg = curr_sum / len(DIGITS)

if LOW_BETTER:
if avg < best_score:
best_score = avg
best_pos = pos
else:
if avg > best_score:
best_score = avg
best_pos = pos

return best_score, best_pos

def get_pos(self, game, digit):
"""
Get the optimal move for a game and digit.
"""
_, pos = self.score(game, digit, self.depth)
return pos

class GameHandler():
"""
Handles a game with a player and picker.
"""
def __init__(self, game, player, picker, io=False):
self.game = game
self.player = player
self.picker = picker
self.io = io

def play(self):
"""
Plays a game.
"""
game = self.game # so it can be re-used

if self.io:
print("State:", game)
print()

while not game.over():
digit = self.picker.get_digit()

if self.io:
print("Digit:", digit)
print()

pos = self.player.get_pos(game, digit)
game = game.move(digit, pos)

if self.io:
print("State:", game)
print("\n" + "-" * 20 + "\n")

score = game.score()

if self.io:
print("Final score:", score)

return score

def main():
tot_score = 0

game = Game(USED_DIGITS, DISCARD_DIGITS)
player = UserPlayer() # or AIPlayer(DEPTH)
picker = RandomDigitPicker() # or UserDigitPicker

handler = GameHandler(game, player, picker, io=True) # io is whether or not to print stuff

print(handler.play())

if __name__ == "__main__":
main()


Problems:

• I am slightly concerned about the DigitPickers, should I be using an abstract base class for one method?
• It's very slow for depths > 3, are there any optimizations I can make? I thought about pruning but I am not sure how it works for expectimax.
• Should I be using separate lists for the used and discarded digits?

I am aware the input format is kind of cumbersome but the AI is more my focus here.