Game algorithm

Game algorithm

[John]

I am doing a strategy game of "turned-base" type in Ada and I am in search
of an algorithm which builds a binary tree in wich all the leaves represents
all the possible moves for a player, at the given moment.

Could somebody direct me to a good link for this type of problem.

Thank you

Re: Game algorithm

[@ 2002-11-02 4:08 UTC (permalink / raw)]

On Thu, 31 Oct 2002 20:54:01 +0000, John wrote:

> I am doing a strategy game of "turned-base" type in Ada and I am in search
> of an algorithm which builds a binary tree in wich all the leaves represents
> all the possible moves for a player, at the given moment.

You'll have to be more specific than that.. if the tree is binary you can
only move forwards or backwards..

You want a tree with at least 4 children to each node.

Just store left, right, up, down 
lefts children would be left, right, up, down.
Which strikes me as odd since left then right would be totaly strange
thus you'd not want to check that...
gaah.. Im to tired I shouldn't even be answering...

> Could somebody direct me to a good link for this type of problem.

Use google and search for Minmax:
http://www.google.com/search?hl=en&lr=&ie=ISO-8859-1&q=Minmax+algorithm


> Thank you

Np

/M�rten

Re: Game algorithm

[John Stoneham]

"John" <celineg@look.ca> wrote in message
news:us3njhnp968eed@corp.supernews.com...
> I am doing a strategy game of "turned-base" type in Ada and I am in search
> of an algorithm which builds a binary tree in wich all the leaves
represents
> all the possible moves for a player, at the given moment.
>
> Could somebody direct me to a good link for this type of problem.
>
> Thank you
>

One of the "future" projects I am planning is a chess program in Ada.
Studying chess programming has been an on-and-off hobby of mine for several
years, and although you may not be usisng chess as your turn-based strategy
game, I believe the underlying principles will remain the same.

First look at www.cs.ualberta.ca/~tony/ICCA/anatomy.html for a very brief
description of how a computer chess program "thinks". There are two
algorithms enjoying dominance right now, one is called NegaScout, and the
other is MTD(f). C-code for NegaScout is available at
www.zib.de/reinefeld/nsc.html, and pseudo-code with an analysis for MTD(f)
is at www.cs.vu.nl/~aske/mtdf.html. A good links page for computer chess
programming is at www.xs4all.nl/~verhelst/chess/programming.html.

I also highly recommend the book Chess Skill In Man And Machine, which you
will probably need to find used somewhere like www.abebooks.com. Although
dated (it doesn't describe the more recent algorithms I mentioned above),
the basic descriptions of chess programs are very good. I still refer to it
when I want a "refresher".

Hope this helps.

--
John Stoneham
(to email, reverse the domain)

Re: Game algorithm

[@ 2002-11-04 15:49 UTC (permalink / raw)]

On Sat, 02 Nov 2002 08:25:23 +0000, John Stoneham wrote:

> "John" <celineg@look.ca> wrote in message
> news:us3njhnp968eed@corp.supernews.com...
>> I am doing a strategy game of "turned-base" type in Ada and I am in search
>> of an algorithm which builds a binary tree in wich all the leaves
> represents
>> all the possible moves for a player, at the given moment.
>>
>> Could somebody direct me to a good link for this type of problem.
>>
>> Thank you
>>
> 
> One of the "future" projects I am planning is a chess program in Ada.
> Studying chess programming has been an on-and-off hobby of mine for several
> years, and although you may not be usisng chess as your turn-based strategy
> game, I believe the underlying principles will remain the same.
> 

Me and my friends did a Chessprogram in Ada for a school project.
We used a weighted minmax algorithm for our two AI-clients.

It was a client server aproach since we needed networking for the project.
Our server could handle many games at the same time (tested with 4Gb RAM
so we didnt care). AI-clients ate through 60.000 boards before doing a
move. that's about 4 levels deep into the move tree.

I could probaly get you the whole source (client, server and ai).
We used a local package for drawing colors in Sun x-terms so
that probably wont work well.. there should be a quick 'n dirty version
of it too...

If you want it just say so...

<snip>
> Hope this helps.
> 
> --
> John Stoneham
> (to email, reverse the domain)

/M�rten

RE: Game algorithm

[Steven Deller]

Instead of chess, you might want to look into "Go".  The rules are
simpler than chess but the complexity is far greater (huge orders of
magnitude greater).  And it requires as much "feel" as "analysis".  Plus
there is a $1,000,000 prize waiting for the first program to beat a Pro
player at the lowest level.  So far, no program has even gotten close.
In fact, I am a good (not great) amateur player, and I have no problem
giving any Go program a handicap and still beating it without
difficulty.  If this piques your interest, check out:
   http://www.usgo.org

Regards,
Steve

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of John Stoneham
> Sent: Saturday, November 02, 2002 8:25 AM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: Game algorithm
> 
> 
> "John" <celineg@look.ca> wrote in message 
> news:us3njhnp968eed@corp.supernews.com...
> > I am doing a strategy game of "turned-base" type in Ada and I am in 
> > search of an algorithm which builds a binary tree in wich all the 
> > leaves
> represents
> > all the possible moves for a player, at the given moment.
> >
> > Could somebody direct me to a good link for this type of problem.
> >
> > Thank you
> >
> 
> One of the "future" projects I am planning is a chess program 
> in Ada. Studying chess programming has been an on-and-off 
> hobby of mine for several years, and although you may not be 
> usisng chess as your turn-based strategy game, I believe the 
> underlying principles will remain the same.
> 
> First look at www.cs.ualberta.ca/~tony/ICCA/anatomy.html for 
> a very brief description of how a computer chess program 
> "thinks". There are two algorithms enjoying dominance right 
> now, one is called NegaScout, and the other is MTD(f). C-code 
> for NegaScout is available at www.zib.de/reinefeld/nsc.html, 
> and pseudo-code with an analysis for MTD(f) is at 
www.cs.vu.nl/~aske/mtdf.html. A good links page for computer chess
programming is at www.xs4all.nl/~verhelst/chess/programming.html.

I also highly recommend the book Chess Skill In Man And Machine, which
you will probably need to find used somewhere like www.abebooks.com.
Although dated (it doesn't describe the more recent algorithms I
mentioned above), the basic descriptions of chess programs are very
good. I still refer to it when I want a "refresher".

Hope this helps.

--
John Stoneham
(to email, reverse the domain)


_______________________________________________
comp.lang.ada mailing list
comp.lang.ada@ada.eu.org
http://ada.eu.org/mailman/listinfo/comp.lang.ada