Re: Representing Complex but Static Data in Perl

[dragonchild]

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;
        }
    }
}

[cyocum]

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.

[dragonchild]

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.

[cyocum]

My algorithem choice was alphabeta and it is pretty slow probably due to the fact that I am still learning all the ins and outs of this kind of programming. Once I learn about how to write a good alphabeta, I will then move to something more interesting like MTD(f).

To work out the blocking pieces, you just run along the list of moves and check the square represented against the board, which can be passed to the function as a reference. Since the board is stored internally as a 8x8 multi-dim array, it is pretty easy to see if there is something there and of what color. I have a function called isOccupied to check and isColor to tell me the color.

Of course, this could all be negated by using bitboards but I am not comfortable enough with the idea yet to try it.