I (and perhaps others) will be posting some exercises here. These are not really bound to chapter 2, people can make them whenever they want, but the exercises in this thread assume you've read Chapters 1 & 2.
Let's see if this'll revitalize this workshop...
Pearls before swine
Write a perfect AI which can play at
this game. The rules are
- The game starts with a number of rows each containing a number of pearls.
- Each player, in turn, will choose a row and remove an arbitrary number of pearls from this row.
- The player who is left with one pearl loses the game.
So, you need to write a function which, given a description of the current game state, returns which move to make in order to win. If there is no such move, it must let this know in some way.
I'll provide hints in increasing order of helpfulness. These lead you onto a path that I chose to solve the problem, but as I'm not an AI expert, there very well may be far better ways to solve this problem. My solution has the quality of being rather short and simple to write in a functional setting.
Hint #1
Let's use the word
configuration (cfg) to denote the number of pearls in each row; combined with the information of whose turn it is it describes the entire state of a game. A configuration can be represented as a simple list whose length equals the number of rows and whose elements represent the number of pearls in each of their respective row, e.g. the list (1 0 0 0) represents the configuration which the players need to avoid receiving.
A configuration C's
expansion is the set of all configurations which a player can reach by making a legal move, i.e. removing pearls from one row. An example is expanding (1 2 3) gives the set containing (0 2 3) (1 0 3) (1 1 3) (1 2 0) (1 2 1) (1 2 2). Also, the (0 0 0) configuration should never appear in an expansion.
Using expansion, one can build an entire tree (it's a tree, not a graph, since there are no cycles possible) and use this tree to determine which move will be the best.
The goal of this exercise is thus to write a function taking a single argument, a configuration, and returning a new configuration which represents the new configuration after a winning move. Example: (winning-move '(5 0)) should return (1 0).
Hint #2
We can discern two kinds of configurations in the light of a perfect AI:
- The guaranteed-to-lose configurations (an L-config): no matter what you do, the perfect AI will crush you in the end.
- The possibly-win configurations (a W-config): as long as you don't make any mistakes, you will win.
So, the 'winning-move' function will have to return a new configuration if a W-config is provided, or indicate it's hopeless if it's given an L-config.
As a help, you can write the functions 'winning?' and 'losing?' which given a configuration determine whether it is an L- or a W-config. It's always either one or the other, there are no configs for which both return the same result. The 'winning-move' function will then pick one of the L-configs in the expansion of its argument:
(winning-move '(5 0))
Expansion:
((1 0) (2 0) (3 0) (4 0))
L W W W
Hint #3
An L-config is one in which you cannot win, hence it means that its expansion contains nothing but W-configs. A W-config is the other way around: the expansion needs to at least contain one L-config.
In code:
(define (winning? cfg)
(any losing? (expand-config cfg)))
(define (losing? cfg)
(all winning? (expand-config cfg)))
;; or, should work too
(define (losing? cfg)
(not (winning? cfg)))
'any' and 'all' have yet to be written: both take a predicate and a lst, 'any' represents or-like functionality, 'all' and-like: (any odd? '(1 2 3)) == #t, (all odd? '(1 2 3)) == #f.
Hint #4
The expansion function is by the hardest part of this exercise. A 'range' function might come in handy: (range 1 5) --> (1 2 3 4 5).
Given a configuration (a b c), the function should return
((0..a-1) b c)
(a (0..b-1) c)
(a b (0..c-1))
and also making sure (0 0 0) is filtered out.
Hint #5
The expansion function in Haskell-form would be (the filtering of (0 0 0) has yet to be done):
expandConfig [] = []
expandConfig (x:xs) = [ y:xs | y <- [0 .. x-1]] ++
[ x:ys | ys <- expandConfig xs ]
The ':'-operator is Haskell's equivalent for cons, '++' is appending, and '[expr | x <- lst]' assigns each of lst's elements in turn to x and evaluating expr and collects the results in a list, e.g. [ x * x | x <- [1 .. 4] ] gives [1, 4, 9, 16].
Hint #6
The expansion function in Scheme:
(define (expand-config cfg)
(define (expand cfg)
(if (null? cfg)
()
(append (map (lambda (x) (cons x (cdr cfg)))
(range 0 (- (car cfg) 1)))
(map (lambda (x) (cons (car cfg) x))
(expand (cdr cfg))))))
(filter (lambda (cfg)
(any (lambda (x)
(not (= x 0)))
cfg))
(expand cfg)))
Solution
;;
;; Auxiliary functions
;;
(define (range a b)
(define (range b acc)
(if (< b a)
acc
(range (- b 1)
(cons b acc))))
(range b ()))
(define (all pred lst)
(or (null? lst)
(and (pred (car lst))
(all pred (cdr lst)))))
(define (any pred lst)
(not (all (lambda (x) (not (pred x))) lst)))
(define (filter pred lst)
(cond ((null? lst)
())
((pred (car lst))
(cons (car lst)
(filter pred (cdr lst))))
(else
(filter pred (cdr lst)))))
;;
;; Pearl-specific code
;;
(define (expand-config cfg)
(define (expand cfg)
(if (null? cfg)
()
(append (map (lambda (x) (cons x (cdr cfg)))
(range 0 (- (car cfg) 1)))
(map (lambda (x) (cons (car cfg) x))
(expand (cdr cfg))))))
(filter (lambda (cfg)
(any (lambda (x)
(not (= x 0)))
cfg))
(expand cfg)))
(define (winning? cfg)
(any losing? (expand-config cfg)))
(define (losing? cfg)
(not (winning? cfg)))
(define (winning-move cfg)
(let ((moves (filter losing? (expand-config cfg))))
(if (null? moves)
'impossible
(car moves))))
This code is quite slow, there are many optimisations to be made, the most interesting being memoization, but that's something for Chapter 3.
We could hold a contest now to see whose code will solve (winning-move '(2 3 4 5)) fastest.
;; Using the code above
(time (winning-move '(2 3 4 5)))
cpu time: 10385 real time: 10675 gc time: 2744
impossible
;; Using a bit more optimized version
;; (still relying exclusively on Chapters 1 and 2)
> (time (winning-move '(2 3 4 5)))
cpu time: 2634 real time: 2654 gc time: 801
impossible
