| Author |
Message |
Don Rogers (Patzer42)
| | Posted on Saturday, August 17, 2002 - 3:17 am: | |
I am a new Zillions programmer. I'm trying to code a chess variant where, after each move or capture, some pieces on the board (friendly as well as enemy) may become either temporarily immobilized, or re-mobilized. The rules for which pieces are mobile makes sense (at least to me), but they are complicated and recursive. One piece's being moved, captured or immobilized can have ripple effects on many other pieces (all except the Kings). This could happen potentially anywhere on the board. Immobilized pieces do not give check.
I have a bunch of questions. Some of them are probably easy; some hard, but here goes:
1. I think I need to do all of this recursive stuff in each of my move blocks. (I considered having a "neutral turn" between each White and Black move to do all the housekeeping, but that could lead to situations where a player illegally moves into check as a result of the neutral turn.) Am I right?
2. If so, then I think each move is going to have to be a complex, recursive "cascade". I could do this by changing piece-types (change-piece from Rook, say, to Immobilized-Rook, or vice versa), or by changing a piece-attribute flag. Is one method more sensible than the other? If I change piece-type, would the new Immobilized-Rook automatically inherit the attributes (I'm thinking about "never-been-moved?") of the old Rook? I would guess not, which makes me think it's probably more sensible to change an "immobilized?" piece-attribute flag.
3. I noticed how in the implementation of Ultima, there is a pseudo-attribute called "immobilized?" (this is really just a complicated Boolean expression). I'm sure my game's "immobilized?" condition is too complicated to set up as a Boolean like this.
Instead, what I think I need to do is to:
a) cycle through the whole board, immobilizing every non-King;
b) re-cycle through the whole board, mobilizing the pieces that are "defended?";
c) if any more pieces were mobilized in step b, then repeat step b as many times as necessary;
d) finally, do my "add" step.
But there is a problem: I don't want to really change these piece types or attributes, unless this is the move the player actually chooses. (I suspect this is why the Ultima programmers chose to use a logical pseudo-attribute.) How can I recursively change some pieces' "immobilized?" attributes (changing other pieces' "defended?" states), while making it clear that all this is the result of the player's potential move, which will not necessarily be chosen?
4. There must be a better way to cycle through every square on the board than what I am using now, which is brute force. For example:
(define immobilize-all
(if (not (empty? a1)) (immobilize-piece a1))
(if (not (empty? a2)) (immobilize-piece a2))
(if (not (empty? a3)) (immobilize-piece a3))
.
.
.
(if (not (empty? h7)) (immobilize-piece h7))
(if (not (empty? h8)) (immobilize-piece h8))
)
Is there a good example of a more elegant way to do this?
Thanks to anyone who can help with this. |
David J Bush (Twixter)
| | Posted on Saturday, August 17, 2002 - 8:22 am: | |
| 1. I think I need to do all of this recursive stuff in each of my move blocks.
| (I considered having a "neutral turn" between each White and Black move to do all
| the housekeeping, but that could lead to situations where a player illegally moves
| into check as a result of the neutral turn.) Am I right?
First of all, Zillions does not have recursive subroutines. It has macros, but they
cannot call themselves. So I'm not sure what you mean by "recursive."
Moves are defined in either move blocks or macros that are called by the move blocks,
as far as I know.
| 2. If so, then I think each move is going to have to be a complex, recursive
| "cascade". I could do this by changing piece-types (change-piece from Rook, say,
| to Immobilized-Rook, or vice versa), or by changing a piece-attribute flag. Is one
| method more sensible than the other? If I change piece-type, would the new
| Immobilized-Rook automatically inherit the attributes (I'm thinking about
| "never-been-moved?") of the old Rook? I would guess not, which makes me think it's
| probably more sensible to change an "immobilized?" piece-attribute flag.
Quoting from the language reference help:
Note that if a piece is changed during the game from one type of laser-firing piece
to another with change-type, the "lasers-charged?" attribute will retain its value.
If the new piece type has piece attributes that the old one didn't, or if they have
different default values, you may want to call set-attribute yourself to initialize
the values in the move changing the piece-type.
| 3. I noticed how in the implementation of Ultima, there is a pseudo-attribute called
| "immobilized?" (this is really just a complicated Boolean expression). I'm sure my
| game's "immobilized?" condition is too complicated to set up as a Boolean like this.
|
| Instead, what I think I need to do is to:
| a) cycle through the whole board, immobilizing every non-King;
| b) re-cycle through the whole board, mobilizing the pieces that are "defended?";
| c) if any more pieces were mobilized in step b, then repeat step b as many times as
| necessary;
| d) finally, do my "add" step.
|
| But there is a problem: I don't want to really change these piece types or attributes,
| unless this is the move the player actually chooses. (I suspect this is why the Ultima
| programmers chose to use a logical pseudo-attribute.) How can I recursively change some
| pieces' "immobilized?" attributes (changing other pieces' "defended?" states), while
| making it clear that all this is the result of the player's potential move, which will
| not necessarily be chosen?
No attribute is actually changed, no piece-type is changed, until and unless the
move that would generate those changes is actually played. This is an important
aspect of Zillions. For example, if a piece has an attribute "happy?" which is
false before a move is made, and the following code is encountered:
(set-attribute happy? true)
(if happy?
[code block A]
else
[code block B]
)
The code in block B will be executed, NOT A.
If you need to "remember" whether an attribute has been changed inside a move
block, use a flag or a position-flag.
It might help, if you explain in more detail what your intended ruleset is.
It sounds as though only the King is initially labeled as "defended" and any
mobile piece must be "connected" to the King by a "chain of defense" i.e.
piece A defends piece B defends piece C...
If so, I guess your algorithm description is the way to go. I can't think of
a better one, off hand.
| 4. There must be a better way to cycle through every square on the board than what I
| am using now, which is brute force.
Good God, yes. I assume you define a square grid of positions with a "grid" block.
I also assume you defined the direction e for East, which is (1 0). Now use a "links"
block to define e for the rightmost column of squares. For example:
(links e (h8 a7) (h7 a6) (h6 a5) ... )
like that. I believe that will work, as long as e is not defined as two different
things for any one position. Now you can scan all positions with ease.
David
twixt@cstone.net |
David J Bush (Twixter)
| | Posted on Saturday, August 17, 2002 - 9:20 am: | |
Okay, I thought of a possible improvement to your algorithm. Each piece has an attribute "leaf?" which is initially set to true. During your scan, if a piece X is protected by a piece Y, set the "leaf?" attribute of Y to false. This way, those mobile pieces which are "leaves" of the tree of protection, i.e. they do not themselves protect any other piece, are labeled as leaves. On another move, if you move a piece which is a leaf, and it moves to a position which is not protected by a mobile piece, you can label it as immobile without having to scan the board. If it moves to a position which IS protected by a mobile long-range piece such as a bishop or rook, you might have just blocked the protection of another piece on the same line, so i suppose you would have to scan the board in that case. But if the mobile leaf moves to a square protected only by short-range mobile pieces such knights or pawns, then if the leaf piece is still a leaf, if it still does not protect any otherwise immobile piece, no scan should be necessary. If a mobile non-leaf moves, you would again probably have to scan the board. Hope this helps...
David |
Don Rogers (Patzer42)
| | Posted on Sunday, August 18, 2002 - 5:44 am: | |
Thanks, David, for your very timely suggestions.
Yes, you pretty much inferred the idea of the game, which I am tentatively calling "Chain of Command Chess".
Object: Checkmate the opponent's King by attacking it so it cannot escape. Pieces move exactly as in regular chess; the only difference is that no piece can move unless it is in communication, directly or indirectly, with orders coming from the King.
In this game the King gives all the orders, and so the King can move at any time (within the normal rules of chess). Any piece directly adjacent to the friendly King can move, too, since it can "receive orders" from the King. In addition, a piece can move if it is within an indirect chain-of-command with its King. For example, if the Queen is adjacent to the King then she can move, AND so can any pieces that are guarded by the Queen, AND any pieces guarded by those pieces, and so on.
Note: For purposes of the chain of command, each Pawn can communicate not only with pieces it guards, but also with any friendly piece that stands on a square to which the Pawn could otherwise move.
Any pieces that are not in communication with their King are immobilized (and so cannot give check) until a communication link to the King is re-established. Castling is considered a King move, so the rules regarding it are unchanged (a King can castle with an immobilized Rook).
--------------
Your "leaf?" idea is clever, but there are many ways that even a leaf's move can alter either or both sides' chain of command structure: by capturing, by opening (or interfering with) lines of communication (friendly and/or hostile), and by promotion. For the time being at least, I think it will be simpler to do a full board scan each time through.
For now the plan is, before each move "add":
a) loop through all the squares on the board, immobilizing all of the pieces except the Kings;
b) loop through all the squares on the board, mobilize the pieces that are "defended?" (by the King, initially), or via communication through a regular Pawn move;
c) repeat step b) as many times as necessary, until no further pieces are remobilized. [It's this "repeat procedure as necessary" feature that I was calling "recursive", but you're right -- that's not the right word.]
It might well be more efficient to proceed by:
a) immobilizing all of the pieces except the Kings;
b) mobilizing the pieces defended by the King, keeping track of which ones are "branches" (as opposed to leaves)
c) mobilizing the pieces that are defended by those branches, and so on.
That at least could be done in just one or two passes through the board.
-----------------
Your "links" idea is interesting. But wouldn't it make possible illegal rook, king and queen moves (from h8 to a7, say)? It seems like you would end up with a strange barber-pole shape board. Or would it not affect the pieces' movements?
------------------
You say, "No attribute is actually changed, no piece-type is changed, until and unless the move that would generate those changes is actually played."
Does this mean that I can only use "defended?" to see whether a piece is defended now -- not to see whether it would be defended at every new potential position? Probably so, but unfortunate for me. As you said, "If you need to 'remember' whether an attribute has been changed inside a move block, use a flag or a position-flag." I don't doubt you, it's just that re-inventing the "defended?" logic in my code will be tedious.
---------------
What does Zillions understand as the cue that "that's the whole move"? In my case, is it always "add"? And all of the "change-type" commands are not actually invoked until the final "add"?
Is it right that I do not need to use "cascade", even if I am doing a bunch of "change-type" commands, as long as there is only one piece that actually moves?
-------------------
Thanks again for your interest, time, and patience with a newbie. |
David J Bush (Twixter)
| | Posted on Sunday, August 18, 2002 - 6:41 am: | |
| Your "leaf?" idea is clever, but there are many ways that even a leaf's move can alter either
| or both sides' chain of command structure: by capturing, by opening (or interfering with) lines
| of communication (friendly and/or hostile), and by promotion. For the time being at least,
| I think it will be simpler to do a full board scan each time through.
Yes, there are plenty of exceptions I did not mention, but they can all be dealt with. I guess
it comes down to execution time versus programmer's time.
-----------------
| For now the plan is, before each move "add":
|
| a) loop through all the squares on the board, immobilizing all of the pieces except the Kings;
| b) loop through all the squares on the board, mobilize the pieces that are "defended?"
| (by the King, initially), or via communication through a regular Pawn move;
| c) repeat step b) as many times as necessary, until no further pieces are remobilized.
| [It's this "repeat procedure as necessary" feature that I was calling "recursive", but you're
| right -- that's not the right word.]
|
| It might well be more efficient to proceed by:
|
| a) immobilizing all of the pieces except the Kings;
| b) mobilizing the pieces defended by the King, keeping track of which ones are "branches"
| (as opposed to leaves)
| c) mobilizing the pieces that are defended by those branches, and so on.
|
| That at least could be done in just one or two passes through the board.
I don't understand the difference between these two approaches, other than distinguishing the
branches from the leaves. Would you not still have to scan the board to find all the pieces
defended by the branches? Why would this take fewer passes through the board?
It sounds like you might be trying to run a recursive routine here. Not easy to do in Zillions.
-----------------
| Your "links" idea is interesting. But wouldn't it make possible illegal rook, king and queen
| moves (from h8 to a7, say)? It seems like you would end up with a strange barber-pole shape
| board. Or would it not affect the pieces' movements?
Then define another direction, call it "nextsq" which is not used to define piece movements.
Define it in the grid block the same as e (1 0). Then define it in a links statement as
(h8 a7) (h7 a6) etc.
------------------
| You say, "No attribute is actually changed, no piece-type is changed, until and unless the move
| that would generate those changes is actually played."
|
| Does this mean that I can only use "defended?" to see whether a piece is defended now -- not to
| see whether it would be defended at every new potential position?
That is correct. The same is true for "attacked?" So if you want to update the "mobile?" attribute
at the end of each move, you could scan locally around the piece you moved, looking for friendly
mobile knights which are a knight's move away, etc. You also would have to consider lines of
protection, for both you and your opponent, which you block or unblock with your move. En passant
could present some problems in that regard as well.
Alternatively, you could update the mobile? attribute at the beginning of each move, in which case
the attacked? and defended? booleans will work, except for the pawn situation you describe.
---------------
| What does Zillions understand as the cue that "that's the whole move"? In my case, is it always
| "add"? And all of the "change-type" commands are not actually invoked until the final "add"?
I believe that is correct.
| Is it right that I do not need to use "cascade", even if I am doing a bunch of "change-type"
| commands, as long as there is only one piece that actually moves?
I think so. |
|