• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
lxy

Negamax Algorithm (I am a beginner to this)

4 posts in this topic

I am new to game programming.And I know Artificial Intelligence Algorithm is the most important things in developing games. As everyone knows, Nagemax is the basic things in AI. It was found by Knuth and Moore. But I can't understand it clearly. Can anyone recommand some books or papers to me that help me understand it. And the example in internet is obscurity. Can anyone know a example that clearly explain it . Thanks very much
0

Share this post


Link to post
Share on other sites
I don't know any books but I'll give it a go...

A Negamax algorithm is a way of selecting the best possible move/decision from a range of all possible decisions. The algorithm trys to "look into the future" to predict what the opponent is going to do. From all the possible outcomes, the algorithm selects the move that will give it the greatest advantage while giving the opponent the greatest DISadvantage, hence the term Negamax/Minimax.

There are a couple of things that are important to remember:

1) This algorithm only works for a turn-based game that has a finite number of possible decisions (pokemon, blackjack, connect 4, naughts and crosses etc)
2) The algorithm always assumes that the opponent will choose the best possible move (no human error).
3) Before the algorithm is started, you have to decide how far into the future you're going to look. This is quite important because the number of calculations that are required to look one step further into the future increases exponentially. If you look too far into the future the algorithm is going to slow down to a crawl. Too near in the future and the algorithm doesn't make intellegent decisions.
4) You have to create some sort of scoring algorithm to determine how "good" any situation is for the player. This can be as simple as "Have I won?" (for things like naughts and crosses) or you can use some sort of points system (for things like connect-4 or chess ).

After you've worked all of this out, you can begin to evaluate the moves. This is done in pairs of plies and replies. A ply is a set of every single possible move that can occur in your turn (taking into account every move that could have occured last turn as well). A reply is the same thing, but for your opponent. You have to evaluate each situation in its final form, then work backwards from there to find the correct move (this makes the algorithm recursive, as you'll see on the wiki page). with each reply you choose the move that gives you the greatest negative effect (the opponents best move) and with each ply you choose the least negative effect (your best move considering that the opponent will choose the best move for them).

That's a really high-level overview of the algorithm (I really hope I haven't got anything wrong) and it doesn't go into the technical implementation, but hopefully you've gained something from this post.

Wikipedia has a really good gif that goes through the algorithm step by step.
http://en.wikipedia.org/wiki/File:Plain_Negamax.gif
0

Share this post


Link to post
Share on other sites
One of the best resources about chess programming is Bruce Moreland's programming pages. He stopped hosting them a few years ago, but they are still accessible through www.archive.org.

If you read through his items 1.A, 1.B and 1.C you'll probably understand enough to implement NegaMax with alpha-beta pruning.

By the way, almost everything in the original post is wrong: Knuth and Moore didn't actually invent this algorithm, but they did write a clear paper about it in 1975. Also, the "basic thing in AI" is maximization of expected utility, of which alpha-beta is a special case. And the most important thing in developing games is determining what the players do (the gameplay), not AI. There are some good games that don't have AI at all (e.g., Tetris).

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0