Zillions of Games is a commercial General Game Playing

General Game Playing

General Game Playing is the design of artificial intelligence programs to be able to play more than one game successfully. For many games like chess, computers are programmed to play these games using a specially designed algorithm, which cannot be transferred to another context. For example, a...

 system developed by Jeff Mallett and Mark Lefler in 1998. The game rules are specified with S expressions, Zillions rule language. It was designed to handle mostly abstract strategy board game

Board game

A board game is a game which involves counters or pieces being moved on a pre-marked surface or "board", according to a set of rules. Games may be based on pure strategy, chance or a mixture of the two, and usually have a goal which a player aims to achieve...

s or puzzle

Puzzle

A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...

s. After parsing the rules of the game, the system's artificial intelligence

Game artificial intelligence

Game artificial intelligence refers to techniques used in computer and video games to produce the illusion of intelligence in the behavior of non-player characters . The techniques used typically draw upon existing methods from the field of artificial intelligence...

 can automatically play one or more players. It treats puzzles as solitaire games and its AI can be used to solve them.

Scripting language

The scripting language of Zillions-of-Games uses S expressions. The rules are stored in a text file with extension ".zrf" (zillions rules file). The users can create their own ZRF-files and make the AI of Zillions-of-Games play their newly created game.

Here is an example of rules for Tic-tac-toe

Tic-tac-toe

Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...

 (copyright by Zillions Development Inc.):

(define add-to-empty  ((verify empty?) add))



(game

   (title "Tic-Tac-Toe")

   (description "...")

   (history "...")

   (strategy "...")

   (players X O)

   (turn-order X O)

   (board

        (image "images\TicTacToe\TTTbrd.bmp")

        (grid

            (start-rectangle 16 16 112 112) ; top-left position

            (dimensions ;3x3

                ("top-/middle-/bottom-" (0 112)) ; rows

                ("left/middle/right" (112 0))) ; columns

            (directions (n -1 0) (e 0 1) (nw -1 -1) (ne -1 1))

        )

   )

   (piece

        (name man)

	(help "Man: drops on any empty square")

	(image X "images\TicTacToe\TTTX.bmp"

	       O "images\TicTacToe\TTTO.bmp")

        (drops (add-to-empty))

   )

   (board-setup

        (X (man off 5))

        (O (man off 5))

   )



   (draw-condition (X O) stalemated)

   (win-condition (X O)

	  	(or (relative-config man n man n man)

                    (relative-config man e man e man)

                    (relative-config man ne man ne man)

                    (relative-config man nw man nw man)

		)

    )

)

The result of loading of this ZRF into Zillions-of-Games and playing against the computer is shown in screenshot at right.

The definition of games usually contains the following pattern:

• Game title. One ZRF can contain more than one game and game title allows the user to select a certain game.
• Description, history and strategy of the game. This is a text which shown to the user on demand to explain game rules, history and to give general gameplay advice.
• Players. This is a list of player names used in the game. For example, for chess it would be White, Black. The player name is used in some further places, for example in initial position or game goal definitions. There could be just one player (e.g. for puzzles), two or more.
• Turn order This specifies the order of moves made by the players. In the example above, the player X starts, the player O moves and then the whole sequence repeats. The definition of turn-order can be more complex, for example for balanced double-move chess it would be: (turn-order White repeat Black Black White White), which specifies the following order of moves: White, Black, Black, White, White, Black, Black, White, White, etc.

• Board definition. This sections specifies geometry of the playing board, separate positions of the board and connections between them. The board definition in the example above first specifies a bitmap image to be used for the board. A 2-dimensional board is defined using pixel coordinates from the bitmap. The definition ("top-/middle-/bottom-" (0 112)) specified notations to be used for rows as well as an offset in pixels between rows. The text notation is used in move list, as well for saving the played game into ".zsg" (zillions saved game) file. The connections between board position is specifed in (directions ...) statement. The example above defines four directions: n (north) - one step up, e (east) - one step right, nw - diagonally up-left and ne - diagonally up-right. The directions are used in move definitions as well as in game goal definitions.
• Piece definition. Defines pieces used in the game, their names and how they moved. In the example above one pieces is defined, Man, which can be dropped on any empty position of the board. Besides this two bitmaps for X and O players are specified.
• Board setup. Specifies initial position of the game. The example above defines that the board is empty initially and each side has 5 pieces off the board, which can be dropped.
• Goal of the game. Condition when one of players wins or when draw occurs. In Tic-Tac-Toe win condition (3-in-a-row) is defined as relative piece configurations, using directions n, e, ne and nw from board definition.

Implemented games

Zillions of Games is so called because of its potential to play a very large number of user-programmed games. The system is shipped with over 300 games and puzzles. These include a lot of popular board games, such as Alquerque

Alquerque

Alquerque is a strategy board game that is thought to have originated in the Middle East. It is considered to have been the parent of draughts and Fanorona.-History:...

, Fox and geese, Go

Go (board game)

Go , is an ancient board game for two players that originated in China more than 2,000 years ago...

, Gomoku

Gomoku

Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game...

, Jungle

Jungle (board game)

Jungle or Dou Shou Qi is a traditional Chinese board game. It is also known as Jungle Chess or Animal Chess. It is a two player, abstract strategy game played on a 7x9 board...

, Halma

Halma

Halma is a board game invented in 1883 or 1884 by an American thoracic surgeon at Harvard Medical School, George Howard Monks. The inspiration was an English game called Hoppity, which was devised in 1854....

, Nim

Nim

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap....

, Nine Men's Morris

Nine Men's Morris

Nine Men's Morris is an abstract strategy board game for two players that emerged from the Roman Empire. The game is also known as Nine Man Morris, Mill, Mills, Merels, Merelles, and Merrills in English....

, Reversi

Reversi

Reversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...

, Tafl

Tafl games

Tafl games were a family of ancient Germanic and Celtic board games played on a checkered or latticed board with two teams of uneven strength. The size of the board and the number of pieces varied, but all games involved a distinctive 2:1 ratio of pieces, with the lesser side having a king-piece...

and Tic-tac-toe

Tic-tac-toe

Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...

. The package includes many checkers variants, for example Russian

Russian checkers

Russian draughts is a variant of draughts played in some parts in Russia and some parts of the former USSR, as well as parts of Eastern Europe and Israel.-Rules:...

and Turkish Checkers. Besides standard FIDE chess

Chess

Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

, Zillions of Games contains many national chess variants such as Shogi

Shogi

, also known as Japanese chess, is a two-player board game in the same family as Western chess, chaturanga, and Chinese Xiangqi, and is the most popular of a family of chess variants native to Japan...

, Xiangqi

Xiangqi

Xiangqi is a two-player Chinese board game in the same family as Western chess, chaturanga, shogi, Indian chess and janggi. The present-day form of Xiangqi originated in China and is therefore commonly called Chinese chess in English. Xiangqi is one of the most popular board games in China...

, Janggi

Janggi

Janggi , sometimes called Korean chess, is a strategic board game popular in Korea. It derived from Xiangqi , which itself is thought to be a descendent of the Indian chess game Chaturanga...

, as well as a number of popular chess variants like Ultima

Baroque chess

Baroque chess is a chess variant invented in 1962 by Robert Abbott. In 1963, at the suggestion of his publisher, he changed the name to Ultima, by which name it is also known...

, Extinction chess

Extinction chess

Extinction chess is a variant of western Chess where the objective of the game has changed. Instead of the winning condition of the game being the checkmate of the opponent's king, the object of the game is to capture all of a particular kind of piece the opponent has...

, Losing Chess, Shatranj

Shatranj

Shatranj is an old form of chess, which came to the Western world from India. Modern chess has gradually developed from this game.-Etymology and origins:...

, Berolina chess

Berolina chess

Berolina Chess is a chess variant using a popular fairy chess piece called the Berolina pawn...

, Grand chess

Grand chess

Grand chess is a popular large-board chess variant invented by Dutch games designer Christian Freeling in 1984. It is played on a 10×10 board, with each side having two additional pawns and two new pieces: the marshall and the cardinal....

 and others. It also include some puzzles, such as 15-Puzzle

N-puzzle

The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle...

, Towers of Hanoi, eight queens

Eight queens puzzle

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal...

, and a variety of Solitaires

Peg solitaire

Peg solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known simply as Solitaire in the United Kingdom where the card games are called Patience...

.

Not long after it came to market in late 1998, users of Zillions of Games began to program new games and puzzles for it, creating many of them themselves. Two large collections of Zillions Rules Files (ZRFs) soon began to appear. One was at the Zillions-of-Games website, and the other was at the Chess Variant Pages website. The former collected together every kind of ZRF, whereas the latter focused on ZRFs for chess variant

Chess variant

A chess variant is a game related to, derived from or inspired by chess. The difference from chess might include one or more of the following:...

s. As of 2011, the ZILLIONS interface had 1,953 ZRFs, created by 410 ZRF authors, and the Chess Variant Pages collection had 800 ZRFs of chess variants.

The games programmed by the users include such games as 4D Tic-Tac-Toe, FreeCell

FreeCell

FreeCell is a solitaire-based card game played with a 52-card standard deck. It is fundamentally different from most solitaire games in that nearly all deals can be solved...

, Rubik's Cube

Rubik's Cube

Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...

, Teeko

Teeko

Teeko is an abstract strategy game invented by John Scarne in 1937 and rereleased in refined form in 1952 and again in the 1960s. Teeko was marketed by Scarne's company, John Scarne Games Inc.....

, Mancala

Mancala

Mancala is a family of board games played around the world, sometimes called "sowing" games, or "count-and-capture" games, which describes the game-play. Mancala games play a role in many African and some Asian societies comparable to that of chess in the West, or the game of Go in Eastern Asia...

, Alice chess

Alice Chess

Alice Chess is a chess variant invented in 1953 by V. R. Parton which employs two chessboards rather than one, and a slight alteration to the standard rules of chess...

, Chess960

Chess960

Chess960 is a chess variant invented and advocated by former World Chess Champion Bobby Fischer, originally announced on June 19, 1996 in Buenos Aires, Argentina. It employs the same board and pieces as standard chess, but the starting position of the pieces is randomized along the players' home...

, Hexagonal chess, Star Trek Tridimensional Chess

Three-dimensional chess

Three-dimensional chess is any of various chess variants played on three-dimensional boards. Three-dimensional variants have existed since the late 19th century, one of the oldest being Raumschach , invented in 1907 by Dr. Ferdinand Maack and considered the classic 3D game...

 and Sokoban

Sokoban

is a type of transport puzzle, in which the player pushes boxes or crates around in a warehouse, trying to get them to storage locations. The puzzle is usually implemented as a video game....

. Besides various games and puzzles, there are also educational ZRFs, such as the cellular automata

Cellular automaton

A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...

 Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

, a calculator, and some Turing machine

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

 simulations.

Uses

Zillions of Games can be used for the following:

• Playing any of the games or puzzles that come with it.
• Playing any of the thousands of free games and puzzles that have been programmed for it by users.
• Playing games with remote users through the internet or a dialup connection.
• Playing games by emailing ZSG files back and forth.
• Programming it to play new games and puzzles.
• Using it as a development tool for the creation of new games and puzzles.
• Testing new games for drawishness and other qualities by having Zillions play them against itself.
• Solving puzzles or making sure that newly created puzzles can be solved.
• Creating diagrams that can be cut out of screen captures.

Capabilities

Zillions represents boards and pieces with bitmap images; these can be remapped by the user. The boards may be arbitrary directed graphs, but standard grid-like boards are easier to produce and have built-in support for detecting collinearity. The available win, loss, and draw conditions include checkmate, stalemate, repetition, piece capture, absolute configuration, relative configuration, and various types of piece count. These allow the creation of a variety of different games and puzzles.

Besides defining how pieces move, Zillions can define how pieces may be dropped. This is for introducing new pieces into a game. It is not useful for Shogi, which "drops" captured pieces stored on the sides of the board. It is for games like Go, Reversi, and Tic-Tac-Toe, which routinely allow users to add new pieces to the board. As with piece movement, this is defined algorithmically, and it can be something as simple as letting a new piece drop only on an empty space or follow more complex rules.

Since version 2.0, Zillions has had the additional ability to enforce maximal capturing rules (used in some versions of Checkers) and a full-featured Go-playing engine.

Zillions includes a "random player" which selects from its available moves at random; this can be used to simulate dice in race game

Race game

Race game is a large category of board games, in which the object is to be the first to move all one's pieces to the end of a track. This is both the earliest type of board game known, with implements and representations dating back to at least the 3rd millennium BC in Egypt, Iraq, and Iran; and...

s and Backgammon

Backgammon

Backgammon is one of the oldest board games for two players. The playing pieces are moved according to the roll of dice, and players win by removing all of their pieces from the board. There are many variants of backgammon, most of which share common traits...

 relatives.

The standard AI engine can, if need be, be replaced with user-created engines. These engines can then use opening book

Opening book

Chess opening book refers either to a book on chess openings, or to a database of chess openings used by chess programs.-Literature:Opening books, which discuss chess openings, are by far the most common type of literature on Chess play...

s or other features unavailable to the standard AI.

Limitations

Despite its versatility, Zillions of Games has a number of non-trivial limitations:

• Zillions Of Games is designed to play perfect information
  Perfect information
  In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
  
   games exclusively. This renders it of little or no use in fairly playing imperfect or hidden information games against the AI, such as card games or board games with hidden piece values like Stratego
  Stratego
  Stratego is a board game featuring a 10×10 square board and two players with 40 pieces each. Pieces represent individual officers and soldiers in an army. The objective of the game is to either find and capture the opponent's Flag or to capture so many of the opponent's pieces that he/she cannot...
  
  . Instead, the program will automatically use all information available to itself, including the cards in the deck and the cards in the hands of all other players. The games may still be played by human players, although there is no support for revealing information selectively to only one player.
• Its programming language lacks support for arithmetic, for functions, and for variables beyond some boolean flags.
• The engine does not have built-in support for connection-based goals such as in Hex; thus these goals must be implemented by hand.
• There is also no support for having multiple pieces per location, or for pieces covering multiple locations at once. Thus, complicated workarounds are required for games that need these features, such as Mancala
  Mancala
  Mancala is a family of board games played around the world, sometimes called "sowing" games, or "count-and-capture" games, which describes the game-play. Mancala games play a role in many African and some Asian societies comparable to that of chess in the West, or the game of Go in Eastern Asia...
  
  , Laska or Quoridor
  Quoridor
  Quoridor is a 2- or 4-player abstract strategy game designed by Mirko Marchesi and published by Gigamic Games. Quoridor received the Mensa Mind Game award in 1997 and the Game Of The Year in the USA, France, Canada and Belgium.-Rules of the game:...
  
  .
• Like most AI game playing programs, the default engine plays poorly in games with large branching factors, such as Shogi
  Shogi
  , also known as Japanese chess, is a two-player board game in the same family as Western chess, chaturanga, and Chinese Xiangqi, and is the most popular of a family of chess variants native to Japan...
  
  .
• In some vital respects, the program is too restrictive in what it allows.
  • Although it can recognize repetition, the only kind it can recognize is threefold repetition
    Threefold repetition
    In chess and some other abstract strategy games, the threefold repetition rule states that a player can claim a draw if the same position occurs three times, or will occur after their next move, with the same player to move. The repeated positions need not occur in succession...
    
    .
  • Although it can check for various win, loss and draw conditions at the end of a move, it cannot check for any of them when evaluating possible moves for a piece. Consequently, in Shogi, for example, it cannot be programmed to always accurately enforce the rule against checkmating
    Checkmate
    Checkmate is a situation in chess in which one player's king is threatened with capture and there is no way to meet that threat. Or, simply put, the king is under direct attack and cannot avoid being captured...
    
     a King with a Pawn drop.
  • Many multi-person chess variants cannot be played because it will immediately stop the game when the first player is checkmated or stalemated
    Stalemate
    Stalemate is a situation in chess where the player whose turn it is to move is not in check but has no legal moves. A stalemate ends the game in a draw. Stalemate is covered in the rules of chess....
    
    .
• In some cases, the quality of gameplay is compromised due to the AI automatically calculating piece values inaccurately with no option available for manually overriding it with accurate piece values.

External links

• Zillions of Games homepage
• A review of Zillions of Games by Hans Bodlaender
• Zillions Games by Karl Scherer.