C Program for 21 Sticks game

Here is a good brain refreshing puzzle that I solved recently. Thanks to my friend Raghul for sharing this good piece of puzzle with me. Its a turn based 2 player game (player and computer in our case). c

Now, I am to write a program for this game in such a way that however the player plays, he always picks the last one and thus the computer wins. Looked very simple at first and I came with the following program in 15 minutes and thought to myself (very proudly) that I solved it.

    
    int lineCount;
    int userPick;
    int aiPick;

    lineCount = 21;
    while (lineCount > 1) {
        printf("\n\n%d lines remaining. Pick 1 or 2 or 3 or 4: ", lineCount);
        scanf("%d", &userPick);
        lineCount -= userPick;

        if (lineCount == 1) {
            printf("\nyou win and AI lose\n");
            return;
        }
        if (lineCount <= 5) {
            aiPick = lineCount - 1;
        } else {
            aiPick = rand() % 4 + 1;
        }

        printf("you took %d lines", userPick);
        printf("\nAI took %d lines", aiPick);
        lineCount -= aiPick;
    }
    if (lineCount == 1) {
        printf("\nyou win and AI lose\n");
        return;
    } else {
        printf("\n1 line remains and u lose\n\n");
    }

The AI seems to be working good, but its not perfect. It fails occasionally, especially when the player gets a turn with the remaining number of sticks in the range 2 to 5. So I tried to fix this by playing in such a way that AI always gets its turn when the remaining number of sticks is in the range 2 to 5. But I couldn’t figure out how to do this inside my little mind. So I took a pen and paper and started writing the remaining number of lines, all possibilities of AI’s move and corresponding result, which resulted in a table such as this:

Possible States with results
Remaining Sticks AI Move Worst Case
2 1 Win
3 2 Win
4 3 Win
5 4 Win
6 1 Lose
2 Lose
3 Lose
4 Lose
7 1 Win
2 Lose
3 Lose
4 Lose
8 1 Lose
2 Win
3 Lose
4 Lose
9 1 Lose
2 Lose
3 Win
4 Lose
20 1 Lose
2 Lose
3 Lose
4 Win
21 1 Lose
2 Lose
3 Lose
4 Lose

Only after completely writing out the above table, I found that when there are some certain magic remaining sticks at your turn, regardless of your move, if ur opponent plays his best move, he can win. The magic numbers are found to be 21, 16, 11, 6 and of course 1.

Since the player begins the game with 21 remaining sticks (one of the magic number), as long as my AI plays its best move, it can win. The AI’s best move nothing but the move which makes the remaining number of lines to the next lowest magic number and as we continue when the player plays his move, he will have the remaining sticks as 16, 11, 6 and finally 1 and he loses. Here is the final working program with perfect AI:

#include <stdio.h>

int lineCount;

void main() {

    int userPick;
    int aiPick;

    lineCount = 21;
    while (lineCount > 1) {
        printf("\n\n%d lines remaining. Pick 1 or 2 or 3 or 4: ", lineCount);
        scanf("%d", &userPick);

        lineCount -= userPick;

        if (lineCount >= 17 && lineCount <= 20) {
            aiPick = lineCount - 16;
        } else if (lineCount >= 12 && lineCount <= 15) {
            aiPick = lineCount - 11;
        } else if (lineCount >= 7 && lineCount <= 10) {
            aiPick = lineCount - 6;
        } else {
            aiPick = lineCount - 1;
        }

        printf("you took %d lines", userPick);
        printf("\nAI took %d lines", aiPick);
        lineCount -= aiPick;
    }

    printf("\n1 line remains and u lose\n\n");
}

I am sure this is not the best way to solve this problem, I should have done some research on maths and find some elegant solution, but I guess this is fine for the first step and to achieve the goal. I will look into other possible elegant solutions and if I find any, I will post about it later.

Happy Programming !!!

4 thoughts on “C Program for 21 Sticks game

  1. Pingback: C Program for 21 Sticks game | Gethu Games – Blog | Sticks

  2. your code is untide. here is a tide one(completely made by me and i am proud of it):

    #include
    int main()
    {
    int comp,i,count=0,n;
    printf(“RULES\n”);
    printf(“- There are 21 matchsticks.\n”);
    printf(“- Press 1,2,3 or 4 to pick the number of matchsticks\n”);
    printf(“- If forced to pick 21, you loose\n”);
    while(count<21)
    {

    Scan: printf("user:");
    scanf("%d",&n);
    if(n4)
    {
    printf(“Wrong move\n”);
    goto Scan;
    }

    for(i=1;i<=n;i++)
    {
    printf("%d ",++count);
    if(count==21)
    {
    printf("You loose");
    return 0;
    }
    }
    comp=5-n;
    printf("\nComp:%d\n",comp);
    for(i=1;i<=comp;i++)
    {
    printf("%d ",++count);
    }
    printf("\n");
    }

    return 0;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>