Jump to content

  • Log In with Google      Sign In   
  • Create Account


Wizuriel

Member Since 18 Jul 2012
Offline Last Active Nov 22 2012 05:21 PM

Posts I've Made

In Topic: Designing AI for Quoridor

12 November 2012 - 10:54 AM

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.

In Topic: Designing AI for Quoridor

06 September 2012 - 01:06 PM

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

In Topic: Designing AI for Quoridor

05 September 2012 - 11:42 PM

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

In Topic: Designing AI for Quoridor

05 September 2012 - 02:38 PM


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.


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?

In Topic: Designing AI for Quoridor

05 September 2012 - 12:46 PM

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?

PARTNERS