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.