Ludii Wumpus World
Ludii is a general game system for modeling games and puzzles, although it focuses on historical and traditional games. Ludii was recently used to provide the training data for a Kaggle competition. I noticed their wishlist contained Wumpus World, a common puzzle used for AI training and education. Intrigued, I implemented and submitted a version of Wumpus World.
Wumpus World in the Ludii Player
Background: Hunt the Wumpus / Wumpus World
Hunt the Wumpus was published by Creative Computing magazine in the September-October 1975 issue. The creator, Gregory Yob, describes his desire for a game not set within a Cartesian grid and how the hunter, the Wumpus, and the world’s hazards came together. The game listing in BASIC fits onto a single page and takes 226 lines, including a smattering of comments.
Banner for the Hunt the Wumpus Article
The game was a big success (relative to the time) and the article was reprinted in a “Best Of” issue. The game was ported and recreated for a number of systems.
Two decades later, Russell and Norvig’s textbook Artificial Intelligence: A Modern Approach, uses “Wumpus World” within a series of motivating examples of AI techniques. Wumpus World simplifies the game of Hunt the Wumpus: The cave network is a simple rectangular grid. There are no bats to randomly move the player and the Wumpus and the pits are all static. The interface is normalized with tank-like controls: you can move forward or rotate 90 degrees to the right or left, you may pick up the gold, and you may fire an arrow in the direction you are facing. These simplifications reduce the game to something manageable in first-order logic and easy to model using probabilistic reasoning.
Rules
Wumpus World is a hidden knowledge, single player game set on a 4x4 grid laid out as below. (Variants may randomize the board.) The player’s piece starts at A1. The objective of the game is to pick up the gold and kill the wumpus, in any order.
Divergence: The published rules for Wumpus World also require the player piece to return to the starting position in order to climb out of the cave. I dropped this requirement because backtracking is not fun.
During their turn, a player may move the piece to an orthogonal cell or they may fire their arrow (they have only one) in any orthogonal direction.
Divergence: The published rules only allow forward movement or rotation. Although Ludii can model pieces facing in a single direction, requiring players to rotate and move rather than just move to their desired cell would be annoying friction.
If the player’s piece is othogonally adjacent to a pit, they will receive a percept stating they feel a breeze. If they are orthogonally adjacent to the wumpus, they will receieve a percept of smelling a stench. If they are in the same cell as the gold, they will detect the gold. Player pieces will immediately pick up the gold.
Divergence: The published rules require an explicit action to pick up the gold. This probably has an educational value when teaching students to program agents, but I feel this is an annoying friction within a game. Holding gold carries no penalty (e.g. encumbrance isn’t modeled) so why wouldn’t the gold be picked up at the first opportunity?
If the player’s piece moves into either the wumpus cell or a pit cell, they lose the game.
If the player fires the arrow, it will follow that direction until it either hits a Wumpus, killing it, or hits the wall. Arrows cannot be retrieved once fired. If the arrow hits the Wumpus, the Wumpus will call out in pain informing the player of the Wumpus’s demise.
+---------+---------+---------+---------+
4 | stench | | breeze | pit |
| | | | |
| | | | |
+---------+---------+---------+---------+
3 | wumpus | stench | pit | breeze |
| | breeze | | |
| | gold | | |
+---------+---------+---------+---------+
2 | stench | | breeze | |
| | | | |
| | | | |
+---------+---------+---------+---------+
1 | start | breeze | pit | breeze |
| | | | |
| ==> | | | |
+---------+---------+---------+---------+
A B C D
Game Rules in Ludii
Ludii models games using a declarative language with a S-expression-like syntax. Although the syntax uses S-expressions, Ludii is not a Lisp-like language.
The first “atom” within a S-expression defines the ludeme. Under the hood, each ludeme is implemented by a Java class within the Ludii engine. The top-level game ludeme requires three sub-ludemes: players, equipment, and rules. The complete source code is listed in the appendix and I describe each ludeme block in the sections below. For clarity, I describe the rules prior to the equipment rather than following the order within the file.
Players
The players ludeme defines the number of players and information about each player, if relevant. As a single-player game, the declaration is very simple for this game.
(players 1)
Within the code, P1 denotes the first player. Ludii’s model of ownership includes neutral pieces owned by nobody and shared pieces owned by all players.
A player does not imply human; players may be AI agents or controlled over a network link.
Start Rules (Setup)
The start ludeme is concerned with placing the initial pieces and initializing the board, sites, and players. For Wumpus, the human or player piece is placed in the bottom left. Ludii supports multiple coordinate systems since it supports multiple geometries, but this game seems to be best modeled using spreadsheet like coordinates, so I used coord:"A1" to denote the location. (The original Hunt the Wumpus was played on a dodecahedron with rooms labeled 1 to 20.) I tried modeling the arrow in various ways but placing the arrow into the “hand” of the player turned out to be the most natural option.
(start
{
(place "Human" coord:"A1")
(place "Arrow" (handSite P1))
}
)
I also tried variants by placing pieces representing the Wumpus, the gold, and the pits on the board. By default, pieces are visible (since most games have perfect knowledge, at least for the board) and only one piece per cell is rendered. Rather than fighting convention, I changed those to sites or markings of a grid location.
Although many aspects of the game can be initialized in the start ludeme, general variables (Var) cannot be initialized within this ludeme.
End Rules (Winning and Losing)
There are a number of variants for how to win the game. In the original Hunt, you simply needed to kill the Wumpus. In the CIS587 readings, you need to kill the wumpus, collect the gold, and return to the starting position to climb out of the cave. In the Russel and Norvig text, the highest score is met by finding the gold and climbing out the cave without firing an arrow. I decided to require killing the Wumpus and collecting the gold, but not returning to the original location.
The end rules are modeled as a partial function. If the game state matches the first criteria, the player (Mover) immediately loses. If the game state matches the second criteria, the player immediately wins. Otherwise, play continues.
The "(AtWumpus") and ("AtPit") are ‘defines’ and described later.
(end {
(if (or (and ("AtWumpus") (!= (var "WumpusKilled") 1)) ("AtPit"))
(result Mover Loss)
)
(if (and (= (var "GoldFound") 1) (= (var "WumpusKilled") 1))
(result Mover Win)
)
})
Play Rules
During development, I left the play section as (play (forEach piece)) which allowed me to concentrate on the player movement and interactions with sites. The forEach piece means that each piece’s movement logic (as defined as part of the equipment) may be “played”.
I explored various options for modeling arrow firing. In a general programming system, I’d create four buttons where a button would fire an arrow in one of the cardinal directions. However, Ludii does not have a concept of a generalizable button action. I tried modeling it as a card action, where your hand is populated by N, S, E, and W cards, but that felt unnatural, especially since you would lose access to all cards if you played one. Ludii has a ‘move Shoot’ ludeme which I could have used, but the user interface was clunky between choosing to move or choosing to shoot.
I found that modeling the firing of an arrow as taking an arrow from the hand has a number of advantages. One, in the user interface, it is a very explicit choice and does not collide with piece movement. Two, pieces in the hand can have a count attached to them, if a game variant that allows more arrows is desired.
(play
(or
(forEach piece)
(move
(from (handSite P1))
(to (sites LineOfSight Farthest at:(where "Human" P1) Orthogonal))
(then ("ArrowLogic"))
)
)
)
Rather than including the arrow firing logic in the play ludeme, it could be attached to the piece description in the equipment section —- that is where the logic for the human piece is located. Ultimately, I decided to place the logic in the play ludeme because of its “exceptional” behavior; the arrow is not a regular piece as it is a consumable and does not stay after being placed. The human piece, in contrast, is permaneant and something that will be moved multiple times.
Defines
Defines are an optional feature within the Ludii language to extract ludemes from their regular position. Defines are used to reduce repeated code and attach semantic labels to logic.
Predicates
I created five predicates to simplify expressions. All of them ask if the current location of the human ((where "Human" P1)) intersections within certain sets of locations. The labeled lists of sites or regions are created in the equipment ludeme.
(define "IsNextToPit" (is In (where "Human" P1) (sites "Breeze")))
(define "IsNextToWumpus" (is In (where "Human" P1) (sites "Stench")))
(define "AtGold" (is In (where "Human" P1) (sites "Gold")))
(define "AtPit" (is In (where "Human" P1) (sites "Pits")))
(define "AtWumpus" (is In (where "Human" P1) (sites "Wumpus")))
Alternatively, parameterized defines could be used to remove the repetition:
(define "AtSite" (is In (where "Human" P1) (sites #1)))
and called via:
("AtSite" "Gold")
Arrow Path
When the player fires an arrow, they select one of the orthogonal positions farthest from the human. This is achieved via the sites LineOfSight ludeme and the appropriate filters:
(move
(from (handSite P1))
(to (sites LineOfSight Farthest at:(where "Human" P1) Orthogonal))
(then ("ArrowLogic"))
)
Once the arrow is fired, we need to check all the sites between the human and the farthest point. The sites Between filter is useful for selecting these sites. By default, the filter excludes the ends, so we include the end with the arrow. Since the human is killed if they enter a room with the wumpus, there is no need to check the human’s current position.
(define "ArrowPath"
(sites Between Orthogonal
from:(where "Arrow" P1) fromIncluded:True
to:(where "Human" P1)
)
)
Arrow Firing (ArrowLogic)
Using the path of the arrow, we need to check if the arrow enters any room with the Wumpus. I couldn’t use is In because it requires a single site and (sites "Wumpus") returns a set, so I converted the sets to arrays of integers via array and used the array intersection ludeme as an “exists” operator by checking the size.
I wish Ludii had an progn for processing multiple side-effects in sequence. Lacking that, I combined the multiple effects using logical operators per the documentation. If the Wumpus' location is in the set of locations of the arrow path, we set the WumpusKilled variable. In both cases, we provide a note to tell the player what happened and then remove the arrow from the board. If we did not remove the arrow, it would remain in the farthest location, potentially blocking the human’s movement.
(define "ArrowLogic" (if (= 0 (size Array (intersection (array (sites "Wumpus")) (array ("ArrowPath")))))
(and
(note "Thunk! The arrow hits a wall. You have failed to kill the wumpus.")
(remove (where "Arrow" P1) at:EndOfTurn)
)
(and
(or
(set Var "WumpusKilled" 1)
(remove (where "Arrow" P1) at:EndOfTurn)
)
(note "The wumpus yells in pain and dies")
)
)
)
note and Percepts
A key aspect of the game is that the player is given clues to the positions of hazards. Ideally, this information could be annotated on the board, or lighting an indicator, but I didn’t find a way to achieve that. Ultimately, I used the note ludeme which is a way to write a message to the player. Although the game is traditionally text driven, this aspect of the game should be modeled more explicitly especially for the benefit of generic game playing agents.
Equipment
The equipment ludeme defines the board, pieces, and other semi-physical aspects of the game. Logic for how pieces are used in the game can be attached to their definition or placed within the play ludeme within the rules.
Non-Human Pieces and Sites
Wumpus World uses a square grid of cave rooms, which can be easily declared as a (board (square 4)). Within the equipment ludeme we also define starting locations for all elements using spreadsheet coordinates.
I decided to “pre-compute” the locations where the human will feel a breeze or smell a stench by setting those locations based on the existing regions. Using sites Around I can have the computer compute the set of sites rather than manually set them like Gold, Pits, and Wumpus.
The pieces are declared in the equipment ludeme but placed in the start ludeme (above).
(equipment
{
(board (square 4))
// ... human piece defined here ...
(hand P1 size:1)
(piece "Arrow" P1)
(regions "Gold" (sites {"B3"}))
(regions "Pits" (sites {"C1" "C3" "D4"}))
(regions "Wumpus" (sites {"A3"}))
(regions "Stench" (sites Around (sites "Wumpus") Orthogonal))
(regions "Breeze" (sites Around (sites "Pits") Orthogonal))
}
)
Human Piece
The human piece (human was chosen as the name because it fit an existing Ludii graphic) is owned by the first player, P1, and can move one step orthogonally each turn. The syntax requires an explicit to ludeme. We restrict moves to locations that are empty. Since there is only one piece on the board, this restriction is unnecessary.
Ludii lacks a switch or match structure, so we need to chain the effects of various sites using logical operators. The logic is complicated because the conditions are not exclusive to each other. I use defines heavily here to reduce the clutter.
The end game messages are handled here because the syntax does not allow them within the end rules.
(piece "Human" P1
(move Step Orthogonal
(to if:(is Empty (to) ))
(then
(or
(if (and ("AtGold") (!= (var "GoldFound") 1))
(and
(set Var "GoldFound" 1)
(note "You found the gold")
)
)
(and
(and
(if ("IsNextToPit") (note "You feel a breeze. A pit is nearby!"))
(if ("IsNextToWumpus") (note "Your nose wrinkles from the strong stench. A wumpus is nearby!"))
)
(and
(if ("AtPit") (note "You fall into a pit and die."))
(if (and ("AtWumpus") (!= (var "WumpusKilled") 1)) (note "You are eaten by the wumpus."))
)
)
)
)
)
)
As an alternative to the variables, I could use trigger and is Triggered to track boolean states. Although they are referenced as events within the documentation, there does not appear to be a way to explicitly process some side effect whenever the trigger occurs. However, they could be checked explicitly within the play ludeme during turn execution.
Developer Experience
I often found the development process to be tedious. The Ludii language is defined and enforced through a grammar, but the parser seemed unable to give the developer any explanation of what was incorrect. Rather, if something is wrong, a stack exception will be printed to the console, typically with no sense of which line is wrong. For instance, a missing parentheses would show a StringIndexOutOfBoundsException. By following a very incremental approach, I could at least restrict problems to the lines that had changed and that allowed progress.
That said, the succinct nature of the language is very appealing. As a declarative language, the developer is able to concentrate on the core rules and mechanics and gets a user interface for “free.”
Applicability to “Modern” or Euro-Style Games
I recently played Creature Caravan, a worker-placement game published in 2024. Each player in the game controls a caravan that moves across a shared board gathering points. Players draw cards and activate powers from creatures they add to their tableau. The game provides players with many options each turn and, since cards are unique, there are many interacting systems. If someone attempted to model this game in Ludii, I think:
- Tracking the caravans across the main board would be straight-forward along with marking locations for the mountains, lakes, towers, and such
- Restricting actions to the “core” should be feasible, with workers from the hand being played to specific locations
- Modeling cards that are recruited to the tableau would likely be infeasible or very complex. While some creatures are relatively simple (place a worker to gain 2 bread), many have meta abilities like reducing costs or feeding other cards.
With the addition of new ludemes, additional styles of games may be supported more easily. The Ludii language does not support adding new ludemes within itself (defines are more of a macro system), so this would require development within the Java source code. This is not a focus area for the Ludii team who are more interested in historical and abstract games.
Conclusion
My submission of Wumpus World was accepted in February 2025 and is part of the 1.3.14 release. The Ludii team has secured additional funding to “inspire methodologies and applications on how to use game AI to study, reconstruct, and preserve the intangible cultural heritage of games”.
Appendix: Source code for version 1.0.0
This listing does not include the “info” block which contains metadata about the game.
|
|
Links
Hunt the Wumpus in Creative Computing