Homework 1 (Spring 2023)

Answer the following prompts in a maximum of 8 pages (excluding references) in JDF format. Any content beyond 8 pages will not be considered for a grade. 8 pages is a maximum, not a target; our recommended per-section lengths intentionally add to less than 8 pages. This length is intentionally set expecting that your submission may include diagrams, drawings, pictures, etc. These should be incorporated into the body of the paper.

If you would like to include additional information beyond the word limit, you may include it in clearly-marked appendices. These materials will not be used in grading your assignment, but they may help you get better feedback from your classmates and grader.

Question 1: ~3 pages

Ever since the One Ring was forged by the Dark Lord Sauron, few have been able to resist its seductive power. Gollum was famously corrupted by it, and during his journey to destroy it, even Frodo was tempted by it. One of the few to be able to resist the call of its power was Samwise (Sam) Gamgee.

At one point during their journey to destroy the ring, Frodo, Sam, and Gollum arrive at a river. The river is too wide and deep to swim across, but fortunately, there is a small raft docked on one side. Frodo is too tired from the burden of carrying the ring to drive the raft, however, and Gollum is weak to steer. So, only Sam can steer the raft.

The raft is only large enough for two people at a time; if all three try to ride it, they will sink. So, Sam will have to take Gollum and Frodo across one at a time. However, neither Gollum nor Frodo can be be trusted alone with the One Ring on either side of the river. In fact, neither of them can be trusted alone on the raft with Sam and the ring: its allure is too great, and if given the opportunity, they will simply shove Sam off the side and keep the ring. Therefore, if the either Frodo or Gollum is on the raft with Sam, the ring must be left on one of the riverbanks; if the ring is on the raft, then only Sam can be on the raft with it.

How can Frodo, Sam, Gollum, and the ring get across the river under these conditions? Specifically, neither Frodo nor Gollum can ever be alone with ring on either bank of the river, nor can Frodo or Gollum be on the raft with the ring. If the ring is on the raft, then only Sam can be on the raft with it. Obviously, Sam is also permitted to steer the raft alone. (It is okay, however, for the ring, Sam, and Frodo or Gollum to be on one bank of the river together, so long as on the next move, Sam departs with either the ring or Frodo/Gollum).

First, construct a semantic network representing this problem. This should take approximately half a page, including a figure of two states with a transition between them. Make sure to include all components of the state, and an operator indicating how we transition from one state to another.

Second, apply generate & test to this semantic network in order to solve the problem. In applying generate & test, your generator should be smart enough to only make valid moves (e.g. it will not try to move Gollum and the ring together at once, or make consecutive moves in the same direction across the river without Sam bringing the raft back), but it should not be smart enough to only make moves that result in valid states (e.g. it should still try to move Frodo first, even though that move results in an invalid state, specifically Gollum alone with the ring). Your tester, in turn, should check each generated state to see if (a) it follows the rules, and (b) if it has met the goal. You may decide whether identifying states that have already been visited is the responsibility of the generator or the tester.

Include the entire semantic network that solves this problem. Clearly indicate which states are failed, and why. The semantic network should explore the entire problem space: every state should be either ruled out or have its following states explored. We expect this will fit on one page: you may create a more space-efficient representation if need be. As long as it is legible, you may also hand-write the network and insert it as an image into your paper.

For the purposes of this question, please ignore how foolhardy it would be to leave a ring of such immense power alone on the side of a river, as well as the fact that Frodo would never willingly permit Sam to carry the burden of the ring.

Question 2: ~3 pages

Uno is a card game manufactured by Mattel and invented over 50 years ago; it is very similar to the game Crazy Eights played with a standard deck of cards. If you already know how to play Uno, you can skip the next four paragraphs.

A deck of Uno cards is made of 108 cards. Most cards are divided into four colors: there are 25 red cards, 25 yellow cards, 25 blue cards, and 25 green cards. Within each color are the numbers 0 through 9, and three special types of cards: Skip, Reverse, and Draw 2. There are also 8 black cards: 4 Wild cards and 4 Wild Draw 4 cards.

The rules of Uno are simple: between 2 and 10 players each receive 7 cards. The players then take turns putting down one card at a time on top of the Discard pile. The card that a player puts down must have either the same color or same number as the current card on top. So, if the top card is a red 7, then the next player can put down any red card or a 7 of any color. If a player has no other cards they can play, they may place a Wild card and select a new color for the next player to play. For example, if the top card is a red 7, then the current player could play a Wild card and say that the new color is Green. If a player has no cards that can be played, then they must draw a card; if they can play it, they may play it immediately, but otherwise play continues to the next player.

Some cards have special effects. A Skip card skips the next player’s turn. A Reverse card reverses the order in which players play; if players were initially taking turns clockwise, they will now play counter-clockwise. A Draw 2 or Wild Draw 4 card requires the next player to draw the given number of cards instead of taking their turn.

The goal of the game is to get rid of all your cards. The first player to get rid of all their cards wins. Any time a player goes down to having only one card left, they must announce “Uno!” If another player says “Uno!” first, the player must draw 4 more cards. You can find a full rundown of the rules of Uno in this PDF (though you can ignore the parts about “500 points”, those refer to a game made of multiple individual rounds of Uno—we’re only talking about one round).

You may practice playing against an AI at this site.

After getting familiar with the rules of Uno and how to play, write the pseudocode for a rule-based Uno-playing agent. A rule-based agent is one that, like a production system, operates according to a set of programmed rules; however, for this assignment, you are allowed to go beyond what a production system typically contains and include things like else blocks and nested conditionals.

Specifically, the pseudocode should handle what the agent does on a single turn. You may assume that the agent has full, perfect knowledge of the following set of knowledge about the game: the number of players, how many cards each player has, the agent’s own cards, the current card on top of the pile, and each card every other agent has previously played and when. You may also add additional pieces of knowledge to this set if you can think of any. The agent should conclude by selecting an action; possible actions include: selecting a specific card to play, drawing a card from the deck, or selecting a Wild card and selecting a color. Saying “Uno” may accompany any of these other actions as well.

Your agent should handle all scenarios that it could encounter on a single turn, including (a) having multiple cards available that could be played and selecting only one, (b) playing its second to last card, (c) having no cards that can be played, and (d) playing a Wild card and choosing a color. Your agent should have some strategy; places where you might add some strategy could include how it chooses a color when playing a Wild card, how it selects from multiple available cards based on what other players have played, or how it considers how many cards other players have left when selecting a card to play. For full credit, your agent should use at least three different things it can perceive from the set above as part of its strategy. Some decisions may be be random, but your agent could also make those decisions strategically.

Then, before playing a round of Uno, explain why your agent works the way it does. What is the rationale behind the decisions that it makes? What strategy is it trying to employ?

Then, use your agent’s rules to play a round of Uno, using either the site above or your own set of cards. As you play, log the game progress. For opponents moves, you may just log the observable move (e.g. Player 2 plays Blue 7). For your own moves, include how your agent’s reasoning operated and why it landed on the rule it did (e.g. There are 3 cards my agent can play: Blue 6, Blue 8, or Red 7. My agent decides to choose between Blue 6 and Blue 8 because it prioritizes whatever color it has the most of. Then, it randomly chooses Blue 6.).

Finally, reflect on the agent’s rules. Select at least one time when you would have made a different move than the one dictated by your agent’s rules; if such a time did not emerge, play a couple more games (and if one still does not emerge, imagine what one such situation might be). What element of your human reasoning is missing from the agent? Is more knowledge needed? Or is it more nuanced and complex reasoning? Could that knowledge be implemented in your agent’s structure?

Note that our expectation is that the pseudocode and the game log for this question will each be around half a page (especially if you make them each two-column); if you need more room specifically for the pseudocode or game log, you can shift any content beyond a half-page for each into an appendix that will not count against the length limit.

Submission Instructions

Complete your assignment using JDF, then save your submission as a PDF. Assignments should be submitted to the corresponding assignment submission page in Canvas. You should submit a single PDF for this  assignment. This PDF will be ported over to Peer Feedback for peer review by your classmates. If your assignment involves things (like videos, working prototypes, etc.) that cannot be provided in PDF, you should provide them separately (through OneDrive, Google Drive, Dropbox, etc.) and submit a PDF that links to or otherwise describes how to access that material.

This is an individual assignment. All work you submit should be your own. Make sure to cite any sources you reference, and use quotes and in-line citations to mark any direct quotes.

Late work is not accepted without advanced agreement except in cases of medical or family emergencies. In the case of such an emergency, please contact the Dean of Students.

Grading Information

Your assignment will be graded on a 10-point scale coinciding with a rubric designed to mirror the question structure. Make sure to answer every question posted by the prompt. Pay special attention to bolded words and question marks in the question text. For further information on how the assignment is graded, see the rubric in Canvas.

Peer Review

After submission, your assignment will be ported to Peer Feedback for review by your classmates. Grading is not the primary function of this peer review process; the primary function is simply to give you the opportunity to read and comment on your classmates’ ideas, and receive additional feedback on your own. All grades will come from the graders alone. See the course participation policy for full details about how points are awarded for completing peer reviews.