CSE4705 – Introduction to Articial Intelligence November 3, 2019 Project – Ko¯nane 1 Final Project Overview e nal project for CSE 4705 is to develop a player for the Hawaiian game of Ko¯nane which learns from its experience. At the end of the semester, you will join in a competition with other Ko¯nane players developed by your classmates. While the overall goal of this project is to develop as eective a Ko¯nane player as possible (i.e., one that will perform well in the tournament), the specic goal is to develop a player that learns from its experience. To this end, your player will choose its moves based solely on a search of the game tree and evaluation of game states. Specically, the encoding of openings, endings and other move sequences is expressly prohibited. More information about what is allowed is provided below ese projects will be cone in teams of three to four students. Teams of other sizes must be approved by the instructor. e expectations are the same for all teams, regardless of team size. Ko¯nane Game Overview Ko¯nane is a native Hawaiian game played in preliterate Hawaii. Ko¯nane was popular among all classes and genders unlike some other games that were taboo to one class or gender. A game sometimes lasted an entire day and oen matches consisted of a large number of games. e Game Board Ko¯nane is played on a rectangular game board divided into a grid of squares or indentations for game pieces. Boards of dierent sizes and dimensions existed. e number of rows ranged from 8 to 13, and the number of columns from 8 to 20. Each position on the game board had a hole or indentation for the game pieces. e center of the board was called piko (navel). e row along the borders of the board was termed kaka’i . Before starting play, the board positions were lled with alternating black and white stones. Local beaches provided basalt and coral pebbles for game pieces, whose preferred size was under an inch in diameter and slightly aened rather than spherical. Your version of Ko¯nane will be played on an 18 × 18 board. e board rows are numbered from 1 to 18 and columns denoted by the leers a through r. Game Play Initial Player Moves Each game begins with a full game board as shown in Figure 1. One of the two players is selected uniformly at random to move rst. e selected player removes one game piece from the board. e player may select either one of the four corner pieces or one of the four center pieces on the board as shown in Figure 1. 1 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 a b c d e f g h i j k l m n o p q r Figure 1: e starting Ko¯nane board. With this selection the rst player to move selects the color of the pieces they can move for the remainder of the game. e other player’s rst move is to select one of the pieces horizontally or vertically adjacent to the piece removed by player 1, to remove from the board. e piece selected must be of the alternate color from player 1 and will be the color of the pieces moved by player 2 for the remainder of the game. Subsequent Player Moves Aer the initial moves, Player 1 and Player 2 will alternate moves for the remainder of the game. Each player, in turn, will select one of their pieces to move. A move consists of jumping, and removing from play, a piece of the opponent player. Moves may only be made in the horizontal or vertical direction. at is, no diagonal moves (jumps) are allowed in Ko¯nane. A player’s piece which jumps an opponent’s piece must land in the space immediately beyond the opponent piece. is space must, of course, be vacant in order to be able to execute the jump. If a player’s piece is able to jump another piece of their opponent in the same direction, then the player may jump the additional piece of their opponent at their discretion. ere is no penalty for not executing multiple jumps even if the opportunity exists. Any and all opponent pieces which are “jumped” are captured and removed from the game board. Endgame and Winning e rst player who is not able to make a move during their appointed turn loses the game. e number of captured pieces is irrelevant. Players may be unable to move due to either all of their pieces being 2 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 a b c d e f g h i j k l m n o p q r Figure 2: Selecting a piece for removal from the Ko¯nane board. captured or having a board conguration which does not oer them any moves from which to choose. e last player to move is deemed the winner. Client Players and Competition Language and Environment You are free to use any programming language (or languages) you choose to develop your player. However, it must be able to compete as a client using the Artemis Ko¯nane server. See the document “e Artemis Server Protocol” for more information on the server. A player who aempts to make an illegal move loses immediately and without warning. We will play using a game clock. If your player exhausts its alloed time, your player loses the game. You may choose to represent the game state however you like. But, you must communicate with the server using its representation. Wherever you care running your client, it will need to be available at the nal competition, which will be in the location selected by the University for your nal examination. Make sure it is feasible to run your client player with the server well before the competition. Project Debrief Each team will meet with the instructor (scheduled during class time as much as possible) during the nal week of the semester. Each debrief will last approximately ten minutes and will involve discussion of your 3 program design, how your program updates its evaluation function, and how you trained it. 1.1 e Tournament e tournament will be held during nal exams. We will have a round-robin tournament (where each client plays each other client), followed by a two-game nal round for the two top programs (best of three wins including the earlier match). For this to be feasible, we will allow three minutes per player in each match. Documentation and Deliverables Each team will submit a report that includes appropriate design documentation for your client, a descrip- tion of the factors used by your evaluation function and a description of how your program was trained and evaluated. It should also include documented code for all of your programs. is report should docu- ment how your program progressed over time. It should show how the evaluation function changed as a function of the games it played. What is Allowed? Your program will choose moves based on limited lookahead, using a board evaluation function at the leaves. Your board evaluations should be a function of observable board features that estimates the Min- imax value of the state. Samuel used a set of 25 board features for his Checkers player plus 12 “binary connective” terms, as his parameters. ese may serve as a guide for parameters in your evaluation func- tion. Starting from an evaluation function with arbitrary coecients, your client should learn a beer eval- uation function by playing games. We will look at a number of possible techniques for doing so (Chapter 21 in particular; Samuel also provides information on what he did for Checkers). However, feel free to apply other techniques. Boom line: Your program can learn to evaluate boards by playing with any other players, but it must always make its own moves. So, Samuels method of playing book games is not allowed and the use of opening or endgame databases is prohibited. 1.1.1 Endgame Variations Experience shows that endgames are dicult to do with the same evaluation function that was used in earlier game play. ere are fewer pieces, hence fewer features. Also, dierent features may have greater value when trying to end the game, etc. We will, therefore, allow programs to change behavior once during the game. From then on, it can use a dierent board evaluation function and search depth. As with any board evaluation, it must be based on learned feature weights, not encoded endgame knowl
edge. If you choose to use this feature, your client can only change to endgame mode once in a game and must remain there until the end of the game. Grading Grades will be assigned based on a linear function of the quality of your report, the debrief, and how well your client does in the tournament with weights approximately 0.4, 0.3, and 0.3 respectively. However, 4 winning the tournament will be given extra weight, so the winner is virtually guaranteed an A unless the team neglects to produce a report or participate in a debrief. 5
