Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Shogi programming
2015-04-25, 08:12 PM
Post: #21
RE: Shogi programming
Well, perhaps it is because I have never programmed in an object-oriented language, but it seems to me there shouldn't be any reason at all to ever allocate any new object during search. When I play a game of Chess using 'woodware' I don't go running to the shop for buying new pieces when I want to make a move. I just reuse those already on the board.

But 40knps should be doable. Of course you would be likely to lose against a program that does 500knps (and is not GNU Shogi), but I suppose your goal isn't to make the strongest program in the world anyway. I also would not bother with SMP, if I were you, unless that is explicitly part of your assignment. Using 4 cores gives you at best an increase of a factor 4 in the nodes/sec, and probably not more than a factor 3 reduction of time-to-depth. In a perfectly working search that would result in a 100 Elo strength improvement. Working on your search (Queiescence, check extension) and evaluation (King Safety) could earn you 500-1000 Elo.
Find all posts by this user
Quote this message in a reply
2015-04-25, 08:19 PM (This post was last modified: 2015-04-25 08:23 PM by Dalv.)
Post: #22
RE: Shogi programming
Awesome, thank you for the explanation I already looked on king safety and I have an "advanced evaluation" which counts escape routes for king, free tiles around it, and safe infiltration points around the files adjacent (or same) as the king where the opponent could drop something and make an attack. My only fear is that if I plug this "advanced eval" my nodes/second will drop drastically. Well, my assignment was very vague when it came to what I should achieve, the only things were: implementation of search algorithm (like negamax, minimax or other) and improvements to search algorithm like alpha-beta on second semester of my dissertation project. So, in this this sense I think I'm way over what I am supposed to be working on.

Oh and the transpositon table doesn't seem to improve nodes/second, in the beginning of the game it looks rather like a slow down. Can you have a quick look on my code of using the entries ?
// query the transposition table (with collision check)
TranspositionTableEntry tte = table.querryTable(node.zobristKey);
// information found and depth check
if (tte != null && tte.basedOnDepthOf >= (maxDepth - depth)) {
switch (tte.type) {
// return SCORE node score
case HashTranspositionTable.SCORE: {
return tte.evaluationScore;
}
// maximise alpha
case HashTranspositionTable.ALPHA: {
alpha = Math.max(alpha, tte.evaluationScore);
break;
}
// minimise beta
case HashTranspositionTable.BETA: {
beta = Math.min(beta, tte.evaluationScore);
break;
}
}
if(alpha >= beta)
return alpha;
}
Find all posts by this user
Quote this message in a reply
2015-04-25, 09:02 PM
Post: #23
RE: Shogi programming
It is normal that TT slows you down. micro-Max 1.6, which has no TT, does ~6Mnps, while micro-Max 4.8, which has, does only ~1Mnps. The gain must come from that you need fewer nodes. Note that the most important effect of the TT is to provide the cut moves from the previous iteration.

It is hard for me to judge if your code is correct, because I don't know what case ALPHA and BETA are. If case ALPHA means the entry contained a lower bound it would look OK.
Find all posts by this user
Quote this message in a reply
2015-04-25, 09:04 PM (This post was last modified: 2015-04-25 09:06 PM by Dalv.)
Post: #24
RE: Shogi programming
(2015-04-25 09:02 PM)H.G.Muller Wrote:  It is normal that TT slows you down. micro-Max 1.6, which has no TT, does ~6Mnps, while micro-Max 4.8, which has, does only ~1Mnps. The gain must come from that you need fewer nodes. Note that the most important effect of the TT is to provide the cut moves from the previous iteration.

It is hard for me to judge if your code is correct, because I don't know what case ALPHA and BETA are. If case ALPHA means the entry contained a lower bound it would look OK.

Yes, sorry was planning to explain that well ALPHA is a LOW_FAIL node while BETA is a HIGH_FAIL node. And a LOW_FAIL node stores in evaluationScore the alpha that failed while the other one the beta that produced the cut-off.
Find all posts by this user
Quote this message in a reply
2015-04-25, 09:22 PM (This post was last modified: 2015-04-25 09:24 PM by H.G.Muller.)
Post: #25
RE: Shogi programming
Then you have it the wrong way around, not? After a beta cutoff the score S is a lower bound, which you store as BETA. So when originally you were looking for a score between alpha and beta, you can now look for a score between S and beta, because the TT tells you that in an equal or better search (depth-wise) the score was proven > S. That means you have to set alpha to max(alpha, S). But you set beta.
Find all posts by this user
Quote this message in a reply
2015-04-25, 10:10 PM (This post was last modified: 2015-04-25 10:20 PM by Dalv.)
Post: #26
RE: Shogi programming
Yes, indeed you are right now that I have checked online. Good good, that changes a lot. Ok so if you could I would like to really clear up what's in my head so: (alpha>= beta) => HIGH_FAIL which will store the beta value in the table. Now next time when I encounter this node (by transposition of moves and assuming the depth/collision verification is fine) it will take this beta that I have stored and try to use it as a lower bound (by comparing it with current alpha), at this point I get lost why do i want to use the beta stored before as my lower bound ? Can you explain please ? Thank you.
Find all posts by this user
Quote this message in a reply
2015-04-25, 11:22 PM (This post was last modified: 2015-04-25 11:23 PM by H.G.Muller.)
Post: #27
RE: Shogi programming
Alpha is the score of the best move found so far, in the current node or any earlier node along the path to the current node with the same side to move. Beta similarly is the best move the opponent has found so far (i.e. worst for the current side to move) along the current branch. So if we increase alpha because we found a new move that scored better than the old alpha, and that brings alpha >= beta, the current branch is no longer relevant: we have just proven it end worse for the opponent than an earlier side branch, so he will prefer that side branch. Thus we fail high in the current node, because the score is 'too good for us (the side to move)', and the move(s) leading to it are refuted. We won't waste time on searching more moves for us in this node, even though those moves could be even better than the one that just raised alpha. So we will never know how good the score really is in the current node; it is at least alpha, but there could be moves that are arbitrarily better. Alpha at that point is just a lower bound on the true score of the node.

So at a node where we failed high (alpha >= beta) the score >= alpha. So it is better to store alpha in the TT as beta; both are lower bounds to the true score, but alpha is a sharper lower bound.

If the next time you get to the same position you find in the TT (with sufficient depth to be relevant) a lower bound L >= current alpha, you know that in the previous search (that created that TT entry) you have found a move that scored >= L. When also L >= current beta, you can again immediately fail high, as the move that caused the beta cutoff before will certainly do that again now. But if L < current beta you have to search again, as the move that was good enough before to cause the cutoff isn't good enough now, as apparently beta was increased since your previous visit to this position. If the true best move would have score between L and beta, you would want to know exactly what it is (because then the current node would be on the PV). If it is above beta, you don't care how much above beta, because any move above beta refutes the move(s) leading to the current node. And you are not interested how much the score is below alpha, because you already know it isn't. So you set the search window to {L, beta}, the narrowest window that will tell you what you want to know. (And therefor will do it with minimal effort.)
Find all posts by this user
Quote this message in a reply
2015-04-26, 06:03 PM
Post: #28
RE: Shogi programming
Awesome, now it makes more sense, but I still find it quite hard to get my head around it. Thank you. Big Grin
Find all posts by this user
Quote this message in a reply
2015-04-30, 04:28 AM (This post was last modified: 2015-04-30 04:29 AM by Dalv.)
Post: #29
RE: Shogi programming
Hello Big Grin. Is there any way to figure out the weight of the different heuristics inside the evaluation function ? For pieces I've taken the values from "Computer Shogi" book. I couldn't find any other weights for let's say, king safety or controlled squares or distance to king ? Is there any research paper or way of knowing how much these should be worth ?
Find all posts by this user
Quote this message in a reply
2015-04-30, 06:16 AM (This post was last modified: 2015-04-30 06:20 AM by H.G.Muller.)
Post: #30
RE: Shogi programming
The only way to obtain such knowledge is empirically (i.e. play a few million games with different settings, and see which values work best), by statistical analysis of a large collection of games by human experts, extracting the knowledge through some advanced learning algorithm, or get the information from some open-source Shogi program that explicitly contains the parameters in its code.

None of these methods seems very practical, considering your dead-line.

Guessing how much King Safety is worth would also be problematic if you don't play the game yourself. In Shokidoki I started defining King Safety as being adjacent to a number of generals, close to the back rank, and behind a Pawn shield, and just tried a few very different weights. This did not work very well, and it was often checkmated when hugely ahead (like +40 on a scale where Rook=5). Then I included hefty penalties for having enemy pieces two steps away, even more so when they were on both sides. That worked much better. My impression now is that you can easily sacrifice a general to establish a 'foothold' of another general on one side near the opponent's King. But you would really have to ask a Shogi player.

I got the impression mobility is less important in Shogi than in Chess, because most pieces move by dropping them. You should prevent it from locking in its Bishop or Rook, though. For the steppers proximity to King or other material they can attack is very important. If you have a general that needs to make 3 steps to capture anything in the enemy camp, you might as well not have it at all. (In your own camp it can serve a defensive function.) If you cannot make a threat with your move, you will be dead before you can make a second move with that same piece...

Can you play automatic games against other opponents? That would be very helpful, to determine where you stand, and whether you make progress. If you run your computer overnight you can easily play a few hundred games with several versions (if you have a dual or quad core), to see which is better. Your first goal should be to consistently beat GNU Shogi. (And considering the time you have, that should be your final goal as well.)

P.S. I did not know there even was something like a Computer-Shogi book!
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


User(s) browsing this thread: 1 Guest(s)