Description of ISOLA This is a two-player game. You start with a 7´7 position board, which initially contains two pieces, one for each player. Both players (h for human and c for computer) flip a coin and whoever wins plays first. At each turn, a player c

Coursework Handout: CCP2410 Logic Programming 1

LLOOGGIICC PPRROOGGRRAAMMMMIINNGG CCOOUURRSSEEWWOORRKK HHAANNDDOOUUTT

UNIT DETAILS DEPARTMENT Computer Science PROGRAMME BSc (Hons) in Computer Science UNIT CODE CCP2410 UNIT TITLE Logic Programming SEMESTER Autumn SESSION 2014-15 STAFF Prof Petros Kefalas STAFF OFFICE Tsimiski Bldg 1st floor E-MAIL [email protected]

COURSEWORK DETAILS C/W NUMBER 2 CONTRIBUTION 45% of the unit final mark C/W TITLE Implementation of a two-player game C/W TYPE Programming in Prolog HAND-OUT DATE 26/11/2014 SUBMISSION DATE 19/12/2014 FEEDBACK DATE 14/1/2015

LEARNING OUTCOMES Upon completion of this piece of coursework, a student will be able to: � understand the functionality of Prolog predicates and express it in natural language; � understand textual descriptions of predicates and design the corresponding Prolog programs; � implement recursive predicates on lists consisting of complex terms; � implement predicates exploiting the power of higher order built-in predicates; � utilise procedural abstraction to decompose a complex predicate description into simpler ones and

synthesise complex predicates by reusing already defined built-in or user-defined predicates; � develop correct and well-documented programs on specific problems, and test them.

ASSESSMENT CRITERIA � Program correctness (code loads to Prolog with no warnings or error messages, correct use of recursion,

procedural abstraction and built-ins, production of correct results for normal and boundary cases). � Proper code documentation and meaningful variable and predicate names. � Programming style (proper use of variable assignment, efficiency). � Explanation of the provided code and justification of design choices.

DETAILED DESCRIPTION

Description of ISOLA

This is a two-player game. You start with a 7×7 position board, which initially contains two pieces, one for each player. Both players (h for human and c for computer) flip a coin and whoever wins plays first. At each turn, a player can do two consecutive moves:

• Move one’s own piece to a neighbouring position (horizontally, vertically or diagonally) that is empty (not crossed out).

• Remove any position from the board by crossing it out.

The looser is the player who cannot move its piece to a neighbouring position, i.e. the piece is isolated. There is no draw. The figure on the next page presents an instance of the game. Aim of the Practical

The aim of this practical is to implement this game in Prolog. One player will be the human, and the other player will be the program, and in our case the computer always plays first. We are not concerned with the program being intelligent (at least not during this semester!) so the program will perform all its moves at random.

Coursework Handout: CCP2410 Logic Programming 2

h

c

x h

c

x h

x c

x x h

c

x

x x h

x c

x

x x h

x

x c

x

x x h

x

x x c

x

x x x x x x x x h

x x

x x x x x x x x c

x x x x x

c moves & crosses out

c moves & crosses out

c moves & crosses out

c moves & crosses out

h moves & crosses out

h moves & crosses out

h moves & crosses out

c moves & crosses out

c wins!!! h cannot play anymore

…

In the first move c moves up-right and crosses out the square south to h. Then h moves down-right and crosses out the square north-east to c. The game continues this way until h cannot move anywhere. c wins because h piece is surrounded by Xs and has no other move available.

Preliminaries

We chose the following representation for the board: board([ (1,1,-), (2,1,-),(3,1,-),(4,1,c),(5,1,-),(6,1,-),( 7,1,-), (1,2,-), (2,2,-),(3,2,-),(4,2,-),(5,2,-),(6,2,-),( 7,2,-), (1,3,-), (2,3,-),(3,3,-),(4,3,-),(5,3,-),(6,3,-),( 7,3,-), (1,4,-), (2,4,-),(3,4,-),(4,4,-),(5,4,-),(6,4,-),( 7,4,-), (1,5,-), (2,5,-),(3,5,-),(4,5,-),(5,5,-),(6,5,-),( 7,5,-), (1,6,-), (2,6,-),(3,6,-),(4,6,-),(5,6,-),(6,6,-),( 7,6,-), (1,7,-), (2,7,-),(3,7,-),(4,7,h),(5,7,-),(6,7,-),( 7,7,-) ]). The above is the initial board which consists of forty nine (49) 3-tuples. When the game is played, the board list

(passed as an argument through all relevant predicates) will be filled by tuples of the form (X,Y,PieceOrX) where X and Y are the coordinates of a square in the board, and PieceOrX is a either or an h or c (pieces of the players) or an x (cross-out).

We also provide some parts of the code which can be downloaded from the unit's site (filename is “Isola Partial 2014.pl ”). The analytical comments in the file will help you understand the specification of each predicate definition. Some of the predicates are complete and can work immediately; some are partially complete and require the definition of more predicates in order to work properly. Finally, some other auxiliary predicates are also provided.

Coursework Handout: CCP2410 Logic Programming 3

Questions

1. What does the predicate pp/1 do and how? Would it matter if the board elements were messed up (not in order)? Would it be possible to write a recursive predicate that does the same operation? Again, would the order of board elements matter?

[10%]

2. Write Prolog code for the predicate in_position/3 , which given a number and a list of items, returns the item that corresponds to the position indicated by the number. For example:

?- in_position (4, [a,b,c,d,e,f], X). X = d

[10%]

3. As it stands now, next/4 finds the neighbouring positions vertically and horizontally. Can you complete it to make it work for diagonal neighbours?

[10%]

4. As it stands now, computer always plays first. Can you modify the code, so that the human decides either who plays first or if the first player is to be chosen at random?

[10%]

5. Write the definition of the predicate find_options/3 , which given a position (X and Y coordinates) and a board, returns a list of all available neighbouring positions.

[10%]

6. Consider the partial definition of select_one_to_move/3 predicate. It is implemented for player h but not for player c. Complete the definition so that player c selects in random an available position to move.

[10%]

7. Write the definition of the predicate select_a_position_to_cross/3 predicate so that either player c or h selects an available position to cross out.

[15%] 8. The board of the game could be represented by alternative notations. For example:

� A list with 49 ordered places, i.e.: board([-,-, … -,-]). � A list of seven lists of seven items each, i.e.: board([[-,-,-,-,-,-,-],…,[-,-,-,-,-,-,-]]). � A set of facts, i.e.

board((1,1),-). board((2,1),-). board((3,1),-). … board((7,7),-).

What would be the pros and cons of such representations, considering code complexity for list manipulation, ordering of list items, time and space efficiency, or any other factor you may think of?

[10%]

9. This game could have variations in scale:

• It could be played in a smaller or bigger board, for example a 5×5 or a 11×11 board. • There could be more than 2 players. • It could be 3-dimensional

What changes, if any, would you perform in each of the above cases to the program in order to make it work?

[15%]

Coursework Handout: CCP2410 Logic Programming 4

SUBMISSION Students are expected to: � Submit a typewritten and well structured report that contains:

� The answers to the coursework questions, which should also include all student code listings (documented) together with a brief explanation and justification of the design choices made. DO NOT print the entire Prolog code and save some trees! However you do need to include all parts that you have developed!

� Evidence that the program is working as a whole or partially, such as a log of a game or example Prolog queries and their answers. You may include bugs that have been identified in the submitted code but could not be fixed.

� References to other sources (if any). � Upload their well documented Prolog program (the completed “Isola.pl” file), which should be

loaded without any problems to the SWI-Prolog interpreter, under ‘Assignments’ in the unit’s page on MOLE. A well documented Prolog program should have: � Comments above each predicate definition that contain the predicate specification

(predicateName/arity), a declarative description of the predicates success conditions and use, possible side-effects (for example "the predicate displays on the user console the …"), solutions returned on backtracking, argument instantiation pattern, etc.

� Predicates, variables and constants with meaningful names. � Correct indentation, i.e. clear separation between head and body of definitions, clear separation of

predicate definitions, etc. IMPORTANT NOTE: Delayed submissions will not be accepted.

NOTE All sentences or passages quoted in this coursework from other people's work should be specifically acknowledged by clear cross-referencing to author, work and page(s). Failure to do this amounts to plagiarism and will be considered grounds for failure in this coursework. It is on the instructor’s discretion to contact an oral examination, which will result to the award of the final grade to that particular piece of coursework.