Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Shogi programming
2015-04-22, 11:28 PM
Post: #1
Shogi programming
I'm writing a Shogi program with a computer player. Due to the drop rule, when the computer player captures a few pieces, the branching factor increases a lot and the running time becomes infeasible. I haven't manage to find any research or information on drop reduction and my own selection is too slow and not "selective" enough (trying to remove drops that are not safe or not protected and don't have any use like defending or attacking). Does anyone know any heuristics that can be implemented with reasonable time complexity for selecting drops that are worth adding to the game tree ?
Find all posts by this user
Quote this message in a reply
2015-04-23, 02:06 AM
Post: #2
RE: Shogi programming
I don't know what your aim is, in terms of strength. Shogi is more difficult than Chess, due to the larger branching factor and the lack of quiet positions, complicating evaluation. So where writing a simple alpha-beta searcher with material evaluation and centralization already gives you a Chess program that is unbeatable for the average amateur, it takes much more effort to achieve the same in Shogi.

My own Shogi engine (Shokidoki) is only of very modest strength compared to top engines such as GPS Shogi and Bonanza. I am still reasonably happy with its performance, though, because it is a 'knowledgeless' engine which consists of just a ~60KB executable, while GPS Shogi and Bonanza need several hundred megabytes of knowledge, extracted from human games.

In Shokidoki I use late board moves by 1 ply, and drops (which are searched last) by 2 ply. As usual in LMR the reduction is revoked if the move scores above alpha. I don't even generate drops at depth <= 1, as these usually lose score (the dropped piece being worth more in hand), and should be treated as bad captures.

This does not apply to check-drops, these are generated at all depth > 0, and extended like other checking moves.

Shokidoki uses a normal quiescence search, searching only captures. It doesn't have a special tsume search. I understood from its author that Bonanza does a 3-ply tsume search in every QS node where it cannot stand pat.
Find all posts by this user
Quote this message in a reply
2015-04-23, 02:15 AM (This post was last modified: 2015-04-23 02:18 AM by Dalv.)
Post: #3
RE: Shogi programming
I am an undergraduate student and I have no prior AI or Shogi knowledge and I'm finding it really hard to make my own AI work and debug it and my time is VERY limited at this point. Now I have a multi-threaded negamax with transposition table, late move reduction, null move, iterative deepening and with basic move ordering: MVV-LVA + killer moves and history heuristic. I am aiming towards a modest strength player, but when I simulate a game between two AI's it always slows down heavily after a few captures are made. I'm having a really hard time finding any research that I can understand and checking if any of the procedures that I have implemented actually help or work properly. I was thinking that maybe by reducing the branching factor more by reducing drops I could get some speed improvement but I'm still having problems I guess. Thank you for your reply.
Find all posts by this user
Quote this message in a reply
2015-04-23, 02:34 AM (This post was last modified: 2015-04-23 02:35 AM by H.G.Muller.)
Post: #4
RE: Shogi programming
It sounds like you already have most of what is required in place. Just give non-checking drops the double reduction of other late moves in LMR, and you should have something comparable to Shokidoki. Don't forget to implement check extension, though; without that you would be really blind to getting tsume-mated. This is already a problem in Shokidoki; the SPEAR engine, for instance, seems to see mates far earlier than Shokidoki. (SPEAR sometimes reports mate-in-25, while Shokidoki must already be lucky to see the same mate when it is 11 moves away.) SPEAR must spend a lot of time on a dedicated tsume search. The price of this of course is that it searches other moves less deeply, so when there is no mate to be found, it consistently loses material to Shokidoki, so that the latter is still able to win ~20% of the games against SPEAR.

That it takes more time to reach the same depth when the position gets more complex is natural. You must just accept that you cannot search as deep then.
Find all posts by this user
Quote this message in a reply
2015-04-23, 02:38 AM (This post was last modified: 2015-04-23 02:40 AM by Dalv.)
Post: #5
RE: Shogi programming
Thank you very much for your advice and for your time. Another issue, if I may ask is about killer heuristic and history heuristic. So, do the data structure containing the 2 killer moves and the piece-to table for the history heuristic values have to be reset after the best move is found ? Or they should store like global information that is used through all searches during a game ?
Find all posts by this user
Quote this message in a reply
2015-04-23, 02:48 AM
Post: #6
RE: Shogi programming
The history table should be global to the entire search. It is intended to collect moves from all over the tree that sometimes do any good, and thus must not be totally crazy, from the moves that are always useless. A very course mechanism, but better than just randomly ordering the non-captures. As the position usually does not change that much in 2 ply, even the information from the previous search will be useful, and can be kept. So rather than clearing the table, you can divide all values by 2 or 4 before every search. That will make it 'forget' moves that are no good anymore quickly enough.

The killer array is for communicating the best move of a node to its direct sibblings. So the entry belonging to the current level should not be cleared, but you can clear the entries belonging to the next level when you start searching a node (so that you would not propagate information from its 'cousin' nodes). This is not essential, though.
Find all posts by this user
Quote this message in a reply
2015-04-23, 03:00 AM (This post was last modified: 2015-04-23 03:43 AM by Dalv.)
Post: #7
RE: Shogi programming
Great explanations. Thank you again so much. If you don't mind I will be asking more later on if I encounter other conceptual issues. Regarding the extension search (quiescent search), my engine is slow (and probably buggy as it is) so for now I will be ignoring any search extensions. The only issue is that I have 15 days left to fix everything. Sad

Ah, another issue that I have discovered is regarding the null move reduction technique. So I'm not allowing a null move reduction (by 2) when the player is in check or the previous move was a null move. The problem is even if it speeds up the search A LOT, in the beginning of the game it always cuts-off everything (possibly due to very primitive evaluation function that takes in account only material, distance to opponent king and check) and the computer player is rubbish so to say, do you use any extra condition to regulate when the null move technique is applied ? Before, I used to allow a null move only if the current material score was greater than beta as in the Madchess program (for western chess), it seemed to fix the rubbish play in the beginning of the game but it slowed down the search a lot.
Find all posts by this user
Quote this message in a reply
2015-04-23, 04:07 AM (This post was last modified: 2015-04-23 04:18 AM by H.G.Muller.)
Post: #8
RE: Shogi programming
This sounds like a bug. Applying null move when the score is below beta should not make the engine overlook more. It should not do much at all, other than blowing up the tree size. Because doing nothing is almost never a good plan for improving your position. And when you already are below beta, you will need an improvement to get above beta. The normal situation is that a null move will not improve the evaluation compared to what it is before the null move, as you give away initiative. So a null move from a position that has an evaluation below beta should normally return a score also below beta, and thus should not lead to pruning the real moves. (Only in the rare cases where you have a fork or skewer you can afford to wait and still gain material later.) That means that searching the null move has basically be a waste of time. This is why most programs don't do it when the evaluation is below beta.

BTW, Quiescence Search should be your first priority. It is far more important than null move or LMR. The latter are just techniques to reach the same depth faster (searching fewer nodes), without much impact on accuracy. But without QS the search will just return nonsense. And it doesn't matter much whether you return the nonsense faster. You should look upon QS as a convergence acelerating method, which makes an otherwise diverging series converge. Like in mathematics summing the geometric series 1, -1, 1, -1 will never get you anywhere, no matter how many terms you take, while the trick of counting the last term of the partial sums only with weight 0.5 already gives you a sensible result when you consider only the first term.
Find all posts by this user
Quote this message in a reply
2015-04-23, 04:55 PM
Post: #9
RE: Shogi programming
(2015-04-23 02:06 AM)H.G.Muller Wrote:  My own Shogi engine (Shokidoki) is only of very modest strength compared to top engines such as GPS Shogi and Bonanza. I am still reasonably happy with its performance, though, because it is a 'knowledgeless' engine which consists of just a ~60KB executable, while GPS Shogi and Bonanza need several hundred megabytes of knowledge, extracted from human games.

Yet it is still strong enough to pick you up, wipe the floor with you and stick you back in the mop bucket with a bad hairdo.

I have beaten it I think once and nearly (by one move to go) maybe twice.
It is stronger than you would imagine based on HGM's comments so be under no illusion. In a quick game, playing at the pace many do nowadays, it'll eat you up. I've never come close in any game where I haven't taken the time to really look.

I suppose that counts for anything really. Anyway, I have thought about using GPS to analyse new games between myself and lesser engine and then, with the help of what should be 'better moves' I can learn to beat 'lesser engines' one at a time.

It's a plan, nothing more. The idea of using an engine to learn smacks of desperation but we aren't all graced with the spirit of Habu.
Find all posts by this user
Quote this message in a reply
2015-04-23, 05:45 PM
Post: #10
RE: Shogi programming
Thank's a lot about your observation of my null move being bugged. I did find the bug (took me ages though !!!). Anyways, how many moves do you search before allowing a LMR ? Right now I search 4 moves and then allow LMR (plus the other check and horizon constraints).
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


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