std::sort with memory?

This is a discussion on std::sort with memory? within the C++ Programming forums, part of the General Programming Boards category; actually, the sorting is an optimization. The search needs to recurse down every possible move up to a certain depth. ...

  1. #16
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    actually, the sorting is an optimization. The search needs to recurse down every possible move up to a certain depth. However, the algorithm I am using, Alpha-beta (http://en.wikipedia.org/wiki/Alpha-beta_pruning), performs a lot better when the initial move ordering is good (good moves are searched before bad ones). Of course, I cannot just find a best move without doing the recursion, otherwise I wouldn't need the recursion in the first place. Sorting just makes it MORE LIKELY that good moves are placed in the front.

  2. #17
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by cyberfish View Post
    Thanks for your offer, really appreciated it. However, it is quite complicated as I am sorting a list of chess moves generated by my chess engine during its search in the order of likelihood to be a good move. The comparison operator does things like static exchange evaluation (count pieces from both sides attacking on the destination square to estimate material gain/lose), history heuristic (how many times has a move been proven useful in other parts of the search tree), and other minor criterias. Therefore, I think it would be too context-dependent for anyone to help just by looking at that function alone.

    Thanks
    That's alright. Even without getting code posted here I've prompted the release of more information we can use to help you. It sounds like you don't really need to fully sort the array afterall since presumably it will still succeed without being sorted, it will just take longer, am I correct?
    If so, you could instead periodically perform quick-sort-like passes similiar to how you the find k-smallest algorithm, that uses partitioning and only recurse on the lower half each time (assuming a near-even split). That would bring the lowest (best) value items to the front, and those almost as low (good) ones to close-ish to the front.
    However if you are actually repeatedly sorting this array then you may find that insertion sort beats introsort as it becomes O(n) in the nearly sorted case.
    Are duplicates possible, and is sorting being used to help identify them? If so then it's a different story again...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #18
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Couldn't you separate position evaluation from comparisons? The position evaluation (which would be done only once for each position) could yield a single number and you could compare based on that?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by cyberfish View Post
    Thanks for your offer, really appreciated it. However, it is quite complicated as I am sorting a list of chess moves generated by my chess engine during its search in the order of likelihood to be a good move. The comparison operator does things like static exchange evaluation (count pieces from both sides attacking on the destination square to estimate material gain/lose), history heuristic (how many times has a move been proven useful in other parts of the search tree), and other minor criterias. Therefore, I think it would be too context-dependent for anyone to help just by looking at that function alone.

    Thanks
    Make sure that if you do attempt to sort, that your sort criterion satisfies all of the conditions of a strict weak ordering. If it's a total preorder instead of a strict weak ordering, you can make use of the correspondence between the two to convert the one to the other (see my earlier link for details).

  5. #20
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    Couldn't you separate position evaluation from comparisons? The position evaluation (which would be done only once for each position) could yield a single number and you could compare based on that?
    That wouldn't be as accurate as the static evaluation function doesn't resolve captures. See my post above for what I am currently doing for move ordering. Many of those techniques cannot be used with static evaluation (history heuristic for example).

  6. #21
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    Make sure that if you do attempt to sort, that your sort criterion satisfies all of the conditions of a strict weak ordering. If it's a total preorder instead of a strict weak ordering, you can make use of the correspondence between the two to convert the one to the other (see my earlier link for details).
    Thanks for reminding me. Yes, it satisfies conditions of a strict weak ordering.

  7. #22
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    It sounds like you don't really need to fully sort the array afterall since presumably it will still succeed without being sorted, it will just take longer, am I correct?
    that is correct.

    If so, you could instead periodically perform quick-sort-like passes similiar to how you the find k-smallest algorithm, that uses partitioning and only recurse on the lower half each time (assuming a near-even split). That would bring the lowest (best) value items to the front, and those almost as low (good) ones to close-ish to the front.
    That sounds like a very interesting scheme. However, as the list of moves is usually small (~30), I am not sure if it's worth the complexity.

    Are duplicates possible, and is sorting being used to help identify them? If so then it's a different story again...
    duplicates are possible (in the sense that two moves are estimated to be equally as good), however, they are not identified by the sorting. The sorting does not have to be stable either.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. available memory from task manager
    By George2 in forum Tech Board
    Replies: 10
    Last Post: 01-18-2008, 01:32 AM
  2. Replies: 4
    Last Post: 01-13-2008, 01:14 AM
  3. Question regarding Memory Leak
    By clegs in forum C++ Programming
    Replies: 29
    Last Post: 12-07-2007, 12:57 AM
  4. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  5. Shared Memory - shmget questions
    By hendler in forum C Programming
    Replies: 1
    Last Post: 11-29-2005, 01:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21