# Designing AI for Quoridor

This topic is 1899 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

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.

##### Share on other sites

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.

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?

##### Share on other sites

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?

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.

##### 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?

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

##### 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:
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); int score = -negamax(b, -beta, -alpha, depth-1); b.undo_move(moves, old_pawn_pos); if (score > alpha) { alpha = score; if (score >= beta) break; } } return alpha; } 

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.

##### 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:
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

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

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

##### Share on other sites

Did you do any optimization to get those numbers?

No, nothing special. My more ordering is something like North, South, East, West, place horizontal walls, place vertical walls. Not really anything smart.

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

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

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

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