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] ];
[download]

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

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 );
[download]

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