Ultima

[hgm]

BTW I'm afraid I'm afraid I won't manage to get Oberon working on big boards in time for Grand Chess, especially after I started using it as a tool for... learning object oriented programming. Nice for catching bugs, but not for coding fast, especially with little time in my hands.

Don't worry, I was not really planning to hold the Grand Chess tourney anytime soon. And certainly not the 10x8 Championship; I was more thining Oct/Nov for that.

[Daniel Shawul]

I have come to the conclusion that it is virtually _impossible_ to solve it when there are long leapers. It is like a recursive qsearch which can blow up easily. If you look at the position that I have provided, there is only one capture but you can start from any of the opponent tests. And then there is the issue of merging 'different looking moves into one'. Btw it can also start making regular jump captures, and then starts leaping when it encounters longleapers... It is one big mess I tell you.
I am so frustrated I offer money for whoever comes up with a pseudo-code to handle all the smallest details. I am serious but not about the money

[Daniel Shawul]

I didn't see your post before replying to Evert's post.

The most nasty are the Pincer and Coordinator-style captures. Those would indeed have to be tested for on every to-square. An alternative here might be 'retrograde' capture generation, starting from the victim. E.g. in the initial position of Ultima you have 8 Pincer Pawns, that each have 4 moves. That is already 32 Pincer moves, and the number rises when you break the closed rank of them, due to sideway moves. (Move 1 forward, and you get 9 extra...) It would be kind of expensive to test for all of these 32+ moves in 3 directions if something gets sandwiched. It could be cheaper to run through the opponent piece list (16 pieces), and check every piece for an opponent neighbor that could act as 'backer' for the sandwich (in 4 directions). Because usually there will be none, and that immediately rules out the piece can be captured this way. If there is a backer, and an empty square on the other side, you could try to generate all Picer moves to that empty square, from piece list Pincer section, 0x88 alignment test and ray scan. you could mark all squares where a Pincer would capture something (e.g. with a bit mask to indicate what it captures), and do normal generation of Pincer moves, testing the masks on the to-squares.

Yes I did the chameleon captures as you described in a straight forward manner for all the ultima pieces. The problem is when adding additional pieces. Lets say we add a knight to the ultima game, then I can simply add a knight's capture test to see if it is possible to capture a knight from the current destination square of the chameleon. But this forward method has additional cost because I have code which is always tested even if that piece didn't exist. For example in Ultima there is no knight but that code will definately be done slowing down the game unnecessarily. Or even when that piece is captured in the same game.. More jumpers more slow down so this forward method will be too slow after some time...

About retrograde generator, I have come to the conclusion that it is very very difficult to do bar simplistic situations as in capablanca style chameleon chess. But the general chameleon piece is really difficult. I will look to your suggestions more carefully now.

[Evert]

I have come to the conclusion that it is virtually _impossible_ to solve it when there are long leapers. It is like a recursive qsearch which can blow up easily. If you look at the position that I have provided, there is only one capture but you can start from any of the opponent tests. And then there is the issue of merging 'different looking moves into one'. Btw it can also start making regular jump captures, and then starts leaping when it encounters longleapers... It is one big mess I tell you.
I am so frustrated I offer money for whoever comes up with a pseudo-code to handle all the smallest details. I am serious but not about the money

I would treat a long-leaper (or a chamaeleon for this purpose) in the same way as I would a capture in draughts (or a multi-move in general): make the move, but not flip the side to move.
When a new move is made, test whether the side-to-move has changed since the last move. If not, do some special/restricted move generator, for instance only captures with the piece that made the last move. If there are no legal moves generated in this way (no further captures possible), flip the side to move.
Those extra moves should probably all be extended so they don't count against the search depth, and they should probably be discarded for the purpose of checking killer moves as well. Might still want to store that position in the transposition table.

There are subtleties there that I'm sure I've missed because I haven't actually tried this (yet - but I've been thinking about it and keeping notes) but it seems to me to at least have the advantage of splitting up the problem in smaller, more manageable sub-problems.

[Daniel Shawul]

Ok let me define the problem as clearly as possible to avoid confusion.

A chameleon attacks a piece the way the piece attacks it. Hence, a chameleon captures a piece the way it captures it. A piece in my case is defined as a list of directions along with flags indicating the way the piece is going to act in that directon. Similar to fairy maxes. You can not talk about a piece as a whole without breaking it down to directions and its flags indicating if it can capture, slide, ride, hope , pinch_capture, coordinate_capture etc...
For example WinChloe has 1100 fairy pieces... http://winchloe.free.fr/wc.html

Now my wish is to have a chameleon piece that works in a way I described in the bold faced text, for any kind of piece that the user might create from alien.ini by combining directions and flags. Is that possible ? It should be possible but I don't know how.

The problem may not be simplified.
Thank you
Daniel

[Evert]

Ok let me define the problem as clearly as possible to avoid confusion.

A chameleon attacks a piece the way the piece attacks it. Hence, a chameleon captures a piece the way it captures it. A piece in my case is defined as a list of directions along with flags indicating the way the piece is going to act in that directon. Similar to fairy maxes. You can not talk about a piece as a whole without breaking it down to directions and its flags indicating if it can capture, slide, ride, hope , pinch_capture, coordinate_capture etc...
For example WinChloe has 1100 fairy pieces... http://winchloe.free.fr/wc.html

Now my wish is to have a chameleon piece that works in a way I described in the bold faced text, for any kind of piece that the user might create from alien.ini by combining directions and flags. Is that possible ? It should be possible but I don't know how.

The problem may not be simplified.

I'm not sure I see the problem, but that could be because I've only thought about it and not tried to actually do it.
Why would going through a list of piece types that the opponent has on the board and testing whether a piece of that type on the location of the Chamaeleon not work? Some parts of it could probably be pre-calculated.
I haven't really tried to understand how Fairy-Max works, so maybe this is a lot more complicated than I think it is but I don't really see why.
Unless you're worried that this approach is too slow, which I can see it might be. I don't really think that can be avoided in this case though. Maybe clever use of C++ templates buys you something?

Sjaak stores "movement type" in a bitfield for each piece (with separate bitfields for normal moves and captures). When it does move generation, it tests these bitfields for each piece as it builds up the list (more efficient would be to do it once per type, but without using templates the code becomes hideous for that). The Chamaeleon would need another loop inside that one.

Hmm... that probably doesn't help much, does it?

[Daniel Shawul]

I think for Ultima it was easy for the following reasons
- you know all pieces from the start
- Testing along the 8 queen directions from the start square is enough
- non-recursive

For general games, we have

Option 1 - forward
- It is recursive. After the chameleon makes it first capture it can go
on making other captures. Also you can have jumpers,hopers etc attacking you
from different directions. For example the knight adds 8 more directions besides
the 8 queen directions. The nightrider, camel, zebra etc add even more. The user
can generate many types of jumpers from the ini.

You can not have code based on piece type as that is not defined, only directions of jump.

Code: Select all

      if we have knight
          test 8 directions of knight
      else we have night rider
          even more jumps along those 8 knight lines
      else if we have zebra
          test 8 directions of zebra
   

We can collect all the possible moves of the opponent pieces into a list at the start of move generation
and search along those lines for opponent pieces, at each and every intermediate square. If one of them results in a capture
we recurse... I can imagine there could be some merging & comparing of captured pieces. All in all I wouldn't be
surprized if this method becomes 20x more expensive. The chameleon is not really a single piece in this regard.
BTW if there were only jumpers and sliders its move generation is very simple, as that boils down
to a one step test to see if opponent pieces attack a chameleon (hence a chameleon can capture them). The long-leapers and other
'locust' pieces are what complicate the issue.

Option 2 - retrograde
- For the retrograde generator, we are starting from the tips, destination square (terminal or could also be part
of continuation capture ). Now we are back propagating from tips towards the root which is even
more difficult. We also have to compare different moves to see if they are part of the same move.
Take for example the position that I posted
[d]

Can you describe a way to generate it retrograde ? There is one long white capture g6-c6 which captures all the black
pieces and give a check. You can start testing for this capture from any of the captured (black) pieces.
Note that the other two captures g6-c2 and c4-c6 are easy.

[Evert]

Option 1 - forward
- It is recursive. After the chameleon makes it first capture it can go
on making other captures.

Same as for a long leaper: I would not end the turn after the first capture, only once there are no more continuations after the first. This will slow things down, but the branching factor should be low during the continuation sequence. Just hoe expensive this is depends on how frequently this sort of thing happens, but I'd try to make it work first and then try to optimise some common cases. For instance, do multiple leaps in one go, although if multiple captures are optional (they are for the long Leaper, they would not be in draughts) you need to generate the different partial sequences anyway and it's not clear that it would matter how you did this.

Also you can have jumpers,hopers etc attacking you
from different directions. For example the knight adds 8 more directions besides
the 8 queen directions. The nightrider, camel, zebra etc add even more. The user
can generate many types of jumpers from the ini.

You can not have code based on piece type as that is not defined, only directions of jump.

Right. So the way Sjaak does it is this: in its board representation, it stores the type of piece that is on a square. This is completely user defined: the way it's set up currently the King is the fifth piece type, but I could move its definition up and make it the first instead. Doesn't matter, its piece-type is an index into an array of structures that define its properties and the order they're in is arbitrary. One of the properties is a description of how it moves.
So by looping over all piece types that the opponent actually has, I'm implicitly looping over all movement types. This is just a matter of bookkeeping. Effectively, this just does what HGM suggested: try to capture pieces of a particular type.
A concept I find useful for this sort of consideration (I don't think it works for Ultima-style pieces though) is that of the "super piece", which moves as any other piece in the game (for unequal armies should maybe define two distinct types of superpiece, for black and for white). Only pieces on a square that could be reached by a super piece can possibly be captured (or, indeed, give check), so it's a waste of time to even look at other squares. Again, this can be pre-calculated. There may be a clever way to use this concept also for Ultima-style pieces, I haven't really thought about it very much.
It may also be that bitboards make some of this easier.

We can collect all the possible moves of the opponent pieces into a list at the start of move generation
and search along those lines for opponent pieces, at each and every intermediate square.

You only need attacks to the square that contains the Chamaeleon, which should make things a bit better.

BTW if there were only jumpers and sliders its move generation is very simple, as that boils down
to a one step test to see if opponent pieces attack a chameleon (hence a chameleon can capture them). The long-leapers and other
'locust' pieces are what complicate the issue.

Yes.
There is a somewhat similar asymmetry in Xiangqi when you ask whether a particular square is attacked by a Horse: just because a Horse on that square attacks an enemy Horse doesn't mean that the enemy Horse attacks you (it could be blocked). The trick there is to not test with a Horse (ma) but with something that does the two parts of the Horse move in reverse order (a "moa" I think is what it's called). I don't see how to do a similar trick here though (well, ok, I do for locusts that move along rays if I can use bitboards, but then I can just ask for captures by a locust on this location anyway).

Option 2 - retrograde
- For the retrograde generator, we are starting from the tips, destination square (terminal or could also be part
of continuation capture ). Now we are back propagating from tips towards the root which is even
more difficult. We also have to compare different moves to see if they are part of the same move.
Take for example the position that I posted
[d]

Can you describe a way to generate it retrograde ? There is one long white capture g6-c6 which captures all the black
pieces and give a check. You can start testing for this capture from any of the captured (black) pieces.
Note that the other two captures g6-c2 and c4-c6 are easy.

I don't see how to do it with retrograde analysis, but this is how I think my algorithm would go.
To generate captures for the Chamaeleon, I start a loop over enemy piece types.
I find the Withdrawer first, but I can't Xf6 since there's a piece there and I can't play Xe6 because the Withdrawer can't jump.
Next I find the Long Leaper, and I see that I can do Xg6xe6. I store the move, with a flag to indicate that the turn has not ended (and I need to check for side-effects).
I generate the rest of the moves.

I search the position and I try Xf6xe6. When I enter the move generator, I test the last move and notice that the side to move wasn't changed. I am therefore continuing on from the previous move.
Ok, this is annoying: I just realised I need to check side-effects of the previous move. In this case I captured the Withdrawer by moving away from it (albeit with a move that the Withdrawer can't make - wait, is that right?). This is rather annoying. It means I get to do the same loop again. I'd missed that and I'll need to think about a better way to do this.
Anyway, I know the previous move captured a Leaper. Therefore, during this stage, the Chamaeleon should move as a Leaper, and it should stay on the ray it moved in. I generate captures for a Leaper on e6, and find Le6xc6.
I store the move (with the capture of the Withdrawer), with a flag to say the turn has not ended.

I search the only move and play Le6xc6 in the search. I enter the move generator and see that the turn has not ended.
I resolve side-effects from the last move: the Pinchers and the Coordinator are captured. I know the previous move captured a Leaper. Therefore, during this stage, the Chamaeleon should move as a Leaper, and it should stay on the ray it moved in. I generate captures for a Leaper on c6 and find none.
I flip the side to move.

Some details here are a bit cumbersome, and it might be better to resolve side-effects in a separate step. Having to do that is annoying though, and I'll try to think of a better way to do it.

Again, not sure whether that helped or not...

[hgm]

I have come to the conclusion that it is virtually _impossible_ to solve it when there are long leapers.

I am not sure I fathom what exactly is the problem with the Long Leapers. I must admit that there is a certain inconsistency in the way the Chameleon is defined in Ultima, though, which makes it unclear how to generalize it. On the one hand you don't allow captures where the Chameleon reveals it is not what the victim holds it for through its move step: You cannot pince a Pincer through a diagonal move, and you cannot check a King from a distance. On the other hand, when the Chameleon reveals it is not a Pincer by jumping over one or two Long Leapers, it can pince a Pincer or coordinate a Coordinator. Apparently jumping over something is not considered revealing that you are not a Pincer or Coordinator.

So the rule seems to be that if the Chameleon can get to a target square either with one of its non-capture moves or jumping over a number of Long Leapers, it should perform all side-effect captures of pieces of family X when its move step was valid for the prospective victim, and the latter is on a square that would be captured for that capture style.

I guess the retrograde way of generating captures is not very attractive, because:
1) a capture can have multple victims, so you would find the same move multiple times. (Although in principle hash hits prevent they would really be searched multiple times.)
2) You would not automatically get the captures in the order you want to search them by starting at the MVV, because a multiple capture of lesser vctims might be worth more.

So assuming you do normal 'forward' move generation, you would loop over all the pieces in your own piece list, and then do something that depends on the capture style of the piece. This is necessary overhead, and the price you pay for making a general move generator. It can be ameliorated a bit by grooping different priece styles all in separate piece lists, so that you don't need to test the capture style in the loops, but can have separate loops that each can assume the style.

'Chameleon' would be a separate piece style, and when you loop over your Chameleons, for each of them you would basically have to do everything that is done in all of the other loops, but then test if the victims this produces match the style. That is cumbersome, but I don't see why it would not be straightforward. Just loop over all moves of the Chameleon, through the usual ray scans. When you encounter an enemy leap-capturer that can capture in the direction you are scanning, you skip it (but continue the ray scan). When you encounter an enemy replacement-capturer that could make the (reverse) step you are making, you can capture it, and the ray scan ends. That produces all potential capture moves, and you would have to check for other side effects (Withdrawer, Coordinatot or Pincer-style captures) based on the (from,to) pair.

If you are just interested in captures of one specific victim (e.g. the King, for the in-check test), you would have to loop over capture styles, and perform a separate test for each style. The only special thing about a Chameleon-style attacker would be that it can jump a few leap-capturers on the way to its destination. So assuming you have a replacement-capturer victim, the pieces in the enemy's Chameleon list would be checked for alignment in the usual 0x88 way, based on the allowed capture steps of the victim. But the ray scan needed if the victim is a slider would be special in the sense that is can skip over enemy leap-capturers that capture along the ray.

Simlarly for victimes with another capture style. Most capture styles have in common that you have to go to or come from a quite limited set of squares to exercise them. Sandwiching can happen on nearby squares if there is an enemy diametrically opposed (which you would test first, as it is usually not the case), coordinating is possible if you are aligned with enemy King, on two squares, withdrawal-capture is possible if a withdrawer stands next to you and has a move in the opposite drection. Again, for Chameleon would-be capturers the avalability of a move to the required to-square or away from the from-square in the required direction would need a leaping ray scan in stead of a norm alone. For a leap-capturer victim you would test for alignment, and then do a leaping ray scan to see if the would-be capturer can get there. The leaping ray scans would be subtly different for a leap-capturerer than for a Chameleon: the latter could only skip certain victims, namely those that match the direction (and it must match the direction of the ultimate victim based on the allowed capture directions of that victim to start with). The former can jump anything when it matches the direction to the ultimate victim from its own capture directions.

If you are not just interested in the existence of a capture move to a given square, (for the chec test), but want to generate all capture moves to the square, leaper captures should be extended beyond the 'ultimate victim', through the same ind of ray scan as was leading from attacker to victim (and as you would use in forward move generation).

[Daniel Shawul]

Thanks Evert and HG.
I think we can agree that the retrograde way is very cumbersome and it is not
so clear how to do it. If you start from the tip or intermediate square,
and jump in the piece's own style, you won't find the chameleon there as it may
be part of a long-jump. Also you you have to merge and sort (Or not, as HG pointed out, if you depend on
hash moves to reduce the burdern)

The forward way is easier but becomes complicated with locus pieces. BTW the long-leaper
is the easiest as it doesn't change directions. I don't even store the captured pieces
in the move definition since the path is one and clear. The make move will identify any 'side effect' captures.
Maybe I should identify and store them during move generation for MVV/LVA move sorting but it could result in
heavy data structure for the move. Or just the total sum of captured values could suffice. Anyway If it was checkers like piece which
changes directions when it captures, it would be more complex and definately recursive. The checkers capture move generation
is commonly done this way:

Code: Select all

        - recursive
        - many paths capturing the same set of pieces may result when the capture lenght >= 4
          Some captures can loop back on to itself.
        - some checkers rules specify more conditons on the lenght of jumps, total value of pieces
          captured. So you would have to do necessary post-processing

So I can follow this procedure for chameleon too

Code: Select all

        - At every destination square we have to test for 'terminative' types of captures. pinching caps,
          coordinate caps fall under that group. We generate a move when that happens, and keep on hopping.
        - In the previous case it was only 4 directions that was tested, but in this case we have to test
          in a list of directions that we computed at the beginning of move generation. We agree it is cumbersome
          but doable. I am not so sure about the rules, but if we can jump capture and findd a locust piece
          we have to continue that line too.. So the branching factor could become very big.
        - It seems we have to keep record of captured pieces to compare,sort and do other post processing.
         

I guess that is it. It is cumbersome but doable.
Thanks again.