2
\$\begingroup\$

The previous failed attempt

This question derives from this other question I made. In the previous question I tried to use a Monte Carlo algorithm; sadly it did not work.

I am doing an hardcoded AI

I therefore decided to try an hardcoded AI, but not for 21 game because it would have been too trivial, for a more general game similar to it. With the default settings you see below the game is equal to the 21 game.

Starting assumption

This AI was built completely by me, knowing from the start only that in the 21 game to play the best possible you have to always make the number dividble by 4. Ex (2 -> 4) (13 -> 16). I tried to come up with a more general answer.

Sometimes plays well sometimes not

This AI mysteriously plays well only in some cases, (example: END_VALUE = 21 MINIMUM_PLAYABLE_NUMBER = 1 MAX_PLAYABLE_NUMBER = 4).

Coding style part

If you know little about AI's and Math games, feel free to comment only about my coding style.

import random

END_VALUE = 21
MINIMUM_PLAYABLE_NUMBER = 1
MAX_PLAYABLE_NUMBER = 3
INTRODUCTION =     """
    In this game you and the computer
    alternate counting up to """ + str(END_VALUE) + """ chosing a number
    from """+ str(MINIMUM_PLAYABLE_NUMBER) + """ to """ + str(MAX_PLAYABLE_NUMBER) + """.
    The first that arrives to """ + str(END_VALUE) + """ LOSES.
    """

def dividers(n):
    """
    Given a number n returns all its dividers from 2 to the number

    >>> dividers(46)
    [2, 23, 46]
    >>> dividers(100)
    [2, 4, 5, 10, 20, 25, 50, 100]
    """
    return [i for i in range(2,n+1) if n%i==0]

def max_divider_less_than_or_equal_max_playable_number(n):
    """
    Core component of the AI.
    Tries to get the max divider less than MAX_PLAYABLE_NUMBER.
    If fails plays random.

    >>> MAX_PLAYABLE_NUMBER = 6
    >>> max_divider_less_than_or_equal_max_playable_number(65)
    5

    >>> MAX_PLAYABLE_NUMBER = 8
    >>> max_divider_less_than_or_equal_max_playable_number(17)
    [random] # note that 1 is not included in the dividers

    """
    try:
        return max([i for i in dividers(n) if i <= MAX_PLAYABLE_NUMBER])
    except ValueError:  # There are no divisors
        return random.randint(MINIMUM_PLAYABLE_NUMBER,MAX_PLAYABLE_NUMBER)


def AI(current_value):
    """
    Plays a move trying to make the user have to play
    at END_VALUE - 1 so that the player loses and he wins.
    He does so by playing the so that
    (current_value + move) % max_divider_less_ \
    than_or_equal_max_playable_number(END_VALUE - 1) == 0:
    is True.
    This AI misteriously works only for some values of the
    constants at the start.
    """
    moves = range(MINIMUM_PLAYABLE_NUMBER,MAX_PLAYABLE_NUMBER + 1)
    for move in moves:
        if (current_value + move) % max_divider_less_than_or_equal_max_playable_number(END_VALUE - 1) == 0:
            return move
    return random.randint(1,MAX_PLAYABLE_NUMBER)

def get_input_and_handle_errors():
    """
    Asks the user for input.
    Checks if it is a number, if it isn't raises error with message.
    Checks if it is in the correct range, sif it isn't raises error with message.
    """
    try:
        temp = int(input("Enter a number "))
    except ValueError:
        raise TypeError("You must enter a number.")

    if MINIMUM_PLAYABLE_NUMBER <= temp <= MAX_PLAYABLE_NUMBER:
        player_move = temp
    else:
        raise ValueError("You must play a number from " + str(MINIMUM_PLAYABLE_NUMBER) + " to " + str(MAX_PLAYABLE_NUMBER) + " both limits included.")

    return temp

def show_information_after_turn(value,who):
    print("After " + who + "'s turn value is " + str(value))

def check_if_game_over(value):
    if value >= END_VALUE:
        return True

def ask_user_if_he_wants_to_be_first():
    temp = input("Do you want to be first? ")

    # I check "y" in temp.lower()
    # instead of temp.lower() == "yes"
    # To give more freedom to the user
    if "y" in temp.lower():
        return True
    elif "n" in temp.lower():
        return False

def main():
    """
    Main interface.
    """
    value = 0
    print(INTRODUCTION)
    player_is_first = ask_user_if_he_wants_to_be_first()
    while 1:
        if not player_is_first:
            #############################################
            # Computer's turn
            value += AI(value)
            show_information_after_turn(value,"computer")
            if check_if_game_over(value):
                print("Computer has lost")
                break

        player_is_first = False

        ##############################################
        # Player's turn
        player_move = get_input_and_handle_errors()
        value += player_move
        show_information_after_turn(value,"player")
        if check_if_game_over(value):
            print("You have lost")
            break


if __name__ == "__main__":
    main()
\$\endgroup\$
  • 2
    \$\begingroup\$ You might find the behaviour less mysterious without a random component (or at least seed it for testing). \$\endgroup\$ – jonrsharpe Nov 3 '14 at 21:33
  • \$\begingroup\$ @jonrsharpe Indeed now that you make me think about it, if (END_VALUE - 1) is prime, fireworks happen (i.e. computer plays comletely randomly). Good comment. On a side note I would argue that if (END_VALUE - 1) is prime there is usually no way to force a win. \$\endgroup\$ – Caridorc Nov 3 '14 at 21:38
2
\$\begingroup\$

Since you have already acknowledged deficiencies in the AI algorithm, I'll just review the implementation.

You have a latent bug in the AI() function:

return random.randint(1,MAX_PLAYABLE_NUMBER)

The lower bound should be MINIMUM_PLAYABLE_NUMBER. I am puzzled by the naming inconsistency. The constants should be MIN_PLAYABLE_NUMBER and MAX_PLAYABLE_NUMBER, or they should be MINIMUM_PLAYABLE_NUMBER and MAXIMUM_PLAYABLE_NUMBER.

Conventionally, there should be a space after each comma. This is not explicitly stated in PEP 8, but implied in all of the examples.

To generate the introductory message, use str.format() instead of string concatenation.

There is a lot of similarity between the human and the AI. The main loop could therefore benefit from converting them into objects.

import itertools
import random
import string

END_VALUE = 21
MINIMUM_PLAYABLE_NUMBER = 1
MAX_PLAYABLE_NUMBER = 3

class AI:
    @property
    def name_possessive_case(self):
        return "computer's"

    @property
    def losing_message(self):
        return 'Computer has lost.'


    @staticmethod
    def _dividers(n):
        """
        Given a number n returns all its dividers from 2 to the number

        >>> dividers(46)
        [2, 23, 46]
        >>> dividers(100)
        [2, 4, 5, 10, 20, 25, 50, 100]
        """
        return [i for i in range(2,n+1) if n%i==0]

    @staticmethod
    def _max_divider_less_than_or_equal_max_playable_number(n):
        """
        Core component of the AI.
        Tries to get the max divider less than MAX_PLAYABLE_NUMBER.
        If fails plays random.

        >>> MAX_PLAYABLE_NUMBER = 6
        >>> _max_divider_less_than_or_equal_max_playable_number(65)
        5

        >>> MAX_PLAYABLE_NUMBER = 8
        >>> _max_divider_less_than_or_equal_max_playable_number(17)
        [random] # note that 1 is not included in the dividers

        """
        try:
            return max([i for i in AI._dividers(n) if i <= MAX_PLAYABLE_NUMBER])
        except ValueError:  # There are no divisors
            return random.randint(MINIMUM_PLAYABLE_NUMBER, MAX_PLAYABLE_NUMBER)


    def play(self, current_value):
        """
        Plays a move trying to make the user have to play
        at END_VALUE - 1 so that the player loses and he wins.
        He does so by playing the so that
        (current_value + move) % max_divider_less_ \
        than_or_equal_max_playable_number(END_VALUE - 1) == 0:
        is True.
        This AI misteriously works only for some values of the
        constants at the start.
        """
        moves = range(MINIMUM_PLAYABLE_NUMBER, MAX_PLAYABLE_NUMBER + 1)
        for move in moves:
            if (current_value + move) % AI._max_divider_less_than_or_equal_max_playable_number(END_VALUE - 1) == 0:
                return move
        return random.randint(MINIMUM_PLAYABLE_NUMBER, MAX_PLAYABLE_NUMBER)


class Human:
    @property
    def name_possessive_case(self):
        return 'your'

    @property
    def losing_message(self):
        return 'You have lost.'

    def play(self, current_value):
        """
        Asks the user for input.
        Checks if it is a number, if it isn't raises error with message.
        Checks if it is in the correct range, sif it isn't raises error with message.
        """
        try:
            temp = int(input("Enter a number "))
        except ValueError:
            raise TypeError("You must enter a number.")

        if MINIMUM_PLAYABLE_NUMBER <= temp <= MAX_PLAYABLE_NUMBER:
            player_move = temp
        else:
            raise ValueError("You must play a number from " + str(MINIMUM_PLAYABLE_NUMBER) + " to " + str(MAX_PLAYABLE_NUMBER) + " both limits included.")

        return temp

def determine_player_order():
    yes_no = input("Do you want to be first? ")

    if "y" in yes_no.lower():
        return itertools.cycle((Human(), AI()))
    else:
        return itertools.cycle((AI(), Human()))

def main():
    print("""
    In this game you and the computer
    alternate counting up to {END_VALUE} chosing a number
    from {MINIMUM_PLAYABLE_NUMBER} to {MAX_PLAYABLE_NUMBER}.
    The first that arrives to {END_VALUE} LOSES.
    """.format(END_VALUE=END_VALUE, MINIMUM_PLAYABLE_NUMBER=MINIMUM_PLAYABLE_NUMBER, MAX_PLAYABLE_NUMBER=MAX_PLAYABLE_NUMBER))

    value = 0
    turns = determine_player_order()
    for player in turns:
        value += player.play(value)
        print("After %s turn value is %d" % (player.name_possessive_case, value))
        if value >= END_VALUE:
            print(player.losing_message)
            break


if __name__ == "__main__":
    main()
\$\endgroup\$
  • \$\begingroup\$ You use @property def name_possessive_case(self): return "computer's" isn't it simpler and nicer to use name_possessive_case = "computer's" ? \$\endgroup\$ – Caridorc Nov 4 '14 at 13:04
3
\$\begingroup\$

Starting from the top, there is an inconsistency in constants' names:

MINIMUM_PLAYABLE_NUMBER
MAX_PLAYABLE_NUMBER

You could change the first one to MIN_PLAYABLE_NUMBER to solve this. The introduction string is concatenated by using the + operator which is not very efficient for multiple fragments. You could use format method of string objects instead.

INTRODUCTION = 'In this game you and the computer alternate counting up to '\
               '{0} chooing a number from {1} to {2}. The first that arrives '\
               'to {0} loses.'.format(END_VALUE, MINIMUM_PLAYABLE_NUMBER,
               MAX_PLAYABLE_NUMBER)

I am not sure why you are calling the dividers function so. Aren't they usually called factors? The name max_divider_less_than_or_equal_max_playable_number is not so pythonic. You have done this with other functions too. Also, the fact that you've broken every single step in to a function doesn't make anything easier.

The function named AI is just making a move. The calculation for doing so depends on other functions. I would recommend you wrap all of these inside a class because there are good reasons for doing so:

  • There is both data and behavior in this code.
  • Objects like players are very apparent. It is easy to follow an inheritance model
  • You can expand the class later (or even subclass them)
  • A huge benefit is that you can change the core 'move' method of a player from normal random moves to an intelligent move without changing the rest of the code.

There are many flaws with the current AI. You have noticed it yourself. Avoid something like this:

def show_information_after_turn(value,who):
    print("After " + who + "'s turn value is " + str(value))

Instead just do it when you want it to print. Again, you make things like this much better if you do it from a 'show' method inside your class, if you choose to do so.

One more thing - the main function is currently doing player_is_first = False to cycle between the players. You could make it more apparent by using:

from itertools import cycle
for player in cycle((player1, player2)):
    move(player)

This way you can avoid declaring any more variables and easy to change the order of players when you want to. All you have to do is to isolate the players in to a list or a tuple and change it's order. No while loops needed!

\$\endgroup\$
  • 1
    \$\begingroup\$ which is not very efficient for multiple fragments I really do not care about 0.001 seconds speedup, anyway I will use .format because it is nicer to see. \$\endgroup\$ – Caridorc Nov 4 '14 at 13:22
  • \$\begingroup\$ You should care about efficiency especially if the entire code is about Artificial Intelligence. The gain might be small, but continued usage would add up to a considerable difference in the outcome. This is just the same with the repeated function calls. They are expensive too. \$\endgroup\$ – Renae Lider Nov 4 '14 at 13:55
  • \$\begingroup\$ Premature optimization I am doing very little calculation, almost all is I/O, there no need to optimize here. \$\endgroup\$ – Caridorc Nov 4 '14 at 16:45
1
\$\begingroup\$

Coding Style

Line 6 (INTRODUCTION=...): Don't intermix values with strings. Instead, use str.format:

mystring = """
The value of {name} is {value}
""".format(name='something', value='something else')

Other than that, it looks pretty good. My only quibble might be that you have a lot of functions with very long names and very short bodies. While that's certainly a legitimate style, I find that it obscures what the code is actually doing. For example, get_input_and_handle_errors could really just be named handle_input and dividers is only called once, in max_divider_less_than_or_equal_max_playable_number, so it doesn't really need to be its own function.

\$\endgroup\$
1
\$\begingroup\$

Your attempt to generalize the 21 game winning strategy indicates you don't really understand how the strategy works. I'll try to explain. It hinges on two facts:

  1. Score 20 is a losing position, as you know.
  2. The sum of the minimal and the maximal moves is 4.

The second fact means that no matter what move the opponent makes, you can choose a move so that the two moves add up to 4. So, you can force the score to advance in steps of 4. If you can put your opponent in a position where score % 4 == 20 % 4 you can force them to lose.

The fact that 4 is a divisor of 20 is irrelevant, while your approach seems to be based on that fact.


Your program seems to play well with this modified AI function:

def AI(current_value):
    step = MINIMUM_PLAYABLE_NUMBER + MAX_PLAYABLE_NUMBER
    moves = range(MINIMUM_PLAYABLE_NUMBER,MAX_PLAYABLE_NUMBER + 1)
    for move in moves:
        if (current_value + move) % step == (END_VALUE - 1) % step:
            return move
    return random.randint(1,MAX_PLAYABLE_NUMBER)

It could still be improved. The loop basically solves the equation by brute force, while it could be rearranged to give the result directly.

\$\endgroup\$
  • \$\begingroup\$ Sorry for bad formatting in comment, I created this function based on yuor suggestion, is it rigth? def can_force_a_win(self,current_value): losing = END_VALUE - 1 minmaxsum = MIN_PLAYABLE_NUMBER + MIN_PLAYABLE_NUMBER if current_value % minmaxsum == (END_VALUE - 1) % minmaxsum: return True \$\endgroup\$ – Caridorc Nov 4 '14 at 17:10
  • \$\begingroup\$ @Caridorc Hard to say, but I added some code to my answer. \$\endgroup\$ – Janne Karila Nov 4 '14 at 19:46
  • \$\begingroup\$ I was only checking if it was possible to win, not actually winning. Thanks for adding the code later and giving me first a chance to do it myself. \$\endgroup\$ – Caridorc Nov 4 '14 at 20:40

Your Answer

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

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