Re: Representing Complex but Static Data in Perl

[jhourcle]

Two comments --

From the looks of things, you're storing the varient of all of the possible moves of each piece, based on the starting position. You can probably store much less initial seed data by telling each piece how it's allowed to move (relative to the current space), and then, either computing each of the valid moves for each space, or just verifying them on a per-move basis.

For instance, similar to what you had (which were the valid moves of a rook from position 0,0.

my %moves;
$moves{'rook'} = [ [-7,0], [-6,0], [-5,0], [-4,0], [-3,0], [-2,0], [-1
+,0], [1,0], [2,0], [3,0], [4,0], [5,0], [6,0], [7,0], [0,-7], [0,-6],
+ [0,-5], [0,-4], [0,-3], [0,-2], [0,-1], [0,1], [0,2], [0,3], [0,4], 
+[0,5], [0,6], [0,7] ];

Of course, I don't like typing that much:

foreach my $i ( -7..-1, 1..7 ) { push @{$moves{'rook'}}, [$i,0], [0,$i]; }

But that doesn't answer your initial question -- how do you keep people from changing things? There's 'use constant', but that doesn't quite work for hashes, arrays, or in this case, hashes of hashes of arrays. I'd recommend encapsulating the values, so the general user never interacts with them. Perhaps giving them one (or both) of the following interfaces:

my @valid_moves = valid_moves( $type, $position );
is_valid_move( $type, $starting_position, $end_position );

Update: You could also use tied hashes and arrays, to control updates.

[cyocum]

If I read you correctly and I could be misunderstanding you, you are saying that I should compute rather than store the valid moves. Unfortunetly, you end up spending much more time computing the valid move list for each position than doing a look up then searching down the lists for an invalid move or capture. Since it is almost a linear search, it is much faster. On this topic, I recommend reading this article on chess programming over at Gamedev. According to him, sophisticated chess programs generate a few moves at a time then search those (usually trying captures first). I would rather pre-process then do code to add the special cases.

About access control, I was thinking that after I was done filtering the moves so I only had the valid moves and captures, I would just use a copy of the list rather than giving out the referenced array. It does not matter so much in any case since I am the only coder and if anyone else wants to help, I would be able to trust them in the first place. Access control is really all about trust in the end.

Thanks for the thoughts!

[jhourcle]

Well, yes and no. I said

and then, either computing each of the valid moves for each space, or just verifying them on a per-move basis.

If all you're doing is having a chess game between two human players, it may be enough to validate each move on a per-move basis. If you're trying to create an AI, then I'd have some initialization function that runs at startup to build the complex per-space tables based on the simple formulas.

So, for instance, in your case, as you're using an AI, you could compute all of the valid rook moves with:

my %moves;
foreach my $i ( -7..-1, 1..7 ) {
  push @{$moves{'rook'}}, [$i,0], [0,$i];
}

my %valid_moves;
$valid_moves{'rook'} = [];
foreach my $i ( 0 .. 7 ) {
  $valid_moves{'rook'}->[$i] = [];
  foreach my $j ( 0 .. 7 ) {
    $valid_moves{'rook'}->[$i]->[$j] = [];
    foreach my $move ( @{$moves{'rook'}} ) {
      my $x = $i - ($move->[0]);
      next if ( $x < 0 or $x > 7 );
      my $y = $j - ($move->[1]);
      next if ( $y < 0 or $y > 7 );
      push @{$valid_moves{'rook'}->[$i]->[$j]}, [$x,$y];
    }
  }
}

You can shorten it, of course (rely on autovivication, etc ...) I just did that for the sake of what I find to be easy to come back to at some future point. And to save some time, a queen's valid moves are the union of a bishop and a rook's valid moves.

Oh -- and I have no idea how you'd handle castling after building this table (whereas, by validating each move individually, it's an easy case to test for).

[dragonchild]

en-passant is also problematic with this scheme ...