For my final project, I decided to virtualize the game, Chopsticks, in order to combine the keyframing techniques I learned from this class with concepts from my artificial intelligence course (CSCE 420). After starting the program, the user/player uses the keyboard to input what hands they are using and targeting. Once the player makes a move, the computer opponent uses the minimax search algorithm to decide what move to make. In order to conserve resources, I limit the search to a depth of 3 by default. The computer is still challenging to defeat with this limitation.
There are several variants of Chopsticks. I simply implimented the rules that I am most accustomed to playing with.
Here's how the game works:
Each player starts the game holding up only thier index finger on each hand. On thier turn, a player taps their opponent's hand. The opponent raises as many fingers on their tapped hand as were raised on the hand that the acting player tapped it with. If the number of fingers they need to raise exceeds the five fingers they have on their hand, they start back over at one. If an attacked hand ends up with exactly five fingers raised, that player must lower all the fingers on that hand. It can no longer attack or be attacked. The most controversy (in my experience) comes with the next rule: instead of attacking, for their turn, a player with one inactive hand and a hand with an even number of raised fingers may bump their hands together and evenly divide the raised fingers between their hands, reviving their dead hand. When both of a player's hands are rendered inactive, they lose.
First, I used my submission from the keyframing assignment as a starting point. I implemented classes for the hands and fingers, which store and calculate game and model transformation data. Most of the calculation happens in the hand class, which stores and dynamically sequences the keyframes that the hand's model should follow. Since the hands are visually identical, I only needed to create keyframes relative to one hand's model and scale or rotate the other hands as necessary before transforming them with the keyframe data.
After adding the keyframes, I implemented the keyboard input through the provided char_callback() function to test them. Once the animations were working, I began work on input handling so that the user/player's input would only be considered if it was a valid input for gameplay. Next, I implemented the bot and minimax node classes. The bot class uses minimax search (down to its specefied maximum depth) to determine what move to make and produces a string that denotes its move for the program to handle.
Minimax search involves a search tree, where each node represents a game-state, and each node's children represent states that can be reached from that node's state. Each node also has a utility value, which represents how desireable its state is for the searching player. Typically, a node's utility is zero if it is not a terminal state, and terminal nodes' utilities are positive or negative one, depending on which player wins. Once the tree is generated, the leaves' utility values are propogated up the tree. Each node is either a "max" node or a "min" node. Max nodes receive the maximum utility of their children and represent turns of the searching player. Min nodes receive the minimum utility of their children and represent the turns of the searching player's opponent. This minimum-maximum structure reveals what state the game will end at, assuming both players play optimally.
Since I limited the depth of the search tree, to avoid having the computer choose between a bunch of zero-utility states, I altered the utility heuristic. Non-terminal nodes receive a utility equal to the sum of the computer's raised fingers minus the sum of the player's raised fingers. Terminal nodes receive a utility of positive or negative one-hundred, depending on who won.
I modeled the hands using OpenSCAD, and used MeshLab to convert them from .stl format to .obj format.
Here are the controls:
f:
select left hand
j:
select right hand
r:
tap forward with left hand
t:
tap across with left hand
u:
tap forward with right hand
y:
tap across with right hand
Spacebar:
bump hands / start another game
last updated: 12/11/23