11
\$\begingroup\$

From Wikipedia:

Chopsticks is a hand game for two players, in which players extend a number of fingers from each hand and transfer those scores by taking turns to tap one hand against another.

In this challenge "splits" can only be 4->2+2 or 2->1+1.

Challenge

Your challenge is to make a bot (think the AI and framework of a chess program, but not chess) to play Chopsticks.

The game is as follows:

  • Both players (computer and player) start with 2 hands, and 1 finger raised on each hand. (aka the player and computer hands are both [1,1])

  • The players alternate turns. To move, the player taps one of his hands against the other person. Let player 1's hands be [2,3] and player 2's hands be [3,4]. If player 1 taps his first hand against player 2's second (2 vs 4), then player 1's first hand is added to the total of player 2's second hand, modulo five (6 mod 5 = 1).

  • Another explanation: x is the hand player 1 uses to tap player 2, and y is the hand getting tapped (which belongs to player 2), y += fingers(x); y = y mod 5.

You cannot make a move with a hand that has 0. However, if one of your hands is empty and the other one has 2 or 4 sticks, you can split that hand to make your hands [1,1] or [2,2] (this counts as a move, so you don't tap that turn)

If your hands are [0,0], you lose. Same with the other player.

Chopsticks is more or less a solved game1, meaning that neither player 1 nor player 2 can win if the other is a perfect player. Your bot must be a perfect player. (aka it will keep going forever or until it wins, it will never lose) This also means your program must loop indefinitely, it can't rely on recursion (just as an example).

Input and output can be in any acceptable way.

Examples

IO is the right column, odd rows are first player's moves, even rows are second player's moves. Left column is the fingers of the players at that point.

Your bot will always be the second player.

First Second  I/O

[1,1] [1,1]
              [1,2]
[1,1] [1,2]
              [2,2]
[1,3] [1,2]
              [2,1]
[1,3] [4,2]
              [1,1]
[0,3] [4,2]
              [2,2]
[0,3] [4,0]
              S
[0,3] [2,2]
              [2,2]
[0,3] [2,0]
              [1,2]
[0,0] [2,0]

Result: 0-1

Also, there are many variations of this game. For example, some variants have your hand empty if it's above or equal to 5, i.e. 2 vs 4 will give 0, instead of 1 (which is 2+4 mod 5). The rules listed here are the ones you will use however.

Good luck and happy golfing!


[1]: [citation-needed]. I found on the internet that the second player can always win if splits can be arbitrary but neither players have a winning strategy, but I don't know if I should be trusting random blogs. Games like Connect 4 game have a few papers on them, but I could find none on this game.

\$\endgroup\$
  • \$\begingroup\$ Do you know it is possible to play without losing? You can't ask something that may be impossible without this being closed as unclear or too broad. \$\endgroup\$ – FryAmTheEggman Apr 22 '17 at 21:24
  • \$\begingroup\$ @FryAmTheEggman on Wikipedia and other websites they mention that the first player can always force a win if the splitting rule includes transferring, but no websites show a way if transferring is banned. I didn't want to include transferring in this challenge because I thought it would be hard to I/O them. \$\endgroup\$ – betseg Apr 22 '17 at 21:36
  • 1
    \$\begingroup\$ You haven't answered whether what you have asked is known to be possible. As it stands, I have to say this is too broad. If you find out otherwise make sure you draw attention to your change. \$\endgroup\$ – FryAmTheEggman Apr 22 '17 at 21:39
  • 2
    \$\begingroup\$ I read this through a couple of times but still don't think I understand the rules of the game. Additionally, I'm not sure the "you have to be able to play as the first player or as the second player" clause adds to the challenge, and if you want to keep it, you'll have to explain how it works. \$\endgroup\$ – user62131 Apr 22 '17 at 21:52
  • 1
    \$\begingroup\$ If you have no proof that neither player should ever lose then why not just make the criteria that the bot must "play optimally" instead of being "one that never looses", that way the bot may loose if in a loosing position already. \$\endgroup\$ – Jonathan Allan Apr 23 '17 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.