# Game design : Making computer play

Discussion in 'Python' started by v4vijayakumar, Apr 14, 2008.

1. ### v4vijayakumarGuest

In computer based, two player, board games, how to make computer play?
Are there any formal ways to _teach_ computer, to choose best possible
move?

I know this is kind of off-topic here. Please redirect me, if there
are more appropriate newsgroup.

Many thanks.

v4vijayakumar, Apr 14, 2008

2. ### Marc 'BlackJack' RintschGuest

On Mon, 14 Apr 2008 00:13:56 -0700, v4vijayakumar wrote:

> In computer based, two player, board games, how to make computer play?
> Are there any formal ways to _teach_ computer, to choose best possible
> move?

That depends on the type of the game. For a certain class of games one
can use the `minimax method`_ for instance.

... _minimax method: http://en.wikipedia.org/wiki/Minimax

Ciao,
Marc 'BlackJack' Rintsch

Marc 'BlackJack' Rintsch, Apr 14, 2008

3. ### xakeeGuest

On Apr 14, 12:13 pm, v4vijayakumar <>
wrote:
> In computer based, two player, board games, how to make computer play?
> Are there any formal ways to _teach_ computer, to choose best possible
> move?
>
> I know this is kind of off-topic here. Please redirect me, if there
> are more appropriate newsgroup.
>
> Many thanks.

You should pick up some nice Artificial intelligence book and see for
the game playing section. Most of them have it. Teaching the computer
is almost like telling it all the possibilities. The actual teaching
is telling the computer how to decide which possibility is the best.
That is by using heuristics. All possibilities are normally
represented as trees, one move leading to another. Then there is are
pruning techniques, miny-maxy things where we deal with the concept of
minimizing opponents gain and maximizing your own. So you design
heuristics like that. (For example in the game of tic tac toe, there
can be say 5 moves to be made, and the heuristic function is the
number of moves a given player will win in.... and the computer
calculates that its 4 for him and 3 for you for a certain move.... he
will pick the next move with is maybe 3 for him and 4 for you and
execute that move). This is a very simplistic application but this is
how it goes. There are many searching heuristic based algorithms, some
blind search algorithms etc. They are very important in game playing
not just board ones but almost all of them. They are the foundation.
So I would recommend you to open some elementary AI book.

xakee, Apr 14, 2008
4. ### v4vijayakumarGuest

On Apr 14, 12:35 pm, Richard Heathfield <> wrote:
> v4vijayakumar said:
> > In computer based, two player, board games, how to make computer play?

>
> Write some code that works out what the computer player should do. If you

I am just implementing a game played in my village (Tamilnadu /
India), called "aadupuli" (goats and tigers). There are only 23
positions and 18 characters (15 goats and 3 tigers). Some of you might
be aware of this.

I can post initial version of the game (implemented using html/
javascript) in couple of hours here.

Welcome any help in making computer to play one of these player.

v4vijayakumar, Apr 14, 2008
5. ### WillemGuest

v4vijayakumar wrote:
) On Apr 14, 12:35 pm, Richard Heathfield <> wrote:
)> v4vijayakumar said:
)> > In computer based, two player, board games, how to make computer play?
)>
)> Write some code that works out what the computer player should do. If you
)
) I am just implementing a game played in my village (Tamilnadu /
) India), called "aadupuli" (goats and tigers). There are only 23
) positions and 18 characters (15 goats and 3 tigers). Some of you might
) be aware of this.

Odd, I thought there were 25 positions, 20 goats and 4 tigers.
*googles* Oh wait, that is Bagh Chal. Roughly the same rules,
different board layout and number of tigers.

) I can post initial version of the game (implemented using html/
) javascript) in couple of hours here.
)
) Welcome any help in making computer to play one of these player.

If the board is that small then an exhaustive search might work,
but then the computer would be unbeatable.

Minmax would be best I guess.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem, Apr 14, 2008
6. ### v4vijayakumarGuest

v4vijayakumar, Apr 14, 2008
7. ### Guest

On 14 Apr, 09:13, v4vijayakumar <>
wrote:
> In computer based, two player, board games, how to make computer play?
> Are there any formal ways to _teach_ computer, to choose best possible
> move?
>
> I know this is kind of off-topic here. Please redirect me, if there
> are more appropriate newsgroup.
>
> Many thanks.

can you post a link to the game so I can see the rules and how the
board looks.

/hopefully going to india soon

, Apr 14, 2008
8. ### WillemGuest

Richard wrote:
) Here's the board (which bears only a slight resemblance to one I'd seen on
) the Web):
)
) +---------------+
) | HORN \$ |
) +---+---+---+---+---+---+
) |L W| | \$ | \$ | |R W|
) +E-I+--CHEST+---+---+I-I+
) |F N| | | | |G N|
) +T-G+---+---+---+---+H-G+
) | | | | | |T |
) +---+---+---+---+---+---+
) | LEGS| | |
) +---+---+---+---+
)
) There are three tigers and fifteen goats.
) The tigers' goal is to eat all the goats and remain mobile.
) It seems that the initial tiger positions are: one on the horn, and one
) each on CHEST-2 and CHEST-3 (see \$ marks, above).
) The goats' goal is to block the tigers from moving.
) The goats are placed one by one.
) Tigers appear only to be able to move orthogonally (up/down/left/right) -
) although they can use the horn to whizz across the chest (e.g. CHEST-1 to
) HORN, HORN to CHEST-4, in two moves).
) The rest of the rules are beyond me, I'm afraid. It's not clear how tigers
) eat goats or how goats block tigers.

If it's similar to the 'other' goats and tigers game, a tiger eats a goat
by jumping over it, for which the square behind it needs to be empty,
obviously.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem, Apr 14, 2008
9. ### Carl G.Guest

"Marc 'BlackJack' Rintsch" <> wrote in message
news:-berlin.de...
> On Mon, 14 Apr 2008 00:13:56 -0700, v4vijayakumar wrote:
>
>> In computer based, two player, board games, how to make computer play?
>> Are there any formal ways to _teach_ computer, to choose best possible
>> move?

>
> That depends on the type of the game. For a certain class of games one
> can use the `minimax method`_ for instance.
>
> .. _minimax method: http://en.wikipedia.org/wiki/Minimax

While checking the Wikipedia, also check out the A* (a-star) graph search
algorithms:

http://en.wikipedia.org/wiki/A*

There is a table on the top-right of this page that includes other graph
search algorithms.

My AI games are usually built around general purpose mini-max code, possibly
inplementing A* (I reuse the same code for various games). For each new
two-player game, I usually only have to write new "position evaluator" code,
which generates a quantitative value that gives the relative position of one
player over the other for a particular board. Some games can benefit from a
database of opening moves that have been shown to be be superior (this
speeds up the computer's response).

Carl G.

Carl G., Apr 14, 2008