Yellow Rabbit

Trilobite: the Game in Lisp

Trilobite Game in Lisp: Problem Statement

Formulation of the problem

In the 11th hour game a puzzle came into play, the purpose of which is to build 4 chips in a row. And you can not select the row for the new chip, you can select only the column.

Trilobite original game screen I can not beat the computer in this mini-game, so I’ll try to arrange a battle of the two AIs. It would be fun to write an opponent for a computer on Lisp, since I’m practically not familiar with this language.

First I read Land of Lisp: Learn to Program in Lisp, One Game at a Time! to understand how one can write games in this language. As a compiler/interpreter, I use SBCL, as one of the available (/usr/dports/lang/sbcl) for DragonFly BSD.

Playing field (board)

From the book it became clear that the board I needed (the size 8x7) I most likely will not be able to implement without the experience of optimizing programs on Lisp. So let’s start with a tiny 3x3 board, on which, nevertheless, it will be possible to work out the logic of artificial intelligence.


;; *** Consts
;; board
(defparameter *board-width*  3)
(defparameter *board-height* 3)
(defparameter *board-size*   (* *board-width* *board-height*))

The condition for victory will also be considered a shorter line of chips:


;; row length for win
(defparameter *win-len* 3)

Each square of the board can be in one of three states:

  1. be empty;
  2. contain an opponent’s chip;
  3. contain our chip.

;; cell types
(defparameter *empty-cell* 0)
(defparameter *ai-cell*    1)
(defparameter *human-cell* 2)

defparameter not exactly what I need, I rather prefer good old #define, but I have not yet found any substitution for real constants in Lisp.

A board is an array of cells. It can be created either completely from empty cells, or by copying from the list of cells, and I will copy often because there will be a lot of boards with different combinations of chips.


;; *** Board
;; two dimentional array of cells
;; . X ->
;; Y
;; |
;; v
;; initial board
(defun new-board ()
  (make-array *board-size* :initial-element *empty-cell*))

;; make board from list
(defun board-from-list (lst)
  (make-array *board-size* :initial-contents lst))

It is necessary to introduce the concepts of players in order to somehow distinguish whose turn is now, etc.


;; players
(defparameter *ai-player*    1)
(defparameter *human-player* 2)

(defun change-player (player)
  (if (eql player *ai-player*)
    *human-player*
    *ai-player*))

(defun get-player-color (player)
  (if (eql player *ai-player*)
    *ai-cell*
    *human-cell*))

(defun get-player-str (player)
  (if (eql player *ai-player*)
    "The Evil AI"
    "Human"))

Back to our board, we describe a couple of auxiliary functions for accessing and checking cells.


;; get board cell
(defun get-cell (board cell)
  (aref board cell))

;; cell type predicates
(defun cell-emptyp (board cell)
  (eql (get-cell board cell) *empty-cell*))

(defun cell-playerp (board cell player)
  (eql (get-cell board cell) player))

At the moment, you can take a look at the work of the board:


% rlwrap sbcl --load trilobite.lisp
This is SBCL 1.2.9, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (board-from-list '(1 2 3 4 5 6 7 8 9))

#(1 2 3 4 5 6 7 8 9)
* (new-board)

#(0 0 0 0 0 0 0 0 0)
* (cell-emptyp (new-board) 4)

T
* (get-cell (new-board) 4)

0
* (cell-playerp (new-board) 4 *ai-player*)

NIL
* (exit)