Comments/Ratings for a Single Item

I was just reviewing the rules to make sure that my Game Courier preset covered everything, and I noticed this:

Each chief may activate 1 piece per turn. It may activate itself or another chief.

This makes things much more complicated than I first imagined. I was working with the assumption that any piece close enough to one of its Chieftains could move, and moves were limited by the number of Chieftains. But if I read this correctly, the preset would have to keep track not only of which pieces have moved but which Chieftains activated their movement. This will make the notation more complex. Alternately, it will make it much more complicated to calculate the legality of moves, and I haven't begun to figure out what kind of complicated algorithm that will take.

This rule would definitely make it more difficult to implement a computer opponent with a high skill level (although I agree with H.G. that it's already extremely difficult.)  One of the things you need in a chess program is a way to efficiently store a board position – a snapshot encoded in a number or number.

In Chess, for example, this is made more difficult because just knowing the position of all the pieces and who’s turn it is to move isn't enough.  You also need to know what castling rights are still available and if an en passant capture is possible.  So this extra information is also encoded into the representation of the position (the hashcode.)  With this rule you also need to know which chieftains have activated (although this could certainly be encoded as well, and the cost probably wouldn't be too bad, but it is one more thing to have to program in.)

Actually, in Chess (and almost all other variants), there's something even nastier...  You need  to know, for each position you could later encounter, is it a 3-fold repetition?  Or a 50-move draw?  So your hashcode also needs to store information about every position back to the last capture or pawn move...   This proves to be so costly, however, that it isn’t even done at all (for most uses of the hashcode), and this produces definite bugs!  Such bugs are known and very rare and the overall benefit far overshadows the penalty of having the bug.  Here's how it works specifically --  When the engine 'thinks', it recursively plays out moves and counter-moves.  A huge optimization that can be done is to realize that lots of different combinations of moves play out to the same position!  So, when you encounter a position, you look it up in a big table of positions you’ve recently seen to see if you recognize it and if what you learned about it then was 'good enough' so that we don’t have to think about it any more now.  The problem is that the hashcode (which locates information in this table) does not include information about past positions, so sometimes you jump to the wrong conclusion and the information really isn’t 'good enough.'  For example, last time you saw it you decided it was great.  But this time you came here by a different set of moves, you've seen this position multiple times before, and this time it’s not good, it's a draw by repetition.  Oops...

Ok, I digress.  Chieftain Chess.  I don't know that this consideration is significant enough to consider changing the rules but I thought I'd throw it out there.  And that last paragraph is to show you that even imperfect hashcodes aren't necessarily the end of the world.  It just makes it somewhat harder to program because you do have to account for it correctly in actual play (e.g., Chess programs really do need to detect 3-fold repetition correctly when they occur on the actual board; the bug with the hashcode table just makes the computer opponent less smart.)  But a computer opponent for this game is really, really tough anyway because of the multiple moves...  If human players can't see very far ahead in this game either, it might be ok...  But zillions-of-games is, to the best of my knowledge, the only program in the world that plays such games at all at present.  I've always considered trying to implement it, but it is just such a daunting challenge.  I'd be sailing way off the charts; there's nothing written about how to do such a thing at all unless it's very recent.

Visiting family this weekend, so I'm slow in answering again. Yes, each chief has only 1 order to give per turn, then it's used up until next turn. It's a very restricted game in this sense; that's why I call these variants 'structured multi-move games'. A very definite structure is imposed by the leader rules.

I'd thought the game might be difficult for computeres because there are so many different moves, all of which have essentially the same 'value' in chess terms. And given the multi-move nature, the number of possibilities explodes even on turn 2, and except in very restricted circumstances, you cannot calculate a 'most likely' progression of moves even 3-4 moves deep with any significant likelyhood of success. I will say that the game rarely degenerates to 4 separate battles. The chiefs generally work in pairs or larger groupings.

I don't think an engine for this would be hard to program. What would be hard is to make it search deep enough to acquire a reasonable skill. The way I would do it, is to use 4 recursive calls to the search routine for each turn, (or as many as you have Chieftains), doing the negamax flip only once every 4 ply. Each ply would cycle through all pieces, for each piece, cycle through all Chieftains, for each Chieftain that is within range, replace that Chieftain by an 'exhausted Chieftain' (a different piece type, that moves as a Chieftain, but has no activation power) and generate all moves with the piece, and play them out one by one. After moving the piece, you recurse. For efficiency you would keep track of the number of 'charged' Chieftains, and if your move just exhausted the last one, you flip the turn (and score, etc.), and 'recharge' the opponent's Chieftains. I would rely on hash hits to weed out the intra-turn transpositions, probing after each ply. (The turn-phase would automatically be hashed, because the charging and exhausting of Chieftains would alter the hash key.)

That is realy all. But now try to reach meaningful depth...

Very well thought out, H.G.  I see no flaws in that.  Of course, not seeing deeply it's not going to play very well.  Maybe you could use some sort of plan-oriented play ...  Examine the grouping of pieces on the board, decide where you appear to have superiority and focus on moves that concentrate force in this area, heavily reducing or pruning moves that don't.  On the other hand, in some circumstances it might be better to find where the opponent appears to have superiority and move in reinforcements, but I would expect this game is won by relentless offense.  Very interesting game!

Has anyone tried to make a Zillions implementation?

Okay, I have a plan for detecting conflicts between moves that rely on the activation power of the same Chieftain. I start with a set of all combinations of orders in which Chieftains may be used on the same turn. This is a 24 member set, just 4!, which is not too large. For each move, I identify the Chieftains on the board that could have activated that move. I then remove from the set any combinations that don't allow for the current move. If the set becomes empty at any point, then the move is illegal. If I go through all moves, and the set still has members, then a different Chieftain could be used to activate each piece that moved. This is all I need to know to tell that otherwise legal moves were all legal. 

It is not important to tell which Chieftain activated which piece, but besides checking the legality of each move, I need to identify which Chieftains can still be used to activate moves. I can do this by checking the place in each combination for the next move. Any Chieftain mentioned in that place will still be good for activating a piece, and its vicinity can be colored.

This plan for telling which pieces can move ahead of time would be useful in writing a program to play the game. It might be doable in Zillions-of-Games by manipulating flags or piece attributes, but I don't think I will attempt it. Even if it can be done, I think it would overcomplexify things to the point where Zillions will not play it well. As in Shogi, as it was originally implemented in Zillions, there will be multiple moves it can make in the same turn that will lead to the same position at the end of the turn. This will make it more difficult for it to look ahead. In a dedicated engine, it would be helpful to group together all combinations of moves that lead to the same position and pick just one of them at random as representative of all of them when analyzing the position.

I must say that non-programmers create the most difficult games to program. Examples include Marseillais Chess, Hostage Chess, and this game. As a programmer, I normally design my own games with an eye to how I'm going to program them. At least the non-programmers give me more interesting challenges than I give myself, and when I'm done there's more cause for feeling satisfied. It now looks like I finally cracked this nut and got a working preset for the game. Please check it out, Joe, and let me know if everything is working okay.

I have a question concerning another rule:

Once a piece has finished its move, it becomes inactive again. It cannot move in a subsequent turn without being re-activated by a chief.

Does this allow for the same piece to be moved twice or more in a turn if it gets activated by multiple Chieftains? Currently, the preset doesn't allow the same piece to move twice in a turn. Should I change this?

Hi, all. Again, no time. Kudos to Fergus for the preset - it effectively
does what I do in looking at [potential] moves. You've made it a little
easier to play the game. 

HG, I also am concerned about the possibility of draws here. But 4 chiefs
plus 2 men wins against 4 chiefs. I think a 1 man advantage should be
enough, as long as you can trap 1 chief. You force a chief for man trade,
and that's the game.