Design and Play, A Microworld for Designing and Exploring Games

Design and Play in Comenius Logo: A microworld for designing and exploring games

Pavel Petrovic
student of Dept. of Informatics Education,
Faculty of Mathematics and Physics,
Comenius University, 84215 Bratislava, Slovak Republic,
tel. +421-7-728032,
e-mail: Pavel.Petrovic@st.fmph.uniba.sk

Abstract

Many table games (i.e. Checkers, Tic-Tac-Toe, Backgammon) are known to improve a child's thinking skills and problem solving abilities. Playing a game with a stronger opponent challenges him/her to reflect on the game’s strategy. Allowing children to alter the game rules themselves (provided that this is techically possible) encourages the design and exploration of interesting modified versions of well known games.

The Design and Play Logo application developed within the environment of Comenius Logo for Windows (Super Logo) is a microworld for designing and playing table games by combining basic game components. Game rules can be optionally specified using the Learning by Example alternative. A designed game may be saved into a file. It can be played both against another player and the computer. The application is completely opened, i.e. new game components may be added. The constructivist environment has been developed in a semi object-oriented way.

Keywords

games, Comenius Logo, learning by example, generalization

1 Model of environment

1.1 Goals

My aim was to create a user-friendly environment for designing and playing table games. More specifically, we focused only on games which don’t contain any random factor (like a dime). Moves and actions in the game are the results of players’ decisions. This microworld should provide the game equipment, instruments, elements, figures, stones etc. normally used in typical table games. They ought to be easily grouped together so that one can quickly design a game using drag-and-drop and mouse operations. The user should be able to specify the underlying rules for the game and play the game with a friend or the computer. The designed game may be modified any number of times, saved to, or retrieved from, a file. The application should be opened for adding new game equipment, figures, etc. The following is a simple example of a NIM-type game:

NIM12 is a game for 2 players. There are 12 matches on the table and each player can remove 1, 2 or 3 in each move. The goal of the game is to make the opponent take the last match. The game uses individual match figures, a universal group of figures (from where the matches are drawn from) and a waste basket. The 2 pieces of static game equipment are named matchgroup and basket (names are chosen arbitrarily by each game designer). Once the game is started, they cannot move. They are instances of their types: group and wastebasket respectively (during the design process a designer is given a rich set of different types of equipment, triggers and figures). In the beginning, there are 12 matches (named m.1 ... m.12) placed on the equipment matchgroup. As any figures, they are not static and they are always placed on some static equipment. We specify a single rule for this game: one step consists of removing a match from the matchgroup to the basket and we allow this step to be performed in each move once, twice or three times. We also specify a game-over-condition: matchgroup contains no matches (described using Logo expression [empty? contains "matchgroup]). When the game-over condition holds, the winner is the player on move.

This first example necessitates specifying a formal model of such an application. Then the model can be described from different points of view, an implementation method can be selected and another game can be designed in our microworld.

1.2 Game player’s point of view

While playing an already designed game, the player’s screen is split into 3 regions: game environment area, control buttons and the game progress information. The third region displays approving rules for steps and moves made by players. This is not essential for playing the game. Control buttons allow the user to interrupt the game or to pass the move to the next player, if this could not be made automatically. The most important region is the game environment area, where the user can perform steps and moves. One move is made by one player. Players alternate in moves. A move consists of one or more steps and (if necessary) confirmation of the end of the move. The elements in the game environment area are divided into three categories: game equipment which is static and cannot be moved, figures which can be moved in subsequent steps around the equipment, and triggers which serve to save game status information of the game (i.e. whether a player has already done a castling in Chess). Triggers may be invisible and they have a value which can be used or set by rules. The only kind of step a user can perform is to move some figure from one game equipment to the other (i.e. to move a pawn from one square of the chessboard to the other). Even games like Tic-Tac-Toe can work with these restrictions. The starting position of such a game would contain empty squares and groups of unused circles and crosses. A player could drag a single circle or cross to a certain square.

A game is over when some game-over-condition is satisfied. In such a case, one of the players is said to be a winner (for 2-player games). To summarize this section, we have identified that the game specification consists of:

number of players (we allow 2 or 1, a 1-player game is a puzzle)
list of equipment used in the game
list of figures (stones, pieces, etc.) used in the game
list of triggers used in the game
starting configuration of equipment, triggers, and figures on the equipment
rules for steps and moves
game-over-conditions (or game goals)

1.3 Game designer’s point of view

Making the application user-friendly has one of the highest priorities. In fact, designing a simple game is sometimes easier than playing it. On the other hand, the application lets a designer customize the game to specific properties and peculiarities. In the design mode a user can see "a box" with all the available equipment, figures and triggers. The first task is to design a starting configuration by dragging necessary elements from the box to the game environment area.

Each element in the environment should be given a name. Certain types of equipment may automatically generate figures (and their names) and a user can always specify element attributes, (color, size,...) or specific behavior when dropping equipment or a figure in the game environment area. Groups of elements in the game environment area may be moved together when selected (by clipping a rectangle around them).

When the starting configuration is specified, the user has to define the rules for steps and moves. The task is to design moves, each one consisting of one or more steps. Let’s investigate the example of game Dama. There are 4 basic types of moves: single move with a stone, capturing one or more opponent’s stones, single move with a privileged stone, and capturing one or more opponent’s stones with a privileged stone. The second and the fourth consist of one or more steps of the same type, while the first and the third of the only one step. If the stone is moved to the last row, it is changed to the privileged stone. Furthermore, each move can start with removing a stone which was supposed to capture an opponent’s stone and this is allowed only if the previous opponent’s move was non-capturing.

The designer has an option to specify the basic steps by showing an example (i.e. by moving some specific stone, say, stone.white.4 from some specific square, say, square.2.2 to another square, say, square.3.1). The corresponding rule for the step is automatically created. In this example the rule would be:

what: [[NAME stone.white.4][TYPE stone][ORIGIN square.2.2]]

from: [[NAME square.2.2][TYPE square]]

to: [[NAME square.3.1][TYPE square]].

All three main parts of the rule (from, to and what) may be generalized. There are three possible levels of generalization for what part of the rule, and two levels for from and to parts. If what part of the rule specifies a figure named X of type Y which is on the equipment Z in the starting configuration (origin), it can be generalized to a) any figure of type Y from equipment Z (in our example: [[TYPE stone][ORIGIN square.2.2]]); b) any figure of type Y (in our example [[TYPE stone]]); c) any figure (just []). Similarly, from and to parts of the rule may be generalized to any equipment of its type (i.e. [[TYPE square]]) and to any equipment (again []). This generalization occurs when the designer pushes one of the "Generalize" buttons while designing rules. He/she can also write rules manually. Rules may also contain expressions with wildcards (*, ?), for example what: [[NAME stone.white.* [n]]]. Wildcards are substituted by subwords. These substituents are assigned to variables with names ?symbol? (here the variable ?n? would be assigned the value 4, if this rule is used when player moves a figure stone.white.4). These variables may be used in when-conditions which (if any) restrict a usage of a particular step-rule. Some games require their steps to perform certain actions (like changing a stone into a privileged stone when reaching the last row of the chessboard in Dama) and thus the application provides an option to specify side-effects for each step.

When the rules for moves and steps are completed, the last phase of the design is to specify the game-over-conditions. These are lists of when conditions on the game configuration. When all conditions in any list are satisfied, the game is over. There is a player (his/her number) associated with each list. When all conditions in the list are satisfied, this player is said to be a winner. (It’s recommended to see the example in section 1.6 in this moment).

To employ a more formal language: A game specification [N D E F T S M G] consists of N - number of players, D - a description of the game, E - specifications of equipment, F - figures, T - triggers, S - steps, M - moves and G - game-over-conditions or goals.

The number of players is either 1 or 2. A one-player game will be called a puzzle.

The description is a text displayed before playing. It instructs the player how to play a game.

Equipment specification is a list of tuplets [name type position arguments], where name is a word, type is a word (one of the possible equipment types), position [x y] is a position of the equipment in the game environment area and arguments is a type-specific list.

Figures specification is a list of tuplets [name type starting-equipment arguments], where name is a word, type is a word (one of the possible figure types), starting-equipment is a name of some equipment from the equipment specification list and arguments are type-specific.

Triggers specification is a list of tuplets [name type starting-value position visible arguments], where name is a word, type is a word (one of the possible trigger types), starting-value is an expression, position [x y] is a position of the trigger in the game environment area, visible is either a word "visible or "invisible, and arguments are type-specific. Triggers serve as a variables (rules may use them for state-specific behavior). They have a value which can be modified or used in the rules and game-over-conditions.

Steps specification is a list of tuplets [name what from to list-of-when-conditions list-of-side-effects], where name is a word (name of the step), what specifies a figure, from and to specify game equipment, when-conditions give the conditions saying when this step is allowed and side-effects provide a mechanism for coping with consequences of steps performed. Figure is specified in what field as a list of figure-specifications, which are one of

[NAME name-of-figure],

[TYPE type-of-figure],

[ORIGIN name-of-starting-equipment],

[NAME name-with-wildcards list-of-symbols],

[TYPE type-with-wildcards list-of-symbols],

[ORIGIN name-of-starting-equip-with-wildcards list-of-symbols].

(each of NAME, TYPE and ORIGIN appear in a figure-specification at most once).

When using wildcards, list-of-symbols should contain the same number of symbols as is the number of wildcards used and to each symbol a corresponding variable ?symbol? is assigned a value substituted for the wildcard. For example, if the user moves the stone.white.5 and the what is in the form

[[NAME stone.*.? [color num]] [ORIGIN stonegroup1]]

then the ?color? variable will be assigned the value "white and ?num? variable will be assigned number 5. These variables can be used in the when-conditions and side-effects.

Fields from and to of the step specification talk about an equipment from which to which can be a figure moved in one step. The equipment is specified as a list containing up to one NAME and TYPE sublists:

[NAME name-of-equipment]

[TYPE type-of-equipment]

[NAME name-of-equipment-with-wildcards list-of-symbols]

[TYPE type-of-equipment-with-wildcards list-of-symbols]

List-of-when-conditions is a list of Logo expressions, which may use variables from what, from and to fields and several special symbols:

onMove, which is the number of player on move

stepList, which contains names of the steps already performed within this move

at? name-of-figure name-of-equipment, binary predicate testing whether a figure is placed on a given equipment

contains name-of-equipment, an operation returning the list of figures lying on the equipment

value name-of-trigger, operation which returns the value of a trigger.

All conditions must be satisfied in order for move to be approved and all of them are always evaluated.

List-of-side-effects is a list of commands (which may use Logo expressions and symbols from what, from and to and special symbols described above), each of them is one of:

[set name-of-trigger value]

[move name-of-figure-to-move from-equipment to-equipment]

If more than one rule can fire in a given situation, only one candidate (and it is not specified which one) will be used and its variables from when-conditions will be assigned values.

Moves specification is a list of pairs [move-name list-of-step-spec] where move-name is a word and step-spec is one of the following:

step-name

[* step-spec … step-spec]

The first case corresponds to a single step. The second case stands for zero or more repeated occurrences of a sequence of step-specs.

Game-over-conditions specifications is a set of tuplets [condition-name list-of-when-conditions winner] where condition-name is a word, list-of-when-conditions is a list of Logo expressions of the same format as in the steps specifications and a winner is a Logo expression which evaluates to the number of the winning player.

1.4 Implementation point of view

The main principle we tried to follow was to achieve high modularity so that the application can be easily extended and modified. Three modes of operation are clearly identified: game design, playing the game and playing the game against the computer (this will be described separately in the final section). The program maintains a set of figures, equipment and triggers. All of them have some visual representation, i.e. all of them can be drawn. We used a multiple-turtles feature of Comenius Logo to easily implement drag-and-drop. Some operations as well as some attributes are common for all elements. Here are the details:

for equipment:
operations:
accept - to accept a figure which has been dropped over the equipment
release - to release a figure dragged from the equipment
draw - draw the equipment and all figures which lie on it

and attributes:

name
position [x y]
size [height width]
arguments
list-of-accepted-figures

for figures:

operations:
draw

attributes:
name
at
size [height width]
arguments

and for triggers:

operations:
draw
set
get

attributes:

name
value
position [x y]
size [height width]
visible
arguments

1.5 Implementation method

Since the same operations are used for different types of elements and there can be any number of instances of a particular type, we somehow need to implement a mechanism of polymorphism and abstract data type. These are typical for object-oriented design. We chose this paradigm and demonstrated that an object-oriented approach in Comenius Logo is not inappropriate. In fact, it is necessary when designing larger projects.

Each equipment, for example, is stored in a separate ".lgo file" and contains procedures called type.draw, type.accept, type.release, type.init and type.remove and a variable type.attributes. Init and remove stand for constructor and destructor. Constructor is applied whenever an element is dropped in the design mode on the game environment area. All attributes given in the types.attributes variable are constructed first and the constructor receives position and type-specific arguments entered by the user. Destructor is applied when an element is removed from the game during the design process. Draw procedure is called to draw a pictogram of an element. It is applied only once, since the turtle acquires the picture as its shape. The core of the object-oriented engine looks like this:

to call :object :method :arguments
let "self :object
let "p ( word thing ( word :object ".class ) ". :method )
if defined? :p ~
[run se :p map [if word? :% [fput "" :%][:%]] :arguments]
end

to new :name :class :arguments
load_class :class
make "objects fput :name :objects
make word :name ".class :class
let "a thing ( word :class ".attributes )
if not empty? :a [map [[a][make ( word :name ". :a ) 0]] :a]
call :name "init :arguments
end

to delete :name
local "t
make "t thing ( word :name ".class )
if defined? word :t ".remove ~
[call :name "remove []]
let "a thing word :t ".attributes
if not empty? :a [map [[a][erase ( word ": :name ". :a )]] :a]
erase ( word ": :name ".class )
make "objects filter [[a][output not equal? :a :name]] :objects
; here we can unload a class if its last object has just been deleted
end

to setattr :name :attribute :value
make ( word :name ". :attribute ) :value
end

to getattr :name :attribute
if name? ( word :name ". :attribute ) ~
[output thing ( word :name ". :attribute )] ~
[output []]
end

to load_class :class
if not member? :class :classes ~
[load word :class ".lgo ~
make "classes fput :class :classes]
end

The call procedure is responsible for applying a particular method to some object. For each object there exists name.class variable with the name of its class. New and delete procedures are used to construct and destroy objects, setattr and getattr are used for attribute manipulation. The main advantage of this approach is the ability to extend the application. To add a new component (figure, trigger or equipment), one should alter the list of available components and add a new ".lgo" file with a couple of "methods".

1.6 Example

This one will be a game for a single player, a small puzzle. The goal is to get a ball from the starting square to the finish. The player has to explore the path, which looks simple enough, but its behavior is unexpected and the ball jumps to different places after it is moved around the puzzle from square to square.

The starting configuration will consist of 15 squares (s.1 ... s.15) and one ball (b) placed on one of them (s.1). The rules drive the jumps using the side-effects feature. We have one rule for normal progress:

[normal-step []
[[NAME s.? from-square]]
[[NAME s.? to-square]]
[[?to-square? = ?from-square? + 1]
[not member? ?from-square? [3 8]]]
[] ]

Empty list in what field of the step-specification denotes no restrictions. Any figure (in fact there is only one: the ball b) can be moved from any equipment (name of which is assigned to variable ?from-square?) to any equipment (name saved to variable ?to-square?) as long as the when-conditions hold. Thus we can move the ball from anywhere to the adjacent square as long as it doesn’t lie on squares s.3 and s.8. The following rule allows a jump from s.3 and s.8 back to the starting square:

[go-back []
[[NAME * from-square]]
[[NAME s.1]]
[[member? ?from-square? [s.3 s.8]]]
[]]

and the last rule allows the player to overcome the obstacles s.3 and s.8:

[go-forward []
[[NAME s.? from-square]]
[[NAME s.? to-square]]
[[member? ?from-square? [2 7]]
[2 = ?to-square? - ?from-square?]
[]]

The game-over-condition is very simple:

[finish [[at "b "s.15]] 1]

meaning that player 1 is a winner when the ball (b) reaches the last square (s.15).

2 The computer as a player

There would be only little interest in designing a game we cannot play. And when a friend is not available, the computer serves very well. Of course, the model is too general to create fast and effective computer player (except for simple puzzles and games). There are 4 types of computer partners in this application.

First, if the game is for a single player, the application uses iterative deepening algorithm (which is asymptotically optimal in both time and space [3]). The algorithm is described in Lisp in [3]. When a path leading to a solution is found, it is stored and demonstrated. For more complicated problems, the user can provide an evaluation heuristic function (a Logo operation), which is applied to all possible expansions of the current game-state. The best (i.e. with the lowest value) direction is chosen in a hill-climbing manner.

For 2-player games, the program tries to build an AND-OR tree using Minimax algorithm (also described in [3]). When the solution tree is obtained, it is stored and used for playing with the user. The program may be restricted by a certain time factor for each move: if it fails to find a solution tree, it performs a random move. As in the case of the puzzle, the user may provide an evaluation function and the program will not search the tree, rather evaluate only the expanded nodes and chose the one with the lowest value.

3 References

Blaho, A., Kalaš, I., & Mátušová M. (1994) Symbolic Computations and Logo (Lecture Notes Developed Within the Framework of TEMPUS JEP 2063).
Kalaš, I. (1990) Stretnutie s jazykom lisp (Vydavatelstvo alfa, Bratislava) (in Slovak).
Dean, T., Allen, J. & Aloimonos, Y. (1995) Artificial Intelligence Theory and Practice (The Benjamin/Cummings Publishing Company), 141-144.