• Advertisement

DeepButi

Member
  • Content count

    49
  • Joined

  • Last visited

Community Reputation

140 Neutral

About DeepButi

  • Rank
    Member
  1. Quote:Original post by alvaro Quote:Original post by DeepButi Stephane, the methods to recover Principal Variation work only if you are NOT using Transposition Tables. For most games, getting good performance requires TTs. I would be really glad to know if you find a method to get PV with TTs (I were not able to get them when working with alpha-beta) ... Well, I actually use transposition tables to recover the PV. The code that does that looks like this (literally): *** Source Snippet Removed *** mmm ... trying to understand your code: you get the best move for each position from the TT, do it and search again. Right? There is no security about the board position being on TT except if your TT is big enough to hold all your nodes. In my case, my worst test case examines 500 milion nodes and TT is not big enough to hold all of them. And in real games I've found far worst situations. Thanks anyway.
  2. Stephane, the methods to recover Principal Variation work only if you are NOT using Transposition Tables. For most games, getting good performance requires TTs. I would be really glad to know if you find a method to get PV with TTs (I were not able to get them when working with alpha-beta) ... and of course glad to test your game when it's finished :) Enric - Deep
  3. chess AI

    Take a look here. It's just one of hundreds of pages on the subject. Don't copy the board every time: DO the move and UNDO the move upon return. Hope it helps.
  4. AI for cards games?

    manolopm, I've some boots that play a four player trick-tacking card game. They play against human people with reasonable good results. I've been working on them for quite a long time (first ones, 10 years ago) ... I have been trying to use expectiminimax to improve its current euristics algorithms, but for now results are worse. They use minimax "after" game to analyze its own results. Wich game are you working on? (just a guess: mus? :) :) ) Send me a private if you are interested in details. Thanks
  5. Chess rules problem

    Quote:Original post by uckevin111 You must check the squares between the rook and the king to make sure they are not in check because you cannot castle through check (there are 2 or 3 squares, depending on which side the rook is on). No. The king allways moves two squares, no matter wich castle you do. Quote:Original post by uckevin111 You also must check the square the rook currently is on because you cannot move your king into check. So that would be a total of 4 or 5 squares, depending on which rook it is. No and no. The king never goes to where the rook is, no need to check it. Check oficial rules anywhere you like please. Allways 3 squares to verify: * actual king's position * square the king will cross * final square The fact that rook is actually under attack is irrelevant In long castle, the fact that the square adjacent to rook is under attack is irrelevant. For short castle: R..K -> .KR. -> NCCC (C means must be checked, N means it doesn't matter) For long castle: R...K -> ..KR. -> NNCCC Hope it helps
  6. The result is OK, but there is a mistake in the transpose (probably a typo). It should be 1 [1 -1 1 -1] 1 -1 1 -1 -1 = -1 1 -1 1 1 1 -1 1 -1 -1 -1 1 -1 1 Hope it helps
  7. Chess rules problem

    Quote:Original post by uckevin111 you would need to check 4 squares to make sure they are not in check, the square with the king, the two between the king and rook, and the square the rook is on Sorry but your rule is wrong. The only squares to be checked are the king actual position and squares the king will travel along including destinity, but NOT the rook actual position, neither in long castle the rook's adjacent square. Allways 3 squares, never 4 neither 5. Think128 code is wrong also checking unnecesary rook adjacent square in long castle. Quote:Original post by Araxon //swap function just swaps from 1 to 0 (CAN I DO IT WITH A BITWISE OPERATION?) yes you can, use XOR (exclusive OR): // To change it side^=1; // in your code if (board[tmpKingPos + horseMv[i]] == (8 + (side^1))) Hope it helps [Edited by - DeepButi on February 15, 2005 6:25:27 AM]
  8. LonelyStar, 1. As much as you can .... No joke, a match on TT saves a lot of time, so experiment with (primary number) sizes considering the amount of memory available. If it's going to run on an old PC and it needs to page to disk, probably it's too big. 2. Binary or hash, the problem will be the same: size. You cannot expect to store ALL positions (unless the game space is really small). Hash tables require no search (it depends on your replacing schema) so they should be quicker. Hope it helps
  9. How to Debug MTD(f)

    Quote:Original post by LonelyStar The AlphaBeta function never returns anything outside the boundings of alpha-beta, in case of MTD(f, this means that everytime either beta-1 or beta is returned. I know, that the firstguess should be s accurate as possible, but of course I can not know an absolute accurate MiniMax value at that time! But what if my first guess is off by about 500 (500 means a small capture for my evaluation function). Than, (assuming the correct value is 0) MTD(f) first uses the window: 499-500 than 498-499 e.t.c. So it takes 500 passes! On http://www.cs.vu.nl/~aske/mtdf.html it says, it should take about 5 to 15 passes. I seem to have totaly missed something! Can somebody explain a little to me? Thanks! You have a mistake here. Alpha-beta will return a value outside the bounds, so shortening the path to the correct value. Let's use a tree of only one leaf [totally] with a value greater than beta ... and a small pseudocode ... // ... for every move do ... { // do the move val=-NegaMax(-beta,-alpha); // undo move if (val>alpha) { alpha=val; // a leaf value > beta is obviously > alpha // alpha will take this greater value if (alpha>=beta) { break; // the loop broken } } } // ... end of loop return alpha; // and this gretaer value returned to main caller As you can easily see, the returned value will be greater than beta. Hope it helps [Edited by - DeepButi on February 11, 2005 3:55:35 AM]
  10. How to Debug MTD(f)

    Quote:Original post by LonelyStar ... Next Window: 0 to 1 Alpha beta returns 1 Next window 1 to 2 Alpha beta retusn 2 Next window 2 to 3 ... you get the Idea. I know, that the correct value at that point is 0! There should be an error in your alpha-beta code. With a window 0,1 and a correct value of 0 it should return 0, not 1. Try to make it as simple as possible, disable Transposition tables (a very common place for errors when MTD is used), make a log file with alpha,beta,value_before_cutting,value_after_cutting, disable even alpha-beta if possible (reduce to plain minimax) ... Hope it helps
  11. Board game with very high Branching Factor

    LonelyStar, give MTD(f) a try, probably faster than PVS. Sorting moves is essential, and prunning 'probably ilogical' moves could reduce drastically your branching factor (but 1700! ufff it's a lot :( ). Store best move on your Transposition Table, this should be tried first and previous moves at the same level skipped. Hope it helps
  12. Quote:Original post by ngabwI Would you mind terribly of I were to pick your brain again here re: this subject? Not at all, glad to help although I don't promise anything :) Quote:OK, if you promise not to laugh too loudly. :) I cannot see any reason to laugh. Being myself a table game pasionate, Klin Zha looks perfectly well. And yes, I remember Klingons ... I'm older than you probably think ;). Wich kind of minimax are you using? I have some issues about getting PV so perhaps we could share. Send me a private message if you prefer.
  13. I let it unfinished some time ago ... and unfinished tasks allways come back :) I'm currently using a NegaScout minimax to find value and bestmove of a certain position. To find the Principal variation I must do the move, call NegaScout, do the move, NegaScout ... and so on until the desired depth. In most cases this only adds 10%/15% of time, but sometimes it tooks as much as twice the original time to complete. I have been unable to get the whole P.V. in one call, and also unable to find any example of it despite a lot of googling. Has anyone done it? Any ideas? Thanks in advance
  14. ngabwI, testing threads is painfull. Testing minimax also. Testing minimax inside a thread can be a nightmare :). So, keep it simple, one problem at a time. Create a thread that just stops for a couple of seconds and test your boolean synchronizing method. If it does not work check pointer/structure/class. If you cannot find the problem, try a global boolean variable. Everybody will tell you globals are bad programming practice. They are. But we are just testing, and it will not hurt you :-). When it works, go step by step to the pointer/structure again. The minimax. Check for common data that you update in the main program while the thread uses it. If needed make a local copy using another set of boolean to stop the main process while making the local copy. Just an idea: suspend the thread when done. Main can resume the thread and check return value. If it was not suspended ... it has not finished :). (I don't know any method of testing for thread status without resuming it). Just curious: wich game are you working on? Hope it helps. [Edited by - DeepButi on January 19, 2005 3:47:05 AM]
  15. Interrelated genes

    OK, understood. Then probably Genetic approach is not a good way for my problem. Thanks
  • Advertisement