* Game algorithm @ 2002-11-01 4:54 John 2002-11-02 4:08 ` 2002-11-02 14:25 ` John Stoneham 0 siblings, 2 replies; 5+ messages in thread From: John @ 2002-11-01 4:54 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Game algorithm 2002-11-01 4:54 Game algorithm John @ 2002-11-02 4:08 ` 2002-11-02 14:25 ` John Stoneham 1 sibling, 0 replies; 5+ messages in thread From: @ 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Game algorithm 2002-11-01 4:54 Game algorithm John 2002-11-02 4:08 ` @ 2002-11-02 14:25 ` John Stoneham 2002-11-04 15:49 ` 2002-11-05 2:13 ` Steven Deller 1 sibling, 2 replies; 5+ messages in thread From: John Stoneham @ 2002-11-02 14:25 UTC (permalink / raw) "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) ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Game algorithm 2002-11-02 14:25 ` John Stoneham @ 2002-11-04 15:49 ` 2002-11-05 2:13 ` Steven Deller 1 sibling, 0 replies; 5+ messages in thread From: @ 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* RE: Game algorithm 2002-11-02 14:25 ` John Stoneham 2002-11-04 15:49 ` @ 2002-11-05 2:13 ` Steven Deller 1 sibling, 0 replies; 5+ messages in thread From: Steven Deller @ 2002-11-05 2:13 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2002-11-05 2:13 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2002-11-01 4:54 Game algorithm John 2002-11-02 4:08 ` 2002-11-02 14:25 ` John Stoneham 2002-11-04 15:49 ` 2002-11-05 2:13 ` Steven Deller
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox