COMS W4701 Artificial Intelligence Fall 2013 Assignment 3: Battle of the Gomoku Agents Due: 11:59:59 EST November 21st 2013 AD The intent of apply the adversarial search techniques we discussed in class by constructing your first game playing agent. For this project, you will be implementing an agent which is capable of playing the game Gomoku. The Game The game has two players: x and o. The players alternate turns, with player x moving first at the beginning of each game. The game board consists of n by n intersections; when empty these can be represented with a period ".". Each turn a player places one of his or her game pieces at an unoccupied intersection, after which the position is marked with their stone character. For the sake of consistency, please index your board positions starting from 0,0 in the upper left hand corner, i.e., for n=3: (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) The game ends when one of the following conditions is met: - One of the players creates an unbroken chain of m *and exactly m* pieces. The player who has formed the m stone chain wins. - There are no open intersections because the game board is completely full of stones, in which case the outcome is a draw. Your player will be required to run with a set total amount of time. A useful function to consider for this assignment is (get-internal-real-time). It is also useful to think of dividing the time you have left equally among the subtrees you want to search, stopping along any path when you're coming close to running out of the allocated time. If you do not select a move before time expires, your move is forfeit. When initially run, your program should take the game board dimension n, winning chain length m, and move selection time limit s in seconds as input. You should also include a mechanism for deciding if the agent will play x and move first or play o and hence move second. Your player function should take a game state as input and return a move in the format [row column]. If you cannot move, return [-1 -1]. TIf you return an illegal move, the other player (and/or the TA) will detect it and you will lose. Your program should support three modes of play: - Mode one will accept moves through stdin as input and return moves and an updated board to stdout as output. You'll use this version in the Gomoku agent tournament! - In mode two, your agent will play against an agent who moves randomly, outputting the selected moves and an updated board state to the screen as output. - In mode three, your agent will play against itself, outputting the selected moves and an updated board state to the screen as output. All cases should detect win conditions and output the appropriate game outcome when detected. Note that the specific format which you use to output your game state is up to you, since this will not be used as input to your opponent's program. I'd suggest using "x y" (without the quotes) as a standard for formatting move inputs and outputs. While the format which you output your moves in (i.e. "x,y' "[x,y]' (y x)") in also up to you, it may be beneficial for you and your opponent to agree upon a shared format in advance. If you choose to play your opponent via a network connection, you *must* agree on a move format for both input and output in advance. See the tournament section for more details. What to turn in (60% of your grade is proper functioning code, 20% of your grade is the writeup, 20% available in the tournament!) - A single code file named player-your-account containing: - Your name and uni at the top - A time-based version of alpha-beta which plays Gomoku - A good evaluation function for your player - Any supporting code - A single writeup file containing: - Your name and uni at the top - A paragraph or two justifying the evaluation function you designed. You may wish to talk about: - Why it provides an appropriate approximation to the "goodness" of a particular board. - How it balances quickness of execution (i.e. enables deeper search) vs. accuracy. - How you determined it was a good evaluation function. - The efficiency of your implementation. - Any extensions you implemented - A paragraph describing the outcome of you challenging your own creation in mode one five times. - A paragraph describing the outcome of running your agent in mode two five times. - A paragraph describing the outcome of running your agent in mode three five times. Collaboration Policy Before turning in your assignment, you are allowed to try your player out against the players written by your fellow students; however, you are quite explicitly not allowed to look at any code (except what we provide) or descriptions of code for these games (or any games that are similar). You are, of course, allowed to play the games yourself or to play against humans. Again, do not let your discussions turn into any descriptions of an algorithm. The Tournament If you wish, your Gomoku game playing agent will be entered into a competition with the other players submitted by the class. Winners of the competition will receive credit for the assignment as follows: - 1st round: Losers 5 points, winners 10 - 2nd round: Losers 2 more points, winners 3 - 3rd round: Loosers 1 more point, winners 2 - 4th round and onward: Losers 1 more point, winners 2 - Final grand winner gets a final 3 points (If there are fewer than 4 rounds, points will be adjusted so the grand winner can get 100 points. If there are more rounds, enjoy the extra points!) More Tournament Details: The tournament will be held starting at noon on Friday 11/22 in the Clic lab. Participants will be paired up, and a physical source of entropy will be used to determine which player is black and which player is x. Once paired, each players' agent will take turns making moves and entering the opponent's move as "human" input via mode one. To demonstrate: 0) Both players execute their agent programs with complimentary parameters. 1) Player x's agent outputs a move. 2) Player o's agent inputs x's move. 3) Player o's agent outputs a move. 4) Player x's agent inputs o's move. 5)Player x's agent outputs a move. ... n) One player wins. OPTIONAL: Connecting agents via a network If you would like, you can download the following shell scripts and utilize them to connect to an opponent via a network connection: https://www.cs.columbia.edu/~jvoris/AI/notes/assignment_3/player_x.sh https://www.cs.columbia.edu/~jvoris/AI/notes/assignment_3/player_y.sh You will have to modify your program slightly to facilitate this. Instructions for use are as follows: sh player_y.sh )> sh player_x.sh These are short shell scripts, you can view them to see what commands are being called. They set up a simple netcat loop that will time out if it doesn't hear a response in a certain time limit (but won't time out while waiting for an opponent to connect). To use these programs, you must add a line to your program where you open a file named mypipe, and then wherever print your agent's move, it should also writes the move to the file mypipe. For example, in python, to open the file you could use: f = file("mypipe", "w") and to write to it would be: f.write(move) f.flush() Aside from the code inserts, there are only two other conditions that must be met: 1) The players must agree upon the same program parameters (board size, win chain length, time out length) 2) The players must agree upon a move format - recall my recommendation of "x y". Thanks to Oren Finard for writing the network shell scripts.