• 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
Wizuriel

Designing AI for Quoridor

35 posts in this topic

[quote name='IADaveMark' timestamp='1346858764' post='4976850']
Obviously, the longer you can make his path without affecting your own, the better. This is where A* comes in. You want to know which of your potential wall placements will do the most damage without being illegal or making your own situation markedly worse. That is the fitness of your decision.
[/quote]

Yes, that's effectively a depth-1 search in my program. It's already an interesting opponent, but depth-2 is probably the minimum level at which it is not very easy to beat.

I haven't profiled my program, but I think you are right: Having a really fast A* implementation will probably speed things up a lot.

By the way, the large branching factor is an issue, but it's not a deal breaker for alphabeta. In games like go the dealbreaker is that there is no obvious evaluation function to start with. Luckily, the difference in distance to goal between the players serves that role nicely.
1

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1346856164' post='4976835']
Make sure you are not doing any dynamic memory allocation at all. I don't know how feasible this is with languages like C# and Java, but in C or C++ it's fairly straight forward.
[/quote]

Right now everything I do used dynamic memory allocation and truth be told my classes aren't memory efficient (especially for debugging I like tracking some extra information to make sure stuff is working), but would that really be the difference between you're alpha beta pruning taking seconds and mine taking hours?
0

Share this post


Link to post
Share on other sites
[quote name='Wizuriel' timestamp='1346870816' post='4976938']
Right now everything I do used dynamic memory allocation and truth be told my classes aren't memory efficient (especially for debugging I like tracking some extra information to make sure stuff is working), but would that really be the difference between you're alpha beta pruning taking seconds and mine taking hours?
[/quote]

Of course, you might have a bug somewhere. But needless memory allocation can easily result in a factor of 100 slowdown. The problem is that everything in an alpha-beta searcher is part of the "inner loop", in some sense. Keeping an eye on performance is very important in this context.

I'll add some node counts to my code so we can compare mine and yours and see if I am just getting more nodes per second. It could be that I am also visiting many fewer nodes than you are, which would probably indicate a problem with your alpha-beta implementation.
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1346871685' post='4976942']
[quote name='Wizuriel' timestamp='1346870816' post='4976938']
Right now everything I do used dynamic memory allocation and truth be told my classes aren't memory efficient (especially for debugging I like tracking some extra information to make sure stuff is working), but would that really be the difference between you're alpha beta pruning taking seconds and mine taking hours?
[/quote]

Of course, you might have a bug somewhere. But needless memory allocation can easily result in a factor of 100 slowdown. The problem is that everything in an alpha-beta searcher is part of the "inner loop", in some sense. Keeping an eye on performance is very important in this context.

I'll add some node counts to my code so we can compare mine and yours and see if I am just getting more nodes per second. It could be that I am also visiting many fewer nodes than you are, which would probably indicate a problem with your alpha-beta implementation.
[/quote]

Would be appreciated.

Going off my code using standard board and players starting in the middle
P1) initial position has 131 children. Assume player 1 moves
P2) initial position (based off player 1 moving) has 131 children
P1) First child from the 131 children returns 132 more children
P2) P2's first child also has 132 children

This first branch assumes both players are just moving directly towards their desired goal

So yeah I should find a way that you can't move backwards for the children (by backwards I mean to a position already done by one of the earlier children). Easiest way I can think of would be to have each view have a link back to it's parents and make sure the new view is not equal to any of the parents. Would the extra memory usage be worth the less nodes to view? Edited by Wizuriel
0

Share this post


Link to post
Share on other sites
One important thing that helps performance is that I don't make any copies of the board. There is a single board (I pass references to it around, but it could actually be made global), and the search function makes moves on it and then undoes them carefully. Here's my actual search function:
[code]int negamax(Board &b, int alpha, int beta, int depth) {
int current_score = b.get_score();
if (depth <= 0 || abs(current_score) >= 400000)
return current_score;

Move moves[132];
int n_moves = b.generate_moves(moves);
int old_pawn_pos = b.get_pawn_pos(); // I need to remember where the pawn for the side to move was, so I can return it there if I move it.
for (int i=0; i<n_moves; ++i) {
b.make_move(moves[i]);
int score = -negamax(b, -beta, -alpha, depth-1);
b.undo_move(moves[i], old_pawn_pos);
if (score > alpha) {
alpha = score;
if (score >= beta)
break;
}
}
return alpha;
}
[/code]

Once I add move sorting and transposition tables it probably won't be as readable.

As you see, the array of moves is on the stack (moves are small) and I don't need to do any allocation anywhere.
0

Share this post


Link to post
Share on other sites
This is some output from my program when searching from the starting position. It might help you get an idea of whether your search is looking at too many positions, and how much slower than mine it is. The node count is actually how many times Board::make_move has been called since the search started. I search depth 1, 2, 3... until I run out of time. This is running on my laptop:
[code]New best move: side=0 depth=1 move=25 score=12 nodes=1 time=0.00011301 nps=8848.74
Depth complete: side=0 depth=1 move= 25 score=12 nodes=131 time=0.00980401 nps=13361.9
New best move: side=0 depth=2 move=25 score=10 nodes=263 time=0.0124841 nps=21066.8
Depth complete: side=0 depth=2 move= 25 score=10 nodes=524 time=0.018996 nps=27584.8
New best move: side=0 depth=3 move=25 score=10 nodes=1046 time=0.0243661 nps=42928.4
Depth complete: side=0 depth=3 move= 25 score=10 nodes=17980 time=0.134464 nps=133716
New best move: side=0 depth=4 move=25 score=8 nodes=51817 time=0.318163 nps=162863
Depth complete: side=0 depth=4 move= 25 score=8 nodes=86064 time=0.521238 nps=165115
New best move: side=0 depth=5 move=25 score=12 nodes=200464 time=1.14466 nps=175130
Depth complete: side=0 depth=5 move= 25 score=12 nodes=2310718 time=13.1338 nps=175937
New best move: side=0 depth=6 move=25 score=8 nodes=6715517 time=37.9794 nps=176820
Depth complete: side=0 depth=6 move= 25 score=8 nodes=11346684 time=65.374 nps=173566[/code]

So I am searching around 170K nodes per second, and finishing a depth-4 search took a total of 86K nodes.
0

Share this post


Link to post
Share on other sites
Did you do any optimization to get those numbers?

My depth 2 on the starting position is exploring about 17k nodes taking about 46 seconds to do so :S Edited by Wizuriel
0

Share this post


Link to post
Share on other sites
[quote name='Wizuriel' timestamp='1346910152' post='4977079']
Did you do any optimization to get those numbers?[/quote]
No, nothing special. My more ordering is something like North, South, East, West, place horizontal walls, place vertical walls. Not really anything smart.

[quote]My depth 2 on the starting position is exploring about 17k nodes taking about 46 seconds to do so :S[/quote]
17k nodes is essentially the full size of the tree, which means that your alpha-beta search is not producing any beta cuts. That doesn't seem right. Regarding the nodes per second (where you are getting something like a slowdown by a factor of 500), it's a matter of picking the right language (I would argue you should use something low-levelish like C or C++ for this task) and understanding a couple of things about what operations are cheap and which ones are expensive.

By the way, my pathfinding function still needs improvement, and I expect to get more nodes per second that way. Transposition tables and some move-ordering heuristics should allow me to search deeper for a given number of nodes. Edited by alvaro
0

Share this post


Link to post
Share on other sites
edit: wish I could delete this post. Going try and re do the search by scratch and hope I get a better result this time Edited by Wizuriel
0

Share this post


Link to post
Share on other sites
I'm glad to see that I was looking in roughly the right directions, memory allocation and inner loop speed. It's a shame that the pruning isn't working right, I must admit that's not my area of expertise. Overall don't get down that your first cut didn't go so well. Every coder makes mistakes. A friend once decided to write his own sort. Unfortunately he forgot what with handy things like indexer operators in C# that the underlying datatype was a linked list. His solution ended up being O(n^4) and choked on around 10,000 items. Focus on the items to take away from this: frequent memory allocation isn't cheap, everything in the inner loop counts, check that your pruning is working correctly, and learn more about profiling.
0

Share this post


Link to post
Share on other sites
Sorry for kind of necroing this, but I just managed to get negamax working (correctly) and while my program is still slow (3-5min a turn), it's still a huge improvement over my 1hour initial time.

Still trying to cut back on my A* searches and find general improvements, but a working copy has been put up at: http://thetaraday.somee.com/Games?id=7 and wanted to thank everyone here for the help.
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