In Dire Need of Ideas

[hhemken]

Void134,

I can save you a lot of time. The programming language will have no material effect on the AI's ability to play tic-tac-toe. It may have an effect on a particular programmer's ability to express an algorithm or code an efficient, problem-free program, but it is (and should be) transparent to the game itself.

I would suggest you write a program in the language you are most competent at so that language-specific concerns fade into the background. That's the way things are done in industry. Nobody wants to get bogged down in such things, and introducing a new programming language into a software development company is usually met with significant resistance and even derision because nobody wants to deal with it. Software development is hard enough without having to add extraneous and unnecessary problems. Believe me, I've been there.

Think of ways to vary the behavior of your AI through parameters, as I have described before, or with more than one significantly different algorithm or approach. That way you will be testing the AI directly instead of through something as hazy and difficult to measure as the programming language. That way you will be able to put an easy to read and straightforward table in your final results showing the effects of systematically varying parameters or approaches. It has to be something people will "get" just by looking at it. A colored bar chart would be even better. If people can roughly understand what you did and how things turned out by looking at your poster or display board for 15 seconds or less, your chances of winning or at least getting a good review will skyrocket.

Makes sense?

Heinz Hemken

[Void134]

When you say put it in parameters, what exactly do you mean? Like limiting the program?

[akbarkhan]

I would recommend that you stick with the advice given by the expert. One of the easiest ways to check the validity of an algorithm is to have the end-user use the system and to provide feedback (by seeing their performance and getting their opinion on how the system performs). This approach is straight forward and you can be certain that the results are valid.

On the other hand, theoretical measures can be developed to judge the effectiveness of an algorithm, but their validity is always questionable and seem to need to real world data to validate the theoretical approach. In other words, you are back to utilizing end-users to test your software! Bottom-line is that you gained very little. Theoretical approaches are best used if end-user testing is not practical.

[hhemken]

Void134,

What programming language are you most comfortable with? I can help you figure out how to receive runtime parameters for your program to choose among options.

Heinz Hemken

[Void134]

I guess I will use Python. So how can i set parameters for that? And for HTML5,Javascript,CC3 possibly?

[hhemken]

Void123,


Assuming you are writng a command-line python script, you would put something like this in the file that you invoke on the command line (the one with main() ):

Code: Select all

import getopt

def usage():
    print '''\
Usage: %s [Options] [filename1 [filename2 [...]]]

   Explain program here.

   NOTE: Put any special notes here.

   Options
        -h, --help - Print this message and exit

        -l, --l_option [string] - An option that begins with the letter l, so we use -l on the
                                    command line. We tell the user it is expected to be a string.

        -s, --s_option [integer] - An option that begins with the letter s, so we use -s on the
                                    command line. We tell the user it is expected to be an integer.

        -t, --tmp-dir [string] - Path to the directory where temporary files will be created. Since
                                    tmp begins with a t, we use -t

''' % sys.argv[0]

def main(argv=None):
    if argv is None:
        argv = sys.argv

    s_option = 0
    tmp_dir  = '/tmp'
    l_option = None

    # check command line options and whether file names were specified, altering filenames as appropriate
    try:
        opts, args = getopt.getopt(sys.argv[1:], "ht:s:l:", ["help", "tmp-dir=", "s_option=", "l_option="])
    except getopt.GetoptError, err:
        # print help information and exit:
        print str(err) # will print something like "option -a not recognized"
        usage()
        sys.exit(2)
    for o, a in opts:
        if o in ("-h", "--help"):
            usage()
            return(0)
        elif o in ('-s', '--s_option'):
            try:
                s_option = int(a)
            except exceptions.ValueError:
                print"my_program_name: Bad integer argument to -s or --s_option"
                usage()
                return(1)
        elif o in ('-t', '--tmp-dir'):
            try:
                tmp_dir = a
                # make sure the directory actually exists
                os.statvfs(tmp_dir)
            except OSError:
                print"my_program_name: Unable to statvfs the -t or --tmp-dir argument '%s'", tmp_dir
                usage()
                return(1)
        elif o in ('-l', '--l_option'):
            #
            l_option    = a
        else:
            assert False, "unhandled option"

    try:
        if args:
            for fn in args:
                try:
                    with file(fn) as fobj:
                        print"my_program_name: reading from file: %s" % (fn)
                        # call a function that does something with file fn
                except IOError, e:
                    print"my_program_name: Error reading file: %s: %s" % (fn, str(e))
                    return(1)
        else:
            print"my_program_name: reading from stdin"
            # call a function that reads from standard input and does something with the info
    except Exception, e:
        sys.stderr.write(str(e) + "\n")
        return(1)

Note that I cut and pasted this from an actual program, and edited it to make it brief and more generic, so it may have a few errors you'll have to fix if you put it in an actual program. You'll have to fill it in with your game-specific stuff.

If you are doing something in a web page, you will use javascript and HTML to provide text boxes, drop-down selection lists, radio buttons, check boxes, etc. for the user to type something in or select from predefined choices. If you are using python on the back end, then the above command line example would change to something using CGI data. See for example http://docs.python.org/2/library/cgi.html and http://code.activestate.com/recipes/275150/ for more details.

I'm not familiar with CC3, and I would caution you against becoming an expert with a tool that may or may not be there 5 or 10 years from now. Python, HTML, and javascript definitely will be around. CC3? Who knows. Skills you become proficient at should last you for a long time. You'd be surprised how often they come in handy over the years.

Does this shed some light?


Heinz Hemken

[Void134]

This helped quite a bit thank you. If I have any future questions i will post it in this thread I guess.

[hhemken]

Void134,

Yes, please keep us posted on this thread so that future students can also see everything in one place.

Thanks and best of luck to you, I hope you win!


Heinz Hemken

[Void134]

So one neat and orderly question:

What effect do different parameters set and approaches to build the program have on the artificial intelligence's ability to play and approach with moves?

[hhemken]

Void134,

I sense some ambiguity in the phrasing. How about:

What effects do different artificial intelligence approaches, and tunable parameters for each, have on a game's ability to play and choose moves?

Something like that where you indicate 1) that you are using more than one AI approach, 2) tunable input parameters for each, and 3) that different combinations of AI approaches and parameter values will somehow affect game play and the ability of the AI to win against humans.

"Tunable" in this sense means that an input parameter can be given different values, and that you can at least in principle find a set of parameter values that make the AI approach optimally able to play the game well. For example:

Code: Select all

start_my_ai_approach("hi", 25, 16.8);
start_my_ai_approach("med", 47, 1.6);
start_my_ai_approach("lo", 8, 5.0);
start_my_ai_approach("hi", 70, 0.35);

If you start a certain AI approach in your game program by calling the start_my_ai_approach() function with values that came in from selection boxes, radio buttons, or whatever from the web page, then these examples represent four arbitrary sets of parameters that a user could try out while playing the game on four separate occasions. The premise of your project is that these different sets of input parameters should significantly affect game play. By tweaking or "tuning" the values, you might be able to make the game maximally able to win games. Conversely, there should be parameter sets where the game is guaranteed to be so stupid as to essentially never win.

The trick will be to identify the parts of your AI approaches that can have such choices. The string inputs "hi", "med", and "lo" (or for example "the rick james method", "the berkshire-geneva method", or "default") are good when there are three distinct levels or categories of something or other that do not lend themselves well to integers or floating point values. Integers are good when you have an algorithm that performs better the more loop iterations it performs at a certain point, such as how many moves ahead it looks at or how many possibilities it checks per move. Higher numbers mean better game play but slower performance. Floating point numbers are good when there are certain constants or coefficients that are used somewhere in the algorithm. Often it is the case that very high or very low values will cause the algorithm to do stupid things, and it becomes desirable to search for an optimum by actually playing the game with different values.

How does that sound?


Heinz Hemken

[Void134]

Sounds good

Thank you

[Void134]

I understand the experiment and all, but how am i supposed to analyze and measure the results? I am a little unclear on that.

[Void134]

bumping the topic

[hhemken]

Void134,

A statistical way would be:

1) select a panel of human players and have each one play your game 10 or 20 times (or choose a more convenient number)
2) for each play session, assign the player a set of parameter settings
3) have the player play the game and get its result. At very least, it would be "won," "lost," or "tied." If there is a score of some kind, also note it.

You should probably test each set of input parameters 3 times with 3 different players to avoid skewing the results based on player ability. The three games can be called something like a play session set, or game replicates set, or something you make up for the sake of discussion. Once you have the results of all of the games, you should be able to create bar charts, scatter plots, or whatever showing what effect the parameters have on the AI's ability to play the game. You can chart parameters individually in e.g. bar charts or two at a time, e.g. scatter plots where the color of the dots indicates "won," "lost," or "tied." Think about it and discuss it with your science teacher. You should be able to show a few (3 or 4, say) on your display board that clearly show that some parameters drastically affect the AI and others less so or not at all. You will also be able to make charts for individual players to see if some are better than others and whether that skews the results.

Think graphically, since that is what people will see. You may also generate simple statistics like average number of games won in the 3 play session set for certain input parameter ranges. Since the play session set consists of at least 3 game attempts with the same parameters you can calculate the standard deviation, but that might be complicating things. I think that the graphical display of data in colored charts should show clear tendencies. You would have to propose rational explanations for the results.

Would that work?


Heinz Hemken

[Void134]

Code: Select all

# Tic Tac Toe

import random

def drawBoard(board):
    # This function prints out the board that it was passed.

    # "board" is a list of 10 strings representing the board (ignore index 0)
    print('   |   |')
    print(' ' + board[7] + ' | ' + board[8] + ' | ' + board[9])
    print('   |   |')
    print('-----------')
    print('   |   |')
    print(' ' + board[4] + ' | ' + board[5] + ' | ' + board[6])
    print('   |   |')
    print('-----------')
    print('   |   |')
    print(' ' + board[1] + ' | ' + board[2] + ' | ' + board[3])
    print('   |   |')

def inputPlayerLetter():
    # Let's the player type which letter they want to be.
    # Returns a list with the player's letter as the first item, and the computer's letter as the second.
    letter = ''
    while not (letter == 'X' or letter == 'O'):
        print('Do you want to be X or O?')
        letter = input().upper()

    # the first element in the tuple is the player's letter, the second is the computer's letter.
    if letter == 'X':
        return ['X', 'O']
    else:
        return ['O', 'X']

def whoGoesFirst():
    # Randomly choose the player who goes first.
    if random.randint(0, 1) == 0:
        return 'computer'
    else:
        return 'player'

def playAgain():
    # This function returns True if the player wants to play again, otherwise it returns False.
    print('Do you want to play again? (yes or no)')
    return input().lower().startswith('y')

def makeMove(board, letter, move):
    board[move] = letter

def isWinner(bo, le):
    # Given a board and a player's letter, this function returns True if that player has won.
    # We use bo instead of board and le instead of letter so we don't have to type as much.
    return ((bo[7] == le and bo[8] == le and bo[9] == le) or # across the top
    (bo[4] == le and bo[5] == le and bo[6] == le) or # across the middle
    (bo[1] == le and bo[2] == le and bo[3] == le) or # across the bottom
    (bo[7] == le and bo[4] == le and bo[1] == le) or # down the left side
    (bo[8] == le and bo[5] == le and bo[2] == le) or # down the middle
    (bo[9] == le and bo[6] == le and bo[3] == le) or # down the right side
    (bo[7] == le and bo[5] == le and bo[3] == le) or # diagonal
    (bo[9] == le and bo[5] == le and bo[1] == le)) # diagonal

def getBoardCopy(board):
    # Make a duplicate of the board list and return it the duplicate.
    dupeBoard = []

    for i in board:
        dupeBoard.append(i)

    return dupeBoard

def isSpaceFree(board, move):
    # Return true if the passed move is free on the passed board.
    return board[move] == ' '

def getPlayerMove(board):
    # Let the player type in his move.
    move = ' '
    while move not in '1 2 3 4 5 6 7 8 9'.split() or not isSpaceFree(board, int(move)):
        print('What is your next move? (1-9)')
        move = input()
    return int(move)

def chooseRandomMoveFromList(board, movesList):
    # Returns a valid move from the passed list on the passed board.
    # Returns None if there is no valid move.
    possibleMoves = []
    for i in movesList:
        if isSpaceFree(board, i):
            possibleMoves.append(i)

    if len(possibleMoves) != 0:
        return random.choice(possibleMoves)
    else:
        return None

def getComputerMove(board, computerLetter):
    # Given a board and the computer's letter, determine where to move and return that move.
    if computerLetter == 'X':
        playerLetter = 'O'
    else:
        playerLetter = 'X'

    # Here is our algorithm for our Tic Tac Toe AI:
    # First, check if we can win in the next move
    for i in range(1, 10):
        copy = getBoardCopy(board)
        if isSpaceFree(copy, i):
            makeMove(copy, computerLetter, i)
            if isWinner(copy, computerLetter):
                return i

    # Check if the player could win on his next move, and block them.
    for i in range(1, 10):
        copy = getBoardCopy(board)
        if isSpaceFree(copy, i):
            makeMove(copy, playerLetter, i)
            if isWinner(copy, playerLetter):
                return i

    # Try to take one of the corners, if they are free.
    move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
    if move != None:
        return move

    # Try to take the center, if it is free.
    if isSpaceFree(board, 5):
        return 5

    # Move on one of the sides.
    return chooseRandomMoveFromList(board, [2, 4, 6, 8])

def isBoardFull(board):
    # Return True if every space on the board has been taken. Otherwise return False.
    for i in range(1, 10):
        if isSpaceFree(board, i):
            return False
    return True


print('Welcome to Tic Tac Toe!')

while True:
    # Reset the board
    theBoard = [' '] * 10
    playerLetter, computerLetter = inputPlayerLetter()
    turn = whoGoesFirst()
    print('The ' + turn + ' will go first.')
    gameIsPlaying = True

    while gameIsPlaying:
        if turn == 'player':
            # Player's turn.
            drawBoard(theBoard)
            move = getPlayerMove(theBoard)
            makeMove(theBoard, playerLetter, move)

            if isWinner(theBoard, playerLetter):
                drawBoard(theBoard)
                print('Hooray! You have won the game!')
                gameIsPlaying = False
            else:
                if isBoardFull(theBoard):
                    drawBoard(theBoard)
                    print('The game is a tie!')
                    break
                else:
                    turn = 'computer'

        else:
            # Computer's turn.
            move = getComputerMove(theBoard, computerLetter)
            makeMove(theBoard, computerLetter, move)

            if isWinner(theBoard, computerLetter):
                drawBoard(theBoard)
                print('The computer has beaten you! You lose.')
                gameIsPlaying = False
            else:
                if isBoardFull(theBoard):
                    drawBoard(theBoard)
                    print('The game is a tie!')
                    break
                else:
                    turn = 'player'

    if not playAgain():
        break

This is the final basic program.
This is Python 3.3.0 just a reminder. I am asking where i should input different parameters. I suspect it will be in the area where it will look for a good move.