Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Representing Complex but Static Data in Perl

by cyocum (Curate)
on Apr 07, 2005 at 09:46 UTC ( [id://445588]=perlquestion: print w/replies, xml ) Need Help??

cyocum has asked for the wisdom of the Perl Monks concerning the following question:

Fellow monks, this weeks feels like cyocum stupid question week but I cannot think of a more elegant way of doing this so I am asking your advice.

I am writing a chess program as some of you may remember (the code in there right now is very sub-optimal and I am thinking about trashing it and starting over so beware if you check out the code). One of the big probelms that is slowing it down is move generation so I determined to preprocess all valid moves for all peices and store them so that the piece objects can share the data. The preprocessing is now finished and I have moved on to the next step, which is representing this the best way in Perl code.

I figure that a hash of hashes with the value being an anonymous array of arrays with all the valid moves contained in them. Now, my problem is how to best represent this.

if I do this:

use strict; use warnings; #row #col #list of list of valid moves our %hash = (0 => 0 => [[[1, 0],[2, 0],[3, 0],[4, 0],[5, 0],[6, 0],[7, + 0]], [[0, 1],[0, 2],[0, 3],[0, 4],[0, 5],[0, 6],[0, 7]]]);

I get this:

Odd number of elements in hash assignment

This forces me to do this:

use strict; use warnings; our %hash; $hash{0}->{0} = [[[1, 0],[2, 0],[3, 0],[4, 0],[5, 0],[6, 0],[7, 0]], [[0, 1],[0, 2],[0, 3],[0, 4],[0, 5],[0, 6],[0, 7]]];

This works but is ugly and does not really give the reader an indication that this is a shared piece of data that never changes. If I were doing this in C/C++, I would make it all const.

Any ideas or examples of how to make this look better would be highly appreciated. As always, thank you all for your time and effort.

Replies are listed 'Best First'.
Re: Representing Complex but Static Data in Perl
by Jaap (Curate) on Apr 07, 2005 at 09:52 UTC
    Place some {} around the last key/value:
    our %hash = (0 => { 0 => [[[1, 0],[2, 0],[3, 0],[4, 0],[5, 0],[6, 0],[ +7, 0]], [[0, 1],[0, 2],[0, 3],[0, 4],[0, 5],[0, 6],[0, 7]]]});
    You need to let the first hashvalue be a scalar, in this case an anonymous hash ref.
      And maybe let Perl do the counting:
      our %hash = (0 => { 0 => [[map [$_, 0], 1..7], [map [0, $_], 1..7]]});

      Caution: Contents may have been coded under pressure.
Re: Representing Complex but Static Data in Perl
by jhourcle (Prior) on Apr 07, 2005 at 11:31 UTC

    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.

      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!

        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).

Re: Representing Complex but Static Data in Perl
by Roy Johnson (Monsignor) on Apr 07, 2005 at 11:55 UTC
    One way to give the reader the idea that it is shared data that never changes is to put a comment in that says:
    # This is shared data! Do not change it!
    Perl's contracts are usually maintained by agreement rather than by enforcement. Of course, you could encapsulate it (as another poster has suggested).

    Caution: Contents may have been coded under pressure.
Re: Representing Complex but Static Data in Perl
by gam3 (Curate) on Apr 07, 2005 at 12:51 UTC
    There is a Readonly module. This is not the same const, as a Readonly::Hash is slower than a normal Hash.

    You might consider making your data an object. Then it's use will be clearer, and you can control access if you need to.

    package ChessMoves; sub new { my $class = shift; return bless {0 => { 0 => [ [[1, 0],[2, 0],[3, 0],[4, 0],[5, 0],[6, 0], [7, 0]], [[0, 1],[0, 2],[0, 3],[0, 4],[0, 5],[0, 6],[0, 7]], ] }} $class; } sub get_moves { my $self = shift; my ($row, $col) = @_; return $self->{$row}{$col}; }
    -- gam3
    A picture is worth a thousand words, but takes 200K.
Re: Representing Complex but Static Data in Perl
by dragonchild (Archbishop) on Apr 07, 2005 at 13:33 UTC
    A lot depends on how you intend on using this datastructure. One way is "Hey, mister! Give me all the valid moves for this piece at this location." Another way is "Hey, mister! Is this move legal for this piece at this location?"

    Now, with hashes, you can do both. Build it with $isLegal{ $Piece }{ $Start }{ $End } = !!1;. Now, you can either query it with exists $isLegal{ $Piece }{ $Start }{ $End } to determine if $Start->$End is legal for $Piece or you can do a keys %{ $isLegal{ $Piece }{ $Start } }; to get a list of the legal moves for $Piece at $Start.

    It would be best to encapsulate this data structure in an object so that you can simply do things like:

    foreach my $move ( $LegalMoves->get_legal_moves( $Piece, $Start ) ) { # Do stuff here }

    Now, the generation part. This is very simple, assuming you have an algorithm that will determine if a given move is legal for a given piece. This is going to require computation, but you're only doing this once. You could even do this offline and store it with DBM::Deep. I strongly recommend doing this.

    foreach my $Piece (@list_of_pieces) { foreach my $Start (@list_of_squares) { foreach my $End (@list_of_squares) { # You supply the is_legal_move() function!! next unless is_legal_move( $Piece, $Start, $End ); $isLegal{ $Piece }{ $Start }{ $End } = !!1; } } }

      Very Cool. This is an interesting idea. Thanks for the reference to DMB::Deep. I may put the opening move database in there since I will only use it for a little while then once it is exhausted, I would move to the search function. I want to keep the valid move table in memory since I will use it over and over again rather than pulling from a file (although, at this beginning stage, it is probably not a huge increase in speed).

      My plan was to encapulate the hash inside the piece object and then ask the piece object to give me all the valid moves from where it is (the piece object holds it's own position). That way I can control various special moves like en passant and castling in their respective objects.

        That's a lot of memory ... oh - you're also going to have to work out things like blocking pieces (for non-knights) and the like. To tell you the truth, I'm not seeing a huge gain here. Pawns have to have the state of the board to determine ep. Granted, you have a set of optimizers to make the ep check pretty cheap, but it's still there.

        Frankly, I would drop into XS and write the move generation code there. That is, of course, if the speed is that poor.

        Also, a question no-one (including me) has approached is whether or not your original algorithm was good or not. 90% of all speedups happen in better algorithm choice.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://445588]
Approved by jbrugger
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2024-03-28 16:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found