2012-09-03

Design

I still haven’t figured out how the code I’ve been developing will fit into the larger picture, so here are some brainwave snippets.

It occurs to me when contemplating the problems involved with castling that functional programming may have a leg up on OO programming when it comes to modeling, specifically because there’s no implicit requirement that the code model real-world objects. I can define a castling process and no one will blink an eye.

I’m also beginning to wonder if I really want pieces to keep their current location in state. The board will have to keep track of who’s where, so that means there are at least two places in memory where the location is stored, which is risky; additionally, because my code today primarily checks for move legality without concern over obstacles, pinning and the like, it’s entirely possible that I would have to move a piece back.

So, for today’s first task, let’s turn the code back into strictly a legal move checker, with no state other than the move functions.1

Task 1: Statelessness

Goal: we need exactly one pawn process, one queen process, one knight process, etc.2 Each one only checks the legality of a move.

First question: what messages do we need, incoming and outgoing?

Inbound

{ Pid, move, Start, End, Team }
{ Pid, capture, Start, End, Team }
done

Start and End will be tuples, Team an atom, as today. I’m going to rename From to Pid because From could be misinterpreted as the square at the start of the move.

Guards go away; this solves the Chinese Chess board problem I mentioned previously. It’ll be up to some other process to make sure that the targeted square is actually on the board.

Since guards go away, so does this error check:

{ _, _, {X, Y} } ->
    throw({invalid_destination, {X, Y}});

And, of course, the location check message.

Finally, our recently-added promotion message is no longer relevant.

Outbound

For our outbound messages, it’s tempting to just respond with yes or no (or true/false), but there’s always the danger that in a distributed concurrent system that messages might arrive out of order.

The board presumably would only be asking one piece to move at a time, but perhaps we’ll use this for pin checks; maybe we’ll ask whether any of the black pieces can capture the white king, and there’s no inherent reason why we’d have to ask that question in serial.

This also makes me think that each process should know what type of piece it represents. Let’s assume that it does, so our message back should be one of:

{ yes, Piece, Start, End }
{ no, Piece, Start, End }

Perhaps we won’t need all that information on the receiving end; in fact, we probably won’t, but it’s easy to streamline that later.

piece_loop parameters

We no longer need Location or Team, but we’ll add an atom variable for Piece.

New code

We don’t have to touch the move functions at all.

piece_loop(Piece, Move, Capture) ->
    receive
        { Pid, move, Start, End, Team } ->
            move_response(Pid, Piece, Start, Move(Start, End, Team), End),
            piece_loop(Piece, Move, Capture);
        { Pid, capture, Start, End, Team } ->
            move_response(Pid, Piece, Start, Capture(Start, End, Team), End),
            piece_loop(Piece, Move, Capture);
        done ->
            done;
        Message ->
            throw({unknown_message, Message})
    end.

move_response(Pid, Piece, Start, Start, End) ->
    Pid ! { no, Piece, Start, End };
move_response(Pid, Piece, Start, End, End) ->
    Pid ! { yes, Piece, Start, End }.

Because the loop no longer tracks the current location, move_response is no longer responsible for returning that location. Overall, I’m much happier with this code. Looks far cleaner (of course, it’s also doing less)3.

And the shell test:

7> Knight = spawn(piece, piece_loop, [ knight, Kn, Kn ]).
<0.101.0>
8> flush().
ok
9> Knight ! { self(), move, { 2, 1 }, { 3, 3 }, white }.
{<0.84.0>,move,{2,1},{3,3},white}
10> flush().
Shell got {yes,knight,{2,1},{3,3}}
ok
11> Knight ! { self(), move, { 2, 1 }, { 3, 2 }, white }.
{<0.84.0>,move,{2,1},{3,2},white}
12> flush().
Shell got {no,knight,{2,1},{3,2}}
ok
13> Knight ! { self(), move, { 2, 1 }, { 3, 4 }, white }.
{<0.84.0>,move,{2,1},{3,4},white}
14> flush().
Shell got {no,knight,{2,1},{3,4}}
ok

Task 2: Traversals

As I indicated in the design notes above, this code should return a list of squares that the piece must cross so that some other process can look for conflicts.

This will significantly impact the way we define move_response/5 (to the point where it may have a different arity).

Let’s start by revisiting the move functions.

Move functions

At the moment, I have: knight, king, and pawn moves, and a distinct pawn capture function. Of those, only the 2-square initial pawn move would return a list of intermediate squares.

Nonetheless, all of them must be updated.

Currently, they return a single tuple, a location. Now they’re going to have to return location as a nested tuple, with the other element of the tuple the list of squares.

So, for example, the knightmove function today:

fun({ OldX, OldY }, { NewX, NewY }, _)
      when abs(NewY - OldY) =:= 2, abs(NewX - OldX) =:= 1 -> { NewX, NewY };
   ({ OldX, OldY }, { NewX, NewY }, _)
      when abs(NewY - OldY) =:= 1, abs(NewX - OldX) =:= 2 -> { NewX, NewY };
   (Loc, _, _) -> Loc end

Would become:

fun({ OldX, OldY }, { NewX, NewY }, _)
      when abs(NewY - OldY) =:= 2, abs(NewX - OldX) =:= 1 -> { { NewX, NewY }, [] };
   ({ OldX, OldY }, { NewX, NewY }, _)
      when abs(NewY - OldY) =:= 1, abs(NewX - OldX) =:= 2 -> { { NewX, NewY }, [] };
   (Loc, _, _) -> { Loc, [] } end

That means that move_response/5′s pattern matching changes. As of our changes in the last task, we throw the response from the move function between the Start and End tuples; let’s reorder that.

Now:

move_response(Pid, Piece, Start, Start, End)
move_response(Pid, Piece, Start, End, End)

Changed:

move_response(Pid, Piece, Start, End, { Start, Traverse })
move_response(Pid, Piece, Start, End, { End, Traverse })

Side note: I can’t tell you how much fun I’m having writing code with no if/else blocks. Spaghetti code, thy name is if!

Complete code for the new move_response/5:

move_response(Pid, Piece, Start, End, { Start, Traverse }) ->
    Pid ! { no, Piece, Start, End, Traverse };
move_response(Pid, Piece, Start, End, { End, Traverse }) ->
    Pid ! { yes, Piece, Start, End, Traverse }.

That wasn’t so bad.

Now we get to the ugly part: the new move functions. This is the code that was already tough to read, and now it’s all that much more difficult.

movefuns() ->
    [ 
      { pawnmove, fun({ X, OldY }, { X, NewY }, white) when NewY - OldY =:= 1 -> { { X, NewY }, [] };
                     ({ X, OldY }, { X, NewY }, black) when NewY - OldY =:= -1 -> { { X, NewY }, [] };
                     ({ X, 2 }, { X, 4 }, white) -> { { X, 4 }, [ { X, 3 } ] };
                     ({ X, 7 }, { X, 5 }, black) -> { { X, 5 }, [ { X, 6 } ] };
                     (Loc, _, _) -> { Loc, [] } end
      },

      { pawncap, fun({ OldX, OldY }, { NewX, NewY }, white)
                       when abs(NewX - OldX) =:= 1, NewY - OldY =:= 1 -> { { NewX, NewY }, [] };
                    ({ OldX, OldY }, { NewX, NewY }, black)
                       when abs(NewX - OldX) =:= 1, NewY - OldY =:= -1 -> { { NewX, NewY }, [] };
                    (Loc, _, _) -> { Loc, [] } end
      },

      { kingmove, fun({ OldX, OldY }, { NewX, NewY }, _)
                        when abs(NewY - OldY) < 2, abs(NewX - OldX) < 2 -> { { NewX, NewY }, [] };
                     (Loc, _, _) -> { Loc, [] } end
      },

      { knightmove, fun({ OldX, OldY }, { NewX, NewY }, _)
                          when abs(NewY - OldY) =:= 2, abs(NewX - OldX) =:= 1 -> { { NewX, NewY }, [] };
                       ({ OldX, OldY }, { NewX, NewY }, _)
                          when abs(NewY - OldY) =:= 1, abs(NewX - OldX) =:= 2 -> { { NewX, NewY }, [] };
                       (Loc, _, _) -> { Loc, [] } end
      }

    ].

And, once more into the breach:

4> [ Kn ] = [ X || {knightmove, X} <- piece:movefuns() ].
[#Fun<piece.3.48775173>]
5> Knight = spawn(piece, piece_loop, [ knight, Kn, Kn ]).
<0.132.0>
6> Knight ! { self(), move, { 2, 1 }, { 3, 4 }, white }.
{<0.122.0>,move,{2,1},{3,4},white}
7> flush().
Shell got {no,knight,{2,1},{3,4},[]}
ok
8> Knight ! { self(), move, { 2, 1 }, { 3, 3 }, white }.
{<0.122.0>,move,{2,1},{3,3},white}
9> flush().
Shell got {yes,knight,{2,1},{3,3},[]}
ok
10> [ Pm ] = [ X || {pawnmove, X} <- piece:movefuns() ].
[#Fun<piece.0.48775173>]
11> [ Pc ] = [ X || {pawncap, X} <- piece:movefuns() ].
[#Fun<piece.1.48775173>]
12> Pawn = spawn(piece, piece_loop, [ pawn, Pm, Pc ]).
<0.140.0>
13> Pawn ! { self(), move, { 2, 2 }, { 2, 4 }, white }.
{<0.122.0>,move,{2,2},{2,4},white}
14> flush().
Shell got {yes,pawn,{2,2},{2,4},[{2,3}]}
ok

I can’t put off diagonals much longer, and I should also look into unit tests. Tomorrow is another day.


  1. I wonder whether, at the end of this project, this process will no longer exist, in favor of raw access to the move/capture functions. Maybe we’re going the wrong direction.

  2. Note to self: we probably will store the Pawn PID 16 times: once in each square with a pawn in our board matrix.

  3. This code lends itself to unit tests, but I have no idea at the moment how to do that. More research.

erlang chessboard
Previous post
@drkrab on Erlang Of paradigm shifts and finer things.
Next post
Chessboard: Day 6 8th grade Algebra defeats me.