Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Shogi programming
2015-04-23, 06:17 PM (This post was last modified: 2015-04-23 06:24 PM by H.G.Muller.)
Post: #11
RE: Shogi programming
Shokidoki searches late moves at 5 ply (i.e. it calls Search(4) to search the reply) before it starts reducing. (So in a 6-ply node it would search them at 5 ply.) I remember the playing stregth was not very sensitive to this.

Most late moves are refuted by null move. Searching them at 4 ply would bring you directly in QS after null move, and further reduction would not save you anything. By searching them at 5 ply the null move brings you to d=1, which I considered somewhat safer, because then it at least searches check-drops (which QS does not). So you would not overlook late moves that threaten checkmate through a drop (e.g. attacking the square in front of the enemy King when you have a Gold in hand). Normally you would be below alpha when you get to searching late moves, and after the late move plus null move you would still be below alpha, so in the d=1 node the non-captures would probably be all futile (i.e. not raise the evaluation above alpha), so doing a d=1 search isn't really more expensive than a d=0 search.

After having searched killers the 10 non-captures with the best history score are not reduced. I did not really test if this was an optimum.
Find all posts by this user
Quote this message in a reply
2015-04-23, 07:56 PM
Post: #12
RE: Shogi programming
(2015-04-23 04:55 PM)Keith White Wrote:  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.
Actually I don't really know how strong Shokidoki would be on a human scale. Based on a single game against it a Dutch 2-kyu player told me he estimated it between 1 and 2 Dan.

It sounds that you played it a lot. What is your impression? Did you try handicap games? If so, how much handicapping would it need so you score about 50% against it?
Find all posts by this user
Quote this message in a reply
2015-04-23, 08:33 PM
Post: #13
RE: Shogi programming
(2015-04-23 06:17 PM)H.G.Muller Wrote:  Shokidoki searches late moves at 5 ply (i.e. it calls Search(4) to search the reply) before it starts reducing. (So in a 6-ply node it would search them at 5 ply.) I remember the playing stregth was not very sensitive to this.

Most late moves are refuted by null move. Searching them at 4 ply would bring you directly in QS after null move, and further reduction would not save you anything. By searching them at 5 ply the null move brings you to d=1, which I considered somewhat safer, because then it at least searches check-drops (which QS does not). So you would not overlook late moves that threaten checkmate through a drop (e.g. attacking the square in front of the enemy King when you have a Gold in hand). Normally you would be below alpha when you get to searching late moves, and after the late move plus null move you would still be below alpha, so in the d=1 node the non-captures would probably be all futile (i.e. not raise the evaluation above alpha), so doing a d=1 search isn't really more expensive than a d=0 search.

After having searched killers the 10 non-captures with the best history score are not reduced. I did not really test if this was an optimum.

Ugh, this is getting hard to understand, I just want my AI to stop being retarded and slow. Sad
Find all posts by this user
Quote this message in a reply
2015-04-23, 08:37 PM
Post: #14
RE: Shogi programming
Have you compared the depth it reaches with those of other simple engines, such as Shokidoki, TJshogi and Petit Shogi? How many nodes per second does your engine search?
Find all posts by this user
Quote this message in a reply
2015-04-23, 08:59 PM (This post was last modified: 2015-04-23 10:42 PM by Dalv.)
Post: #15
RE: Shogi programming
I don't know yet. I'm fighting right now to find out why at the beginning of a AI vs AI simulation everything looks fine and then it suddenly hangs or slows down A LOT. I think I'm having a Garbage Collector issue, I'm completely lost.
Find all posts by this user
Quote this message in a reply
2015-04-23, 10:43 PM
Post: #16
RE: Shogi programming
After I ran a profiler I concluded that a huge amount of time is spent in the move generation for some reason. I have to figure out a better way to do this.
Find all posts by this user
Quote this message in a reply
2015-04-24, 01:28 AM
Post: #17
RE: Shogi programming
Leaving any garbage to be collected is a mistake. What board representation do you use? Mailbox or bitboard?
Find all posts by this user
Quote this message in a reply
2015-04-24, 07:01 AM (This post was last modified: 2015-04-24 07:02 AM by Dalv.)
Post: #18
RE: Shogi programming
I'm using a two-dimensional array... with padding for minimizing number of comparisons when checking if a move is on the board. Bitboards were too much for me to implement for Shogi (it would have been easier for chess) and I haven't heard of mailbox until now. Again, I'm an university undergraduate and I have no prior knowledge in this so the stuff that I work with is not that advanced.
Find all posts by this user
Quote this message in a reply
2015-04-24, 02:13 PM
Post: #19
RE: Shogi programming
'Mailbox' is the general name for array representations, where each board square ir represented by an individually addressable memory cell.

Two-dimensional arrays are not recommended, because every access needs an address calculation to map the index pair on the one-dimensional memory. So usually one maps the board on a 1-dim array. This could explain why your move generator is a bit slower.

Speed should not be your primary objective now, though. (Perhaps unless you can gain orders of magnitude.)
Find all posts by this user
Quote this message in a reply
2015-04-25, 07:55 PM (This post was last modified: 2015-04-25 08:03 PM by Dalv.)
Post: #20
RE: Shogi programming
Ok, so after I made some initial adjustments and reduced object allocation rate by half (and I will reduce it even more hopefully), I'm getting way better results (with a single threaded search). Right now when I run 2 AI's against each other I get an initial rate of 65.000-70.000 nodes/second, which I think it's quite low but it is a start and it is way better than before, no more hanging and the slowdown over time by garbage accumulation is way slower (rate still drops to 40.000 nodes/s after a few minutes). This is because of Java (C++ or C# would have been a better choice but I have to work with what I have). As the profiler shows the most time lost is during move generation and check/check-mate/repetition check verifications. Another issue is that I don't know if history heuristics help or they just consume more time rather than helping, plus I'm planning to save the best move from previous iterations in the Transposition Table and give it top priority in next iteration when ordering the moves.

So as much as I can tell looking and nodes/second, history heuristics do help not by much, but by something (at least after a quick check).
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


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