CMSC 671 PROJECT INFORMATION 9/24/03 Please read this handout carefully and thoroughly. You should start to meet with your project team this week to discuss what you want to focus on in your project, and how you plan to divide up the work. The first deliverable is the project proposal, which is due on Wednesday, October 15. GAME NIGHT: I will host one or two Game Nights over the next couple of weeks so that you can all have the opportunity to play the game of Empire Builder, upon which the project is based. Dates and places for Game Nights TBA; time 6:00 pm until the game ends or we get tired of playing. A full game can last a couple of hours, but it depends on how many people are playing. (If you can't make any of the Game Nights or would like to play on your own, I'll have a copy or two of the game you can borrow.) TEAMS: You should plan to work in groups of two or three. Students who have a strong preference for working individually should talk to me about the workload and expectations. If you don't know anybody in the class and would like help finding a partner, let me know and I'll try to help match people up. Teams should be formed by next Wednesday, 10/1. GAME DESCRIPTION: Empire Builder is a rail-building board game that can be played by 2-6 players. Players take turns paying money to "build track" (draw edges connecting nodes on a map of the United States) and moving along this track. Each player starts with a certain amount of money, spends money to build track, and receives money for delivering goods from cities that produce them to cities that want them. The first player to have $250M wins the game. (All amounts are in millions of dollars.) Building each segment of track costs from $1M to $5M, depending on the terrain (e.g., building through the mountains costs more than building on a prairie). At any point in time, each player has a set of three demand cards, each with three loads. Each load specifies an amount of money that the player will receive for delivering a specified good to a specified city. After any one of these demands is satisfied, the bank pays the player, and the player exchanges the demand card for a new one. Goods are available at designated cities on the board. For example, one card might have demands to deliver cotton to Cincinnati for $15M, tourists to Kansas City for $26M, and wood to Dallas for $38M. Cotton is available in New Orleans and Miami; tourists are available in Los Angeles and New York; and wood is available in Portland, Oregon, and Portland, Maine. One option would be for the player to build track from Portland, Maine, to Dallas, move to Portland (or start there if it's the beginning of the game), pick up wood, move to Dallas, drop off the wood, and receive $38M. Players can rent another player's track for $4M per turn (no matter how many segments are used on that turn). At the start of the game, each player has a standard train, which can travel 8 milestones per turn, and can carry two loads. The player can upgrade to a faster train (12 milestones/turn) and/or a larger train (three loads). RESOURCES: Empire Builder page at boardgames.com: http://www.boardgames.com/empirebuilder.html What's one guy thinks is cool about the game: http://www.nmt.edu/~shipman/games/mayfair.html A nice overview of some of the key strategies that may be useful: http://www.mimgames.com/tga/tgg/strategy/basiceb.shtml The manufacturer's home page: http://www.mayfairgames.com A PC version you can buy if you really get into it: http://www.gamezone.com/gamesell/p12708.htm A place you can order the board game for under $30: http://www.kumquat.com/cgi-kumquat/funagain/05117 A site where you can get a shareware version of Rail Baron, which is a very similar game: http://www.insystem.com/rbp/index.html PROJECT DESCRIPTION: Each project team will implement a player agent for a simplified versoin of Empire Builder. (The map will be smaller than the actual board, and will have fewer city types and goods). More details about the specific rules for the variation we'll be using will be forthcoming. Your player agent must use *at least* one significant AI technique that we are learning about this semester. The options I have come up with include the following: - Heuristic search (Most of you will use some sort of search, if only the A* search that we'll implement in HW #3 to construct a route from A to B. However, heuristic search *should not* be your only method unless you are exploring more sophisticated variants in some depth (e.g., significant game-playing search, probabilistic search through the space of possible future demand cards) - Constraint satisfaction - Logical inference (e.g., resolution theorem proving) - Planning (e.g., STRIPS planning, means-ends analysis, partial order planning, hierarchical task network planning) - Inductive machine learning (that is, learning to predict members of a class - in this case, your player could learn to predict which moves are "good" and which moves are "bad" in a given situation -- specific methods include decision trees, neural networks, and Bayesian network learning) - Reinforcement learning (that is, iteratively learning reactive policies from reward feedback, typically through repeated "self-play") If you choose to use an AI technique not listed instead of (or in addition to) those listed here, you should justify your choice in your project proposal (see below). I would prefer that you not focus on methods we're not covering in the class (examples include case-based reasoning and natural language processing), since the objective is to give you hands-on experience with the methods being taught in this class. However, if you can make a convincing argument why you want to use another method, I am willing to make exceptions. I am also happy to meet with any team to talk about different options, or to discuss possible project approaches by e-mail. DELIVERABLES AND MILESTONES: Monday 9/29 - HW3 out - Requires implementing A* search on the game board for the class version of the game Monday 10/13 - HW3 due Wednesday 10/15 - Project proposal due (5% of project grade). Wednesday 11/12 - Project design due (5% of project grade). Individual reports due. Wednesday 12/3 - Working player agent should be done; dry run competition. Draft report due (optional, to receive feedback before submitting final report). Monday 12/8 - Tournament (~5% - whether and how well your agent works (e.g., following the rules, not crashing, taking turns nicely); ~5% - performance in tournament) Monday 12/15 - Final report and code due (80%). Individual reports due. -- Proposal: 1 or 2 pages describing your proposed project: What AI method(s) do you plan to apply? What resources have you found to learn more about Empire Builder, game playing in general, and the AI methods you plan to use? How does your team plan to divide the work? What challenges and difficulties do you foresee? The proposal is *not* binding, but if you significantly change your plans, you should submit a new proposal (this can be done as part of the design document, if appropriate). At this stage, I don't expect you to have a deep understanding of the techniques you'll be using, but you should at least have identified what direction you plan to take, and how you will go about learning more. -- Design: This document should describe your proposed approach in more detail. You should provide an overview of the approach (anywhere from a couple of paragraphs to several pages), a basic architectural diagram of how your system will work, a list of the main functions you intende to write, a work plan indicating how you plan to divide the work within your team, and a schedule indicating your team's internal milestones for completing the project. -- Report: Your final report should include the following sections, but can be organized in any way you'd like. Neatness, readability, and organization all count. -- Summary of the problem and your approach -- Description of the AI methods you used, including a background section describing the general method, and an application section describing how you applied the method for this project (e.g., what compromises, simplifications, or extensions did you need to make to get it to work). -- Challenges: a summary of the most challenging problems you faced in designing and developing your agent -- Future work: what would you do next if you had more time? How could your agent be improved? -- Complete citation list of sources you used in designing and developing your agent -- Appendix with your code and any data you've gathered (e.g., performance of your agent playing against itself, against a human player, and/or against the course-provided player agents). Your code should also be submitted electronically. IMPLEMENTATION: We will be providing a game server in Lisp that implements the game as an environment for your agent to "live" in. All of your agents should also be implemented in Lisp. The basic rules and data structures will be provided as part of the game server. All interaction with the game environment should take place through the documneted API that we will provide. In particular, no player agent is allowed to modify the data structures directly. (Of course, if you want to modify the data structures directly in order to test various aspects of your agent, that's fine; it just needs to limit itself to the API interactions during game play.) The basic data structures include the game map (which will be dynamically updated as agents build tracks and move around the environment); the players in the game (including their current location, track owned, current speed, bank account, demand cards, and goods); an availability table (mapping cities to goods available in those cities and vice versa), and the deck of demand cards (no peeking!) The main functions that each player will need to write include: -- init-build1 (player) -- given the starting state of the agent (i.e., a set of demand cards and the current state of the board), this function should return the first set of track segments that the agent wishes to build. -- init-build2 (player) -- given the current state of the agent, this function should return the second set of track segments that the agent wishes to build. -- starting-loc (player) -- return a location (which must be a city) where the player wishes to start the game -- choose-build (player) -- based on the agent's current state and the state of the environment, this function should decide what track to build and return a list of track segments to be constructed. -- choose-move (player &optional distance) - based on the agent's current state and the state of the environment, this function should decide where to move and return a connected list of track segments along which the game server should move the agent's piece. The move list also specifies what goods the player wants to pick up and deliver (or dump) along the way. If the returned move list is shorter than the player's allowed number of moves, after making the moves, the game server will call this function again with the remaining distnace. (This gives the agent an opportunity to move to a city, deliver some goods, and then recompute before deciding what to do next.) Details of the data structure and main function implementations will be included with the Version 0 release. We will set up a repository where students can share utility functions that they think other players might find useful. The incentive to share is that teams posting utilities can receive up to 5 points extra credit towards their overall project grade. The disincentive to share is that if you give away your secrets, you help your opponents in the tournament. :-)