Project
CHECKERS GAME :
Do you want to
play Checkers ?
Oh....Yes .
Then why you don't join to
us.
PROJECT
GROUP :
ROLL NO.
E-MAIL ID
ANKUR JAIN
Y2076
ankj
ANOOP KUMAR
Y2081
anooopkg
LAVAKUSA
REDDY
Y2194
lavakusa
In checkrs ;there are
alternate sqare boxes of two different
colors in which one have to choose
the boxes of same color
to play.
Project Idea:
Who will move
first?
The red pieces
always move first in Checkers.
If Human want to play with the red pieces, he should
start first
. If Human want to play with the white pieces, he should click
anywhere
on the upper half of the board (the computer will move a
red piece).
How can a Human move by clicking on a
piece?
Use the mouse
to drag a piece where you want it to go.
When Human jump multiple pieces, Human need
to
drag
his piece over the first piece he want to jump, and
into the empty square beyond it, and
then continue
dragging over the second piece he want to jump,
and into
the empty square beyond that. Do not release the
mouse
button until you are finished making all your
jumps.
In the beginning, pieces can only move and jump
forward.
However, if a piece reaches the far end of the board
(in
your case, the top), then it becomes a king. (In
checkers,
a king is usually signified by stacking two
checkers one on
top of the other. In this program, the king has
a star on
it.) A king is allowed to move and jump
diagonally
backwards and forwards. Kings can be captured like
any
other piece.
How do Human win?
Human win by capturing all of
computer's pieces, or by
blocking them so that they cannot
move.
SOURCE :GOOGLE.COM
When you play a game with a computer, and the computer plays
back, the strategy for the computer's artificial intelligence is called the
computer
player algorithm. Computer player algorithms come in many different
forms and levels of complexity. In this article, we are going to take a quick
look
at the general theory of computer player algorithms, and then look at
the code to implement a simple computer player algorithm for a one- player
card
game.
Where Computer Player Algorithms are Used
Computer player algorithms are
an essential element of most card games, board games, and strategy games. In
these games, game play is not based on
hand-eye coordination, but rather on
luck and skillful decision making. The player tests his mental acuity against
his opponent, often taking minutes
or hours to decide his next move. After he
moves, he expects the opponent to make a skillful counter-move. If the opponent
is a computer, then the
move is determined by the computer player algorithm.
Computer player algorithms are most common in two-player games such as
checkers, chess, cribbage and backgammon, but you will also see them
in
multi-player games such as poker and Chinese checkers, and one-player
games like solitaire. In solitaire, the computer player algorithm is used for
both
the demo mode and the hint mode. In the demo mode, the player learns to
play solitaire (or simply entertains himself) by watching the computer
play
continuously. In the hint mode, the player plays his own game of
solitaire, but at some point needs help deciding which card to move next, so he
presses
a hot-key sequence for a hint.
Arcade games also have a type
of computer player algorithm. Even when game play is mostly action oriented,
there is still an element of strategy
involved. For example, in the game Pac
Man, a small hoard of ghosties tries to get you before you get them. The motion
of the ghosties is determined by
the computer player algorithm.
Sometimes adding a computer player algorithm will add new life to an old
game. An arcade game like Tetris, for example, which seems to do quite
nicely
without a computer player algorithm, will benefit when one is added.
You can use the computer player algorithm to generate a self-playing demo
mode,
which is useful for promoting your game. You can also find ways to
incorporate the computer player algorithm in the game play itself. For example,
you
could have time trials. Both the player and the computer get the same set
of bricks, and whoever stays alive the longest (or removes the most
bricks
during a fixed period of time) wins.
Writing a computer player algorithm
In order to write a computer player
algorithm, you need to understand the game thoroughly. Usually, that means you
need to play it over and over. If
you have been playing dominoes with your
family since you were in kindergarten, then you are a good candidate to write a
dominoes computer player
algorithm. If you just learned the rules to chess
yesterday, don't even attempt to write the program. Leave it to someone who
knows what they are doing.
Sometimes you can find documentation for
computer player algorithms. Books have been written about chess, checkers, and
bridge strategies. Clubs
exist for Scrabble and backgammon. Sometimes
graduate students write papers on these subjects. It may take a little digging,
but for classic problems
you can often get a head start by looking at
algorithms developed by others.
Ideally, you want to write your computer
player algorithm in such a way that the computer goes through the same thought
processes as a human
player. To do this, you need to start with a human
player, and watch how he plays. Ideally, the human player should be yourself.
Play the game over
and over, until you become an expert at it. In the process
of playing the game, pay attention to the decisions you make. Don't play by
"instinct" or
"intuition", rather try to understand the logic behind each
move you make. Once you understand why you make decisions, you will be able to
codify the
steps in the decision making process. In other words, write the
code to work exactly the way you think when you are playing the game.
For example, in solitaire, you often have your choice of several cards
that can be played. I always play the card that frees up the most other cards,
but I
try not to cut off my opportunities to play future cards. That means I
won't play a card if it is the last one on the row, it unless there is a king
waiting to
occupy that place, and I won't move a card to the discard piles if
I think it may be needed to capture a lower card later. Refer to the sample code
to see
how I implemented this.
Sometimes even an experienced game
player is not sure of the optimal algorithm. In the case of Solitaire, my
husband Ted and I could not agree on
whether the best strategy was to take a
card from the shortest column or the longest column. My argument was, clear up
the shorter columns so there
will always be a place to put a king if one
should appear. Ted said that was all wrong, you have to clear out the longer
columns and let the short columns
take care of themselves. How do you decide
which method is best? It?s very simple. You just write the program in such a way
that the computer can play
against itself. Then you let the computer play
against itself over and over. In my case, I let the computer play 1000 games.
Then I tweaked the algorithm
and let it play another 1000 games. I kept doing
this, recording the number of wins, until I had what I considered to be an
optimal algorithm. The
next_move() function in Figure 3 made this kind of
optimization strategy quite simple.
The next_move() function only makes
one move at a time. I believe, in general, this is the best way to write a
computer player algorithm. In the case of
solitaire, this allows the human
player to control whether he makes the moves, or whether the computer does. In a
multi-player game, the computer
player algorithm should be general purpose
enough so that it can make anybody's next move. In a game such as Chinese
checkers, the computer player
algorithm should be able to examine the state
of the game from the point of view of any player, and make the optimal move for
that player. That way,
one function can handle all the moves for all the
computer players and can be used for the cheat mode for the human player.
Levels of difficulty
The rules of solitaire are fixed, so we can't have
different levels of difficulty. In multi- player games, you will want to
incorporate different levels of
difficulty in your computer player algorithm.
This is important, because many players will start at the novice level and will
continue playing until they
reach the expert level. In fact, this is what you
want them to do. You want people to play your game over and over, and become
addicted to it. If your
game always beats them too often in the beginning, or
if they always beat it, they will get tired of playing it and move on to
something else. So it is best to
gear your levels of difficulty toward a
broad spectrum of players.
There are many ways of adjusting the level of
difficulty of a game. You can use the trick of letting the computer play against
itself to determine the best
algorithm, and then use the second-best
algorithm as the medium difficulty level, and the third best algorithm as the
easy level. Another strategy is to
take your best computer player algorithm,
and stop part way through. For example, if you have a word game that examines
30,000 words at its best level,
have it examine 10,000 words at the medium
difficulty level, and 5,000 words at the easy level.
While these ideas
work in theory, in actual practice the easy and medium difficulty levels may not
feel right to the players. That is why it is so important
to have beta
testers and to play the game many times yourself. Remember, the goal is not to
write a game that always wins, but to write a game that is
fun to play.
Adding Personality
While it is not absolutely necessary to have the
computer exhibit personality while playing against you, I think it greatly
improves the playability of
most games. When playing poker, for example, if
you are looking across the table at a gunslinger or a pretty lady, you will take
more pleasure in winning
the hand.
Cheating in computer player algorithms
This is, unfortunately, a common
practice in the gaming world. When the computer plays against you at bridge, for
example, it peeks at your cards. As a
programmer, I would take no pride in
writing a computer player algorithm that cheats. I believe the information that
is traditionally kept secret from
the human player should not be used in the
computer player algorithm. The computer player algorithm should be able to play
bridge without looking
at the opponent's cards. As a player, wouldn't you
rather win fair and square? The computer player should play by the same rules as
the human player.
About the Code
The code in Figure 3 is the computer player algorithm for
a game of computer solitaire. The entire algorithm takes place in one short
function called
next_move(). Recall that the object of the game is to remove
cards from the columns and the stack and place them on the piles. The stack is
replenished
from the deck, either three cards at a time (classic solitaire)
or one card at a time (Klondike). The next_move() function examines the columns,
the piles,
and the stack, and chooses the most favorable move based on the
current state of the game.
The first thing next_move() does is check if
there are any vacant columns, and any kings waiting for a vacant column. It?s
important that this
information be determined first, because it will affect
other decisions later in the function. It looks for kings both at the bottoms of
columns with more
than one card in them, and on the top of the stack. If it
finds one or more kings, the local variable king_waiting is set to TRUE.
The next step is to try to move one column to another column. Non-empty
columns (columns which contain face-down cards) are moved first, because
we
want to free up whatever cards may be hidden. If a non-empty column cannot be
moved, we try to move an empty column, but only if a king is
waiting. It is
pointless to move an empty column if there is no king waiting for it.
If
we are unable to move a column, we try to take a card off the stack and put it
on a column. Failing that, we try to take a card from the stack and put it
in
one of the discard piles. The next thing we try is taking a card from a column
and putting it on one of the discard piles. We have to be careful with
this
move, though. We don?t want to take cards off the column if they may be
needed later to take a card off the stack. For example, if a red three is still
in
the deck somewhere, we don?t want to remove all the black fours from the
columns. If the red twos have already been put on the piles, then we know
the
red threes are safe, so we can remove the black fours.
The next
move, in order of priority, is to remove a card from the deck and put it on the
stack. If there are no cards remaining in the deck, then we try
one last time
to take a card off a column and put it on a pile. If there are no advantageous
moves we give up, and return to the calling function. At this
point, the game
is over and it is time to shuffle.
Conclusion
Computer player algorithms are rarely talked about any more.
That is probably because everybody wants to write arcade games, and all they
want to
talk about is the frame rate. I think that is a mistake. After a
certain point, users no longer care how many frames per second they are getting.
What
they really want in a game is playability. The classic games are classic
for a reason. Something about them grabs the player?s attention, and makes
him
play them over and over. Games like poker and checkers will never go out
of style. This is to the game programmer?s advantage. Arcade games will
come
and go, and their faddish nature leads to a short shelf life, but people will
buy the classics forever. Therefore, it pays to study the nature of
the
classics, and perhaps even write a few yourself. The earmark of a great
classic game is an excellent computer algorithm.
void
next_move()
{
int col,card,suit,value,color;
int x1,x2,y1,y2,col1,col2;
int
card1,card2,value1,suit1,value2,suit2;
int
color1,color2;
char string[2];
int
first,valid;
int
card_moved,won,vacant,king_waiting;
int i;
int
col3;
/* check if a king is waiting for a vacant column
*/
no_moves = FALSE;
vacant =
FALSE;
king_waiting = FALSE;
for (i = 7; i >=
1; i--)
{
if (top[i] == 0)
{
vacant =
TRUE;
}
else
if (top[i] != 1)
{
card =
column[top[i]][i];
get_card_value(card,&value,&suit,&color);
if (value == 13) king_waiting = TRUE;
}
}
if (stacktop >= 0)
{
card =
stack[stacktop];
get_card_value(card,&value,&suit,&color);
if (value == 13) king_waiting = TRUE;
}
/*
try to move column to column without leaving a vacant column */
for (col1 = 7; col1 >= 1; col1--)
{
if (bottom[col1] != 0 && top[col1] !=
1)
{
card1 =
column[top[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
for (col2 = 7; col2 >= 1;
col2--)
{
if (col1
!= col2)
{
/* move a king to an empty column
*/
if (bottom[col2] == 0)
{
if (value1 == 13)
{
move_column(col1,col2);
return;
}
}
/* move col1 to bottom of col2
*/
else
{
card2 =
column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 != color2 && value2 == value1+1)
{
move_column(col1,col2);
return;
}
}
}
}
}
}
/*
leave a vacant column only if there is a king waiting for it */
for (col1 = 7; col1 >= 1; col1--)
{
if (top[col1] == 1)
{
card1 =
column[top[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 != 13)
{
for (col2
= 7; col2 >= 1;
col2--)
{
if (col1 != col2 && bottom[col2] != 0)
{
/* move col1 to bottom of col2
*/
card2 =
column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 != color2 && value2 == value1+1)
{
/* only move the top of column if a king is waiting
*/
if (!vacant && king_waiting)
{
move_column(col1,col2);
return;
}
}
}
}
}
}
}
/*
couldn't move column to column, try stack to column */
if
(stacktop >= 0)
{
card1 =
stack[stacktop];
get_card_value(card1,&value1,&suit1,&color1);
for (col2 = 7; col2 >= 1; col2--)
{
if (bottom[col2] == 0)
{
if
(value1 == 13)
{
stack_to_column(col2);
return;
}
}
else
{
card2 =
column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 != color2 && value2 == value1+1)
{
stack_to_column(col2);
return;
}
}
}
/*
couldn't move stack to column, try stack to the pile
*/
if (value1 == pile[suit1]+1)
{
stack_to_pile(card1,suit1);
return;
}
/* couldn't put stack on column or pile,
put matching card on pile? */
for (col2 = 7;
col2 >= 1; col2--)
{
if (bottom[col2] > 1)
{
card2 =
column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 == color2 && value1 == value2)
{
if (value2 == pile[suit2]+1)
{
column_to_pile(col2,card2,suit2);
return;
}
}
}
}
}
/*
if a card is the only card on a column, try to move it to a pile
*/
for (col1 = 7; col1 >= 1; col1--)
{
if (bottom[col1] != 0)
{
if (bottom[col1] == 1)
{
if
(king_waiting)
{
card1 =
column[bottom[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 == pile[suit1]+1)
{
column_to_pile(col1,card1,suit1);
return;
}
}
}
else if (top[col1] ==
bottom[col1])
{
card1 =
column[bottom[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 == pile[suit1]+1)
{
column_to_pile(col1,card1,suit1);
return;
}
/*
can't put it on pile, put matching card on pile?
*/
else
{
for (col2 = 7; col2 >= 1;
col2--)
{
if (col1 != col2 && bottom[col2] > 1)
{
card2 = column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1==color2 && value1== value2)
{
if (value2 == pile[suit2]+1)
{
column_to_pile(col2,card2,suit2);
return;
}
}
}
}
}
}
}
}
/*
couldn't move any cards, take one off deck */
if (decktop >=
0)
{
deck_to_stack();
return;
}
/* no more cards on deck, try to move a card to the pile
*/
for (col1 = 7; col1 >= 1; col1--)
{
if (bottom[col1] !=
0)
{
card1 =
column[bottom[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 == pile[suit1]+1)
{
column_to_pile(col1,card1,suit1);
return;
}
}
}
/*
give up -- there's nothing we can do */
no_moves =
TRUE;
return;
}