联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2019-11-26 11:22

CSE4705 - Introduction to Arti?cial Intelligence November 3, 2019

Project - Konane ˉ

1 Final Project Overview

?e ?nal project for CSE 4705 is to develop a player for the Hawaiian game of Konane which learns from its ˉ

experience. At the end of the semester, you will join in a competition with other Konane players developed ˉ

by your classmates.

While the overall goal of this project is to develop as e?ective a Konane player as possible (i.e., one that ˉ

will perform well in the tournament), the speci?c 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. Speci?cally, 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.

Konane Game Overview ˉ

Konane is a native Hawaiian game played in preliterate Hawaii. K ˉ onane 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 o?en matches consisted of a large number of games.

?e Game Board

Konane is played on a rectangular game board divided into a grid of squares or indentations for game ˉ

pieces. Boards of di?erent 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 ?a?ened rather than spherical.

Your version of Konane will be played on an ˉ 18 × 18 board. ?e board rows are numbered from 1 to

18 and columns denoted by the le?ers 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.

a b c d e f g h i j k l m n o p q r

Figure 1: ?e starting Konane 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

A?er 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 Konane. 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

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 Konane board. ˉ

captured or having a board con?guration which does not o?er 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 Konane server. See the document “?e Artemis ˉ

Server Protocol” for more information on the server. A player who a?empts to make an illegal move loses

immediately and without warning. We will play using a game clock. If your player exhausts its allo?ed

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 description

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 document

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 Minimax

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 function.

Starting from an evaluation function with arbitrary coe?cients, your client should learn a be?er evaluation

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.

Bo?om 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 di?cult to do with the same evaluation function that was used in

earlier game play. ?ere are fewer pieces, hence fewer features. Also, di?erent 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 di?erent board evaluation function and search depth. As with any

board evaluation, it must be based on learned feature weights, not encoded endgame knowledge. 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


版权所有:编程辅导网 2018 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。