5
\$\begingroup\$

I am very interested in the Monte Carlo AI.

I tried my best, still, this AI plays very badly.

This code "works" in the meaning that it does not crash, but the quality of play is extremely low.

Have I completly misunderstood the Monte Carlo AI or is there just a nasty bug in my code preventing it from playing correctly?

Can you understand every detail of code?

Creating an AI is quite complex a task so I would like to have the better style possible in order to keep the code understandable by everyone.

"""
TITLE: Monte Carlo AI that plays the 21 game
AUTHOR: Caridorc Tergilti
LICENSE: Creative Commons 3.0
CURRENT_STATE: The AI is currently very weak, I have no clue why.



General explanation:
This game is very,very easy, an AI can be disigned in
much simpler ways than this.

I designed a Monte Carlo AI because I want to learn about Monte Carlo AI-s
(You can find out more about Monte Carlo here:
https://en.wikipedia.org/wiki/Monte_Carlo_method)
and I want to discover if such an AI can actually be powerful in a game.

(Yes, there are many articles and papers on the internet that say that
Monte Carlo AI works but I want to prove it myself).

This programme is also Creative Commons so I hope that many people will enjoy
reading this programme to understand Monte Carlo AI better.



I will now explain my understanding of Monte Carlo AI.

1) The computer, knowing the rules, must decide what move is better.
2) FOREACH move the computer is going to simulate the move.
3) It will than play a big number of random games starting from the position after he made
the move.
4) Each move will be awarded a score equals to: wins / total_games.
5) The move with the highest score will be played.
"""

import random

WELCOME = """
21 game.
The total starts at 0.
Each player can chose 1, 2, or 3,
the number is than added to the total.
If when a player adds his number,
he makes the total equals or more than 21, he loses.
"""
DEPTH = 1000

def play_random_game(state):
    """
    This function plays a random game starting
    from a state.
    The opponent moves first.
    Returns 1 if you win,
    0 if you lose
    """
    if state >= 21:
        return 0 # You previously played a move that made you lose
    while 1:
        state += random.randint(0,3) # Opponent
        if state >= 21:
            return 1   # YOU WIN
        state += random.randint(0,3)
        if state >= 21:
            return 0   # YOU LOSE

def play_n_games(state,number):
    """
    Plays a certain number of random games,
    all starting from the state.
    Return the wins/total ratio.
    """
    outcomes = []
    for _ in range(number):
        outcomes.append(play_random_game(state))
    return sum(outcomes) / len(outcomes)


def AI(total):
    """
    This artificial intelligence uses Monte Carlo
    to make the best move.
    """
    list_of_outcomes = []
    possible_moves = [1,2,3]
    for move in possible_moves:
        list_of_outcomes.append(play_n_games(total,DEPTH))

    # Chose the move with the better score
    if max(list_of_outcomes) == list_of_outcomes[0]:
        return 1
    elif max(list_of_outcomes) == list_of_outcomes[1]:
        return 2
    elif max(list_of_outcomes) == list_of_outcomes[2]:
        return 3

def interface():
    """
    Allows the user to play the game
    against the AI.
    """
    total = 0
    print(WELCOME)
    while 1:
        user_number = int(input("Enter your number: "))
        assert (user_number in [1,2,3]),"Each player can chose 1, 2, or 3"
        total += user_number
        print("The total is " + str(total))
        print()
        if total >= 21:
            print("You lost")
            break
        total += AI(total)
        print("After the AI added a number")
        print("The total is " + str(total))
        print()
        if total >= 21:
            print("You won")
            break

if __name__ == "__main__":
    interface()
\$\endgroup\$
  • \$\begingroup\$ For those who are not aware of it: The ultimate strategy to this game is described here \$\endgroup\$ – Simon Forsberg Oct 24 '14 at 9:25
  • \$\begingroup\$ @SimonAndréForsberg to play the best possible you have to always make the number dividble by 4. Ex (2 -> 4) (13 -> 16). \$\endgroup\$ – Caridorc Oct 24 '14 at 13:16
  • \$\begingroup\$ Yes, I know, which is exactly what the wikipedia article says. Perhaps I should have linked directly to the 21 game part though. \$\endgroup\$ – Simon Forsberg Oct 24 '14 at 13:25
4
\$\begingroup\$

Your simulation assumes the human is playing randomly. This is not realistic. Consider the case when it's the human's turn at 19. A sensible player will certainly play 1 to force a win, but a random player has only 1/3 probability of doing the same. The simulation teaches the AI that the computer has an advantage in that situation, which is wrong.

If the rules of the game were changed so that every move must be made at random, your algorithm should be able to predict each player's probability of winning at any point. However, that would be a different game: a game of chance.

There's also a simple bug: you generate random moves by randint(0,3). This should of course be randint(1,3) because 0 is not a valid move.

\$\endgroup\$
  • \$\begingroup\$ I fixed the simple bug, Your simulation assumes the human is playing randomly in my understanding of Monte Carlo this must be assumed, also, making the human play non-randomly requires some hard-coded move_system that in my opinion is very near to just telling the computer how to play instead of letting it use the AI to understand the best strategy. \$\endgroup\$ – Caridorc Oct 24 '14 at 13:10
  • \$\begingroup\$ @Caridorc You should assume that the human is playing optimally (always think "what is the worst that could happen?"), so you should figure out the move for the human by using the Monte Carlo method. Oh, the recursion! \$\endgroup\$ – Simon Forsberg Oct 24 '14 at 13:28
  • \$\begingroup\$ @SimonAndréForsberg so you're telling me that something has to be hardcoded. \$\endgroup\$ – Caridorc Oct 24 '14 at 13:38
  • 1
    \$\begingroup\$ @Caridorc Not necessarily has to be, but either you implement it with the Monte Carlo as well (which I think would lead to a very slow method considering the recursion), or you use another kind of AI for it, or you do something "hardcoded". \$\endgroup\$ – Simon Forsberg Oct 24 '14 at 15:12

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.