3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.