Assignment

 

**This assignment is out of 12 points. All questions are weighted equally.**

 

## Instructions

 

  1. Fork this repository into your CSE262 project namespace. [Instructions](https://docs.gitlab.com/ee/workflow/forking_workflow.html#creating-a-fork)
  2. Clone your newly forked repository onto your development machine. [Instructions](https://docs.gitlab.com/ee/gitlab-basics/start-using-git.html#clone-a-repository
  3. As you are writing code you should commit patches along the way. *i.e.* don’t just submit all your code in one big commit when you’re all done. Commit your progress as you work. You should have at least one commit per question. **The assignment will not be accepted if you do not follow this procedure.**
  4. When you’ve committed all of your work, there’s nothing left to do to submit the assignment.

 

## Assignment

 

The purpose of this assignment is to model the game of Checkers in Prolog. You don’t have to write any code that is meant to run for this assignment, although if you want you may. For this assignment you can assume that the set of built-in predicates available to you are [the same as SWI-Prolog](https://www.swi-prolog.org/pldoc/man?section=builtin). 

 

Some useful predicates:

 

[retract](https://www.swi-prolog.org/pldoc/man?predicate=retract/1) – The fact or clause is removed from the database.

[arithmatic](https://www.swi-prolog.org/pldoc/man?section=arith) – Pay attention to the use of the [is](https://www.swi-prolog.org/pldoc/doc_for?object=(is)/2) predicate to assign values to an unbound value e.g. `X is 1 + 2`

[not a.k.a. \+](https://www.swi-prolog.org/pldoc/doc_for?object=(%5C%2B)/1) – Returns `true` if a target goal cannot be reached i.e. a fact or predicate cannot be found in the database.

 

In this assignment I give you a number of suggested predicates to use. You may model your problem any way you like, including adding any predicates you need. For any code you write, also include an explanation of the code. There will be few points given for a solution without an explanation. If you can’t write the code necessary, write an explanation of what the code might look like to get partial points. You’ll get more points for an explanation without code than you will for code without an explanation.

 

## The Game Board

 

The standard Checkers game board is an 8×8 grid of cells. Starting at (1,1), every other cell is restricted from play. Player 1 is indicated by `x` markers. These occupy the first three rows. Player 2 is indicated by `o` markers. These occupy rows 6 through 8. Rows 4 and 5 are empty, indicated by underscores.

 

“`

   1  2  3  4  5  6  7  8  

1     x     x     x     x  

2  x     x     x     x     

3     x     x     x     x  

4  _     _     _     _     

5     _     _     _     _  

6  o     o     o     o     

7     o     o     o     o  

8  o     o     o     o    

“`

 

We can call x at (1,2) x1; x at (1,4) x2; x at (2,1) x5 etc.

 

We can call o at (6,1) o1; o at (6,3) o2; o at (7,2) o5 etc.

 

### Valid Moves

 

A player’s pieces may only move away from the player if the pieces are not “kinged” (imbued with additional abilities). 

 

There are two kinds of valid moves: a move into a free space and a “capture”. A piece may move into a free space if the space is adjacent diagonally from it, and it is away from the player. If the piece is kinged, it may move into an adjacent free space that is closer to the player.

 

A capture occurs when a player’s piece moves over a diagonally adjacent opponent’s piece into a free space. The opponent’s piece is removed from play following a capture.

 

If a player’s piece moves into the furthest row from the player (row 1 for player `o`, row 8 for player `x`), then that piece is considered “kinged”, which allows it greater freedom in movement (it can now move toward the player instead of strictly away).

 

### Winning

 

The game ends when one player can no longer make any moves, either by being blocked from making moves, or by having all pieces captured (and removed from play).

 

## Questions

 

### Question 1

 

Write down all of the facts representing the game pieces given their positions at the start of the game. We can use the `occupied(A,B)` predicate for this, where A is the game piece and B is the `cell`. e.g. `occupied(x1, cell(1,2))`

 

### Question 2

 

Write a horn clause (or clauses) to introduce the free cells with the predicate `free(A)`, where `A` is the free `cell`. For example, in the initial game state we would have `free(cell(4,1))`, `free(cell(4,3))`, `free(cell(4,5))` etc.

 

### Question 3

 

Write a horn clause (or clauses) to mark the cells which are not free as `occupied(A)`, where `A` is a cell with either an `x` or an `o` piece on it. e.g. `occupied(cell(1,2))`.

 

### Question 4

 

Consider the piece `o3` at `cell(6,5)`. It has two valid moves: it can move into either `cell(5,4)` or `cell(5,6)` because they are both free. We can use the following predicate to express this: `valid_move(A,B)`, where A is a player’s piece and B is a free space. e.g. `valid_move(o3, cell(5,6))`.

 

Write a horn clause (or clauses) to generate the set of all valid free moves for all of player `o’s` pieces.

 

Don’t considered kinged pieces for this question.

 

### Question 5

 

Consider the following game state

 

“`

   1  2  3  4  5  6  7  8  

1     x     x     x     x  

2  x     x     x     x     

3     _     x     _     x  

4  _     x     x     _     

5     o     o     _     _  

6  _     _     o     o     

7     o     o     o     o  

8  o     o     o     o    

“`

 

Write a horn clause (or clauses) to express all adjacent opponent pieces. Use the predicate `adjacent_to(A,B)` for this, where A is the player’s piece, and B is the opponent’s piece. e.g. `adjacent_to(o2,x11)`.

 

### Question 6

 

For the piece `o2`, it has two potential capture moves: either it can take `x9` at `cell(4,3)` or it can take `x11` at `cell(4,5)`. We can use the following predicate to express this: `valid_capture(A,B)`, where A is the player’s piece, B is the opponent’s piece: e.g. `valid_capture(o2,x9)`. Write a horn clause (or clauses) to generate every `valid_capture(A,B)` for a given game state.

 

Don’t considered kinged pieces or double jumps for this question.

 

### Question 7

 

Consider a piece `o` at `cell(1,2)` or `x` at `cell(8,1)`. They have made it to the other side of the board, and are now considered “kinged”. Write a horn clause (or clauses) to give the “kinged” property to pieces that make this journey. These pieces may travel back toward the player. 

 

### Question 8

 

Update your answer to Questions 4 and 6 to take into account kinged pieces.

 

### Question 9

 

Consider the following game state:

 

“`

   1  2  3  4  5  6  7  8  

1     x     x     x     _  

2  x     x     x     x     

3     _     x     _     x  

4  _     x     x     _     

5     o     o     _     _  

6  _     _     o     o     

7     o     o     o     o  

8  o     o     o     o    

“`

 

The piece `o2` at `cell(5,4)` has two valid capture moves, but one is better: the double capture of x11 and x7. Write a horn clause (or clauses) that can enumate all valid double jumps with the predicate `double_jump(A,B,C)`, where A is the player’s piece, B is the opponent’s first piece, and C is the opponent’s second piece: e.g. `double_jump(o2,x11,x7)`.

 

### Question 10

 

Write a horn clause (or clauses) which will select the next move player `o` will make. Call it `next_move(A)`, where A is the predicate relating to the move the player will make. Use Prolog’s execution model to implement a move selection strategy. The strategy you should use is:

 

  1. Prefer any move which captures the most opposiing pieces.
  2. Prefer any move which leads to a kinged piece.
  3. Prefer any valid move which does not lead to your opponent taking one or more of your pieces (you can call such moves “threatened” moves).
  4. Prefer any valid move.

 

A full solution will consider all of these strategies. You may consider a subset of these for partial credit.

 

### Question 11

 

Write a query which will tell you if the `o` player is winning the game (has more tokens than `x`).

 

### Question 12

 

Write a query which will tell you whether or not the game is won by any player.

 

Answer

Study Cred Tutor

4.6 (24k+)
4.6/5

Purchase the answer to view it

×

Hello!

Click one of our contacts below to chat on WhatsApp

× How can I help you?