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.
