Chess with incomplete information

[AlvaroBegue]

The bidding takes place 'double blind': both sides make their bid without the other seeing it, then the bids are revealed, and if the bids happen to be equal, or the piece's owner bids more, the piece stays. Otherwise it is removed. Both sides lose all the coins they have been bidding, also the side that lost. The players are aware of the number of coins they each have before the bidding starts.

There is an ambiguous case of both bidding with (0,0), in which the current description suggests that the piece stays since the bids are equal. But this means once the players run out of coins, no piece can be captured which is ridiculous. Hence we have to define it so that (0,0) is considered as 'no bid took place' to allow the piece to be captured. Oshu-zumo actually terminates the game in this case.

No, I thought that when I first read this thread, but then I read it more carefully: A capture happens normally, then the auction determines whether the attacking piece dies too!

[AlvaroBegue]

3) Using MCTS indeed sounds more straight-forward to implement. I haven't read the article that Daniel Shawul posted yet, but my intuition is that any randomized multi-armed bandit algorithm that tends to sample the moves with the highest success ratio most of the time will naturally converge to the Nash equilibrium. I don't think anyone has managed to make a reasonable chess engine using MCTS, but this game is different enough that it is worth a try.

One thing to bear in mind is that the current game is played with the mixed strategy nash equilibrium unlike other 2-player games we are used to such as Go, Chess etc where there exists a pure nash equilibrium. I know that MCTS for GO is proven to converge to alpha-beta, but it maybe a little different for simultaneous action games.

I do bear that in mind, and I stand by my previous statement. You can make a move selection algorithm that is randomized --that is, the move selection follows some probability distribution-- in such a way that the probability distribution converges to the [mixed strategy] Nash equilibrium. Not every move selection algorithm used in MCTS is randomized, but it wouldn't be hard to come up with one that would do the job.

[Daniel Shawul]

3) Using MCTS indeed sounds more straight-forward to implement. I haven't read the article that Daniel Shawul posted yet, but my intuition is that any randomized multi-armed bandit algorithm that tends to sample the moves with the highest success ratio most of the time will naturally converge to the Nash equilibrium. I don't think anyone has managed to make a reasonable chess engine using MCTS, but this game is different enough that it is worth a try.

One thing to bear in mind is that the current game is played with the mixed strategy nash equilibrium unlike other 2-player games we are used to such as Go, Chess etc where there exists a pure nash equilibrium. I know that MCTS for GO is proven to converge to alpha-beta, but it maybe a little different for simultaneous action games.

I do bear that in mind, and I stand by my previous statement. You can make a move selection algorithm that is randomized --that is, the move selection follows some probability distribution-- in such a way that the probability distribution converges to the [mixed strategy] Nash equilibrium. Not every move selection algorithm used in MCTS is randomized, but it wouldn't be hard to come up with one that would do the job.

My point is that proofs you know of MCTS that converge to alpha-beta have a pure nash equilibrium. You can't make the same statement for simultaneous action games that have a mixed-strategy nash equilibrium so that is why I said it could be a _little_ different. We have the proof for the two-player perfect information from Kocsis and Szepesvári (Go,chess), but not for an imperfect information game. Btw this game is technically not an incomplete information game as the title says but an imperfect information. Intuition doesn't count for much as this poster asked the same http://math.stackexchange.com/questions ... ence-proof

[Daniel Shawul]

The bidding takes place 'double blind': both sides make their bid without the other seeing it, then the bids are revealed, and if the bids happen to be equal, or the piece's owner bids more, the piece stays. Otherwise it is removed. Both sides lose all the coins they have been bidding, also the side that lost. The players are aware of the number of coins they each have before the bidding starts.

There is an ambiguous case of both bidding with (0,0), in which the current description suggests that the piece stays since the bids are equal. But this means once the players run out of coins, no piece can be captured which is ridiculous. Hence we have to define it so that (0,0) is considered as 'no bid took place' to allow the piece to be captured. Oshu-zumo actually terminates the game in this case.

No, I thought that when I first read this thread, but then I read it more carefully: A capture happens normally, then the auction determines whether the attacking piece dies too!

Wow all this time, I thought the bidding was to prevent our piece from being captured! Indeed it seems we are bidding for the attacker's removal without making a move... I guess this makes the game less exciting because if we capture with PXQ, the SEE routine with bidding would give almost the same result as standard SEE. We don't care if we loose the pawn so I will automatically bid with 0 and save my coins for later. That would not have been the case if we opponent could have prevented Q from being captured preventing a major disaster.
--------------------------------------------------------------------------------------
I prefer the oshi-zumo game to study the bidding process. The game is simple, we start with 50 coins each, and there is a sumo-wrestler (S) placed at the center.

Code: Select all

|-|-|-|-|-|S|-|-|-|-|-| 

Then we make bidding moves to move him one step right or left depending on who bid more. Game ends when both players run out of coins, in which case the loser is in whose half S is. Also if we managed to drive him off the edge before that game ends.
------------------------------------------
Edit: Sigh,wrong diagrams again. Critical cells are bid equally (save piece) and opponent bids with one more coin to capture back attacker.

White captured and bidding to save its piece:

Code: Select all

         B
      0 1 2 3 
    0|X|X|-|-| 
W   1|-|X|X|-| 
    2|-|-|X|X| 
    3|-|-|-|X| 

Black captured and bidding to save its piece:

Code: Select all

         B
      0 1 2 3 
    0|X|-|-|-| 
W   1|X|X|-|-| 
    2|-|X|X|-| 
    3|-|-|X|X| 

Also the SEE with coins has become significantly easier especially for move ordering as done with MVV/LVA.

Code: Select all

Winning captures: PXQ -> capture and bid with 0
Equal captures: NXN -> capture and bid with 0 (won't loose anyway)
Loosing captures: QXP -> Don't do it because opponent will probably give up all its coins to capture back, again similar to standard SEE.

All of them already predicted by MVV/LVA very well, so coins are only important when we test loosing captures according to MVV/LVA _and_ the opponent doesn't have a piece to capture back in which case he can use his coins to re-capture the attacker. This is a very rare case because most QXP are unsafe.

I really don't like this change because it seems to have dropped the value of coins significantly. If a player looses all its coins, all he has to do is not try loosing captures, i.e.according to MVV/LVA, while having the freedom of making equal and winning captures. That is what is mostly done in standard chess anyway. But in the previous rule's interpretation, he would not be able to bid to retain his threatened piece which is a much severe punishment. The SEE is more exciting because we could have prevented PXQ by bidding more for our queens.

[Daniel Shawul]

What about king captures?. Can the opponent bid to remove it (thus chekmate) i.e. if the opponent is dumb enough to try it when he knows he has lesser number of coins? The second option is not to allow capturing with the king, but this would make contact checkmates much easier when we have larger number of coins than opponent, e.g. putting a queen on a safe square in front of king that is on the edges is enough to checkmate, when we have more coins. So for this reason, I prefer the first one, but this will result in a weird kind of checkmate! You invented this game, HG, so say something.
Edit: A third option is that king can not be bid-on, i.e he can freely capture. This seems better as it avoids both the above problems.

[hgm]

Good question. I don't really know how this is handled in Chess 2. Without any special rules I would say it is forbidden to capture something with a King without bidding at least the number of coins you ropponent has, for anything other would be equivalent to exposing your King n check. Alternatives could be to allow exposing Kings to check and using King capture / removal as winning condition (but stalemate would have to be dropped, or reformulated in a cumbersome way), or indeed forbidding to bid on a King. The latter is perhaps the simplest and cleanest way. So for this model game, let us assume that.

I have not had time yet to digest all your postings about this, Some short remarks, however:
- A player that captured a piece through a board move does receive a new coin after the bidding. So in principle the number of coins the players have in hand can grow much larger than 3, although it probably would not make sense to pile them up.
- A position where you have an extra coin is guaranteed to be better as one where you do not have it, by at least the static eval of one coin. Because you could always play exactly the same as without that coin, by never using it, and you would then have that coin in each leaf. But the difference can be much larger, because the extra coin could guarantee winning a piece which you otherwise could not win (or not losing it).
- The static eval of a coin might be dependent on what is the strongest piece on the board much more than for a normal piece.

The latter two point make it difficult to even predict the relative values of the various outcomes of a bidding. Perhaps it makes sense to use information from IID here, however. If searches at lower depth would have provided you with lower limits of the outcomes and probabilities to play them that were sufficient for a cutoff, you could assume the same bidding probabilities first, and decide from that what thresholds you should use on the deeper search of the most-critical outcomes. E.g. if bidding 0 or 1 coin 50-50 was best at the previous depth, you could first try to do that at full depth too, and first seach the 1-coin bid with alpha shifted down half a coin, as the other outcome is guaranteed to be at least one coin better, so that the expectation value with 50-50 bidding would be above alpha if your 1-bid outcome made it above alpha - coin/2.

Fixing bidding probabilities at low depth, and then sticking with them as long as they still provide cutoffs, is not unlike what you normally do in alpha-beta: you find a cut move, which doesn't need to be the best move at all, and it becomes hash move, which will be the only move tried in future visits to the node, as long as it remains a cut move. At QS depth the relative value of the bidding outcomes will be easier to guess, because you are very close to static eval, so the chances that excess coins can be converted into some larger gain than their eval value are not that large yet.

[Daniel Shawul]

Good question. I don't really know how this is handled in Chess 2. Without any special rules I would say it is forbidden to capture something with a King without bidding at least the number of coins you ropponent has, for anything other would be equivalent to exposing your King n check. Alternatives could be to allow exposing Kings to check and using King capture / removal as winning condition (but stalemate would have to be dropped, or reformulated in a cumbersome way), or indeed forbidding to bid on a King. The latter is perhaps the simplest and cleanest way. So for this model game, let us assume that.

Ok about the king. Here is what is causing the who are we bidding on situation , the attacker's removal or the piece to be captured. Apparently you were thinking of the attacker, and I was thinking of the latter, so no wonder I didn't understand some of your posts and probably you didn't understand mine either. There still seems to be something unclear. Do we bid for attacker's removal, when we have the option of capturing with our piece ? . e.g. PXP PXP PXP, In the second pawn capture, black can bid to remove the attacker by bidding alone and not loose one more pawn by capturing back! So two different outcomes of 'biding-captures' and 'standard-captures. The way I interpreted it, i.e. always bid on the piece you want to capture, doesn't lead to such situation and also makes the SEE very interesting. In the current way, bidding is mainly unnecessary in a long series of captures at intermediate points, but only at the end when one side runs out of a piece to capture-with, in which case he is forced to use his bidding to capture-back.

I have not had time yet to digest all your postings about this, Some short remarks, however:
- A player that captured a piece through a board move does receive a new coin after the bidding. So in principle the number of coins the players have in hand can grow much larger than 3, although it probably would not make sense to pile them up.

That is good as that will give some initiative the second PXP capture in my example.

- A position where you have an extra coin is guaranteed to be better as one where you do not have it, by at least the static eval of one coin. Because you could always play exactly the same as without that coin, by never using it, and you would then have that coin in each leaf. But the difference can be much larger, because the extra coin could guarantee winning a piece which you otherwise could not win (or not losing it).

Exactly this is what I was exploiting to reduce the number of payoff computations. We simply set the value of non-critical bidding to some payoff we computed for a critical cell plus/minus number of coin differences. Ofcourse it is will not be accurate, but it can reduce the number of searches from O(N^2) to O(N) making the brute-force approach feasible for many coins. The critical payoff matrix is of banded form, where at the diagonal both bid equally and off-diagonal one of them bid by +1 more coin.

Edit:
A second advantage of this method is that you are sure the payoff for a situation with one pawn less is always less by atleast p-coin_val AND if you get a score that is higher than that you just ignore it. This can happen in both MCTS and also alpha-beta too when you have different extensions, hash-table etc that will not guarantee similar kind of path will be searched. This is very unique because in standard alpha-beta, if you get a score higher than beta you assume you failed high but in this case we know the search/mcts screwed up!

I will have to think of the rest of your post.

- The static eval of a coin might be dependent on what is the strongest piece on the board much more than for a normal piece.

The latter two point make it difficult to even predict the relative values of the various outcomes of a bidding. Perhaps it makes sense to use information from IID here, however. If searches at lower depth would have provided you with lower limits of the outcomes and probabilities to play them that were sufficient for a cutoff, you could assume the same bidding probabilities first, and decide from that what thresholds you should use on the deeper search of the most-critical outcomes. E.g. if bidding 0 or 1 coin 50-50 was best at the previous depth, you could first try to do that at full depth too, and first seach the 1-coin bid with alpha shifted down half a coin, as the other outcome is guaranteed to be at least one coin better, so that the expectation value with 50-50 bidding would be above alpha if your 1-bid outcome made it above alpha - coin/2.

Fixing bidding probabilities at low depth, and then sticking with them as long as they still provide cutoffs, is not unlike what you normally do in alpha-beta: you find a cut move, which doesn't need to be the best move at all, and it becomes hash move, which will be the only move tried in future visits to the node, as long as it remains a cut move. At QS depth the relative value of the bidding outcomes will be easier to guess, because you are very close to static eval, so the chances that excess coins can be converted into some larger gain than their eval value are not that large yet.

[hgm]

Do we bid for attacker's removal, when we have the option of capturing with our piece ? .

The bidding is for removing the attacker. The captured piece will always disappear; it is just a matter of whether the capture square will remain empty after that, or whether the piece that made the capture is allowed to stay.

In the current way, bidding is mainly unnecessary in a long series of captures at intermediate points, but only at the end when one side runs out of a piece to capture-with, in which case he is forced to use his bidding to capture-back.

I am not so sure. Even when you can recapture, it might still be preferable to remove the piece by bidding. Remember that if yu would recapture it, your piece could be removed by bidding. It is true that in this case you would have the advantage in case of equal bids, rather than him, but you also risk an extra piece, which could be valuable.

For the search strategy that must replace alpha-beta this kind of detail doesn't seem very important.

[Daniel Shawul]

Do we bid for attacker's removal, when we have the option of capturing with our piece ? .

The bidding is for removing the attacker. The captured piece will always disappear; it is just a matter of whether the capture square will remain empty after that, or whether the piece that made the capture is allowed to stay.

In the current way, bidding is mainly unnecessary in a long series of captures at intermediate points, but only at the end when one side runs out of a piece to capture-with, in which case he is forced to use his bidding to capture-back.

I am not so sure. Even when you can recapture, it might still be preferable to remove the piece by bidding. Remember that if yu would recapture it, your piece could be removed by bidding. It is true that in this case you would have the advantage in case of equal bids, rather than him, but you also risk an extra piece, which could be valuable.

For the search strategy that must replace alpha-beta this kind of detail doesn't seem very important.

The reason why I think this way of bidding takes steam off the game is because we are not allowed to prevent the capture of a piece on the first move by bidding. Winning captures (PXQ) and equal captures (NXN) are as safe as always been, and loosing captures (QXP) are as bad as always been. That is not the case if we had bid to avoid the capture of queen in a PXQ saving a major disaster.

And also it introduces a weird move where a piece can be removed by bidding alone (i.e. we don't have a piece to capture the attacker with). For example what used to be a safe QXP capture are no more safe if the opponent has more coins. The weird move has already manifested itself in the king-capture situation, which the 'bid for the captured' piece could have avoided and also added some different angles to SEE.