Game design : Making computer play

[v4vijayakumar]

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.

[Marc 'BlackJack' Rintsch]

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

[Richard Heathfield]

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
want a better answer, ask a better question.

Are there any formal ways to _teach_ computer, to choose best possible
move?

That's a better question. The obvious ways are DFS, BFS, and databases.

For example, take backgammon, and computer goes first. You roll the PRNGs
and get 6, 1. You (the computer) have never played this game before, so
you don't have a database of good moves. Your legal moves are:

24,18 and 24,23
24,18 and 8,7
24,18 and 6,5
13,7 and 24,23
13,7 and 8,7
13,7 and 6,5

Of these, which is the best? DFS (Depth-First Search) and BFS
(Breadth-First Search) can help you answer that question. What you do is
define an evaluation function for the position, based on things like how
many blots, how many on the bar, whether you have a prime, and so on. Then
you *play the game* in simulation, as deeply as you can (which won't be
very deep, actually), evaluating all the time. Once you've found the
position that does you most good (or least harm) no matter what die-rolls
the opponent may get and no matter how skilfully he or she plays, you know
what to get your computer player to do next.

If you're clever, you'll keep the solution tree around, destroying only the
bits of it that won't ever be used again - to save processing time on your
next turn.

If you're really clever, you'll write a lot of this information down in a
file, a sort of opening "book", so that you don't have to calculate
everything from scratch every time. For example, in the above situation,
there is no need to calculate, because it's a no-brainer: 13,7 and 8,7 is
far and away the best move.

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

comp.programming is probably where you want to be, at least to start off
with.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[xakee]

On Apr 14, 12:13*pm, v4vijayakumar <[e-mail]>
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.

[v4vijayakumar]

On Apr 14, 12:35 pm, Richard Heathfield <[e-mail]:

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
want a better answer, ask a better question.

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.

[Richard Heathfield]

[comp.programming added, and followups set to that group]

v4vijayakumar said:

On Apr 14, 12:35 pm, Richard Heathfield <[e-mail]:

>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 want a better answer, ask a better question.

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.

comp.programming would be a better group.

I've found a picture of the board, but I can't find the rules anywhere,
without which the task is impossible. Can you tell us what they are?

If you reply, I suggest you do so in comp.programming.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Willem]

v4vijayakumar wrote:
) On Apr 14, 12:35 pm, Richard Heathfield <[e-mail]:
)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
)want a better answer, ask a better question.
)
) 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

[v4vijayakumar]

On Apr 14, 1:00 pm, v4vijayakumar <[e-mail]>
wrote:
....

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

The game is here,

http://v4vijayakumar.googlepages.com...nd-tigers.html

[skanemupp]

On 14 Apr, 09:13, v4vijayakumar <[e-mail]>
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

[Richard Heathfield]

sk*******@yahoo.se said:

On 14 Apr, 09:13, v4vijayakumar <[e-mail]>
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.

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

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.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Willem]

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

[dgates]

On Mon, 14 Apr 2008 12:13:20 +0000 (UTC), Willem <wi****@stack.nl>
wrote:

>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.

v4 gave us a link to a page that not only lists the rules, but lets
you try them out:

http://v4vijayakumar.googlepages.com...nd-tigers.html

Seems like a fun quickie game to play with some coins on a piece of
paper. I like the asymmetrical goals and the quick setup.

[John Bailey]

On Mon, 14 Apr 2008 00:13:56 -0700 (PDT), v4vijayakumar
<vi******************@gmail.comwrote:

>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.

Sargon: A Computer Chess Program (Paperback)
by Dan Spracklen (Author), Kathe Spracklen (Author)
Search Amazon with that title. Its available for under $20.

The Spracklen's book provides a concrete structure and model for a
computer program which attempts to look ahead, evaluating alternative
moves. Unlike AI texts which obfuscate through abstraction, theirs is
quite clear even if you don't know Z80 assembly language. By reading
their book (studying it might be a better phrase) I came to understand
the complexity and immensity of the task.

Good luck.

John

[Carl G.]

"Marc 'BlackJack' Rintsch" <bj****@gmx.netwrote in message
news:66*************@mid.uni-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%2A

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.

[Ed Murphy]

v4vijayakumar wrote:

On Apr 14, 1:00 pm, v4vijayakumar <[e-mail]>
wrote:
....

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

The game is here,

http://v4vijayakumar.googlepages.com...nd-tigers.html

The list of valid moves is incomprehensible to humans without
actually drawing all the possible moves. Without an exhaustive
check for validity, I think the following is an accurate summary:

* Treat the board as a 5x6 grid with the corners removed and
the top 4 cells merged.

* Any piece can move one space up, down, left, or right.

* A tiger can eat a goat by jumping over it, thereby moving
two spaces up, down, left, or right.