Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Shogi programming
2015-04-30, 06:27 AM (This post was last modified: 2015-04-30 06:50 AM by Dalv.)
Post: #31
RE: Shogi programming
Ugh, thank you for the help, but I think it might be too late for that. No, I cannot play automatic games against other opponents, I haven't even looked into that yet. I'm pretty sure my AI is quite weak and I probably don't have the time to do much more work due to travelling and examination period. I just hope whatever I've done it will be enough for an undergraduate project. Is GNU Shogi a program in which AI's can be plugged in ?

I might be able next week to look into GNU Shogi but I don't think that is enough time considering that I have to make the software look "finished" and finish of my dissertation until then. Anyways, "Computer Shogi" is more like a section of an AI book I think or journal (not sure). The section can be found at: http://citeseerx.ist.psu.edu/viewdoc/dow...1&type=pdf

Out of curiosity, can you estimate how long did it take to make your Shogi engine ? Was it work related or a hobby ?
Find all posts by this user
Quote this message in a reply
2015-04-30, 04:14 PM (This post was last modified: 2015-04-30 04:19 PM by H.G.Muller.)
Post: #32
RE: Shogi programming
GNU Shogi is an AI that can be plugged into WinBoard/XBoard (or older versions into xShogi).

Making Shokidoki was a hobby project. In 2010 the ICGA Computer Olympiad was in Kanazawa, Japan, and I wanted to go there anyway to participate in the Chinese Chess with my engine HaQiKi D. So I figured that if there ever was a time to write a Shogi AI, this would be it. If the Olympiad is not in Japan only the strongest programs in the world bother to attend, and an amateur would never stand a chance. But I figured that inside Japan other amateur engines would participate too. So two month before the Olympiad I started making a derivative of HaQiKi D, converting it to play Shogi. My aim was to win at least one game in the Olympiad.

This I managed: there were 9 Shogi contestants in 2010, and I actually beat two of them. (But one was an experimental engine without search, and it did not even protect or move away his pieces when you attacked them, so beating that was not really an achievement.) The surprise, however, was that the Olympiad also had a mini-Shogi tournament, and (after a rather trivial program change I made the evening before it in my hotel, to reduce the board size to 5x5) Shokidoki turned out to be very good at that, and even won the silver medal (after some tweaking of the piece values during the lunch break).

So the short answer is: it took me two months to create a Shogi program that was able to win games. But as I was retired I could work full time on it. And I only had to create the AI, as the GUI (WinBoard) already supported Shogi. And I already had a working AI to start from.
Find all posts by this user
Quote this message in a reply
2015-04-30, 04:34 PM
Post: #33
RE: Shogi programming
Well, congratulations for your achievements. Its a nice hobby and I was considering continuing with Shogi in my spare time. I have so much to learn xD.
Find all posts by this user
Quote this message in a reply
2015-04-30, 07:53 PM (This post was last modified: 2015-04-30 11:33 PM by Dalv.)
Post: #34
RE: Shogi programming
So, I was going through TT again and I found some things that didn't make sense anymore for me. I simplified the algorithm so its readable, can you tell me if you see anything wrong with it ?

public double negamax(GameState node, int depth, double alpha, double beta) {

// rate for the player that has to move next
int playerToRateFor = node.turn;
int type = HashTranspositionTable.LOW_FAIL;
double val, score;

// query transposition table (collision check included)
TranspositionTableEntry tte = table.querryTable(node.zobristKey);
// information found and depth check
if (tte != null && tte.depth >= depth) {

switch (tte.type) {
// return SCORE node score (EXACT value)
case HashTranspositionTable.SCORE: {
return tte.evaluationScore;
}
// low fail => upper bound
case HashTranspositionTable.LOW_FAIL: {
beta = Math.min(beta, tte.evaluationScore);
break;
}
// high fail => lower bound
case HashTranspositionTable.HIGH_FAIL: {
alpha = Math.max(alpha, tte.evaluationScore);
break;
}
}
if (alpha >= beta)
return tte.evaluationScore;
}


// check for maximum depth reached or terminal node
//rate and store in table
if (depth == 0 || node.isLeaf()) {// end of search
score = rate(node, playerToRateFor);
table.addEntry(node.zobristKey, depth, score,
HashTranspositionTable.SCORE);
return score;
}

if (null move conditions) {
// apply a null move
makeNullMove(node);
val = -negamax(node, depth - 1 - JUMP, -beta, -beta + 1);
unmakeNullMove(node);
// cut-off if high fail and store in table
if (val >= beta) {
table.addEntry(node.zobristKey, depth, val, HashTranspositionTable.HIGH_FAIL);
return beta;
}
}

Move move, bestTTMove = null;
double bestValue = Integer.MIN_VALUE;
// generate and order next possible moves
List children = next ordered moves;
int chSize = children.size();
for (int i = 0; i < chSize; i++) {
move = children.get(i);

makeMove(node, move);
val = -negamax(node, depth - 1, -beta, -alpha);
unmakeMove(node, move);

bestValue = Math.max(bestValue,val);

// check for fail low
if (val > alpha) {
// better alpha found => score node
type = HashTranspositionTable.SCORE;
alpha = val;
bestTTMove = move;
}

// check for fail high
if (alpha >= beta) {
table.addEntry(node.zobristKey, depth, bestValue,
HashTranspositionTable.HIGH_FAIL,);
return beta;
}

}

// store in table
table.addEntry(node.zobristKey, depth, bestValue, type, bestTTmove);

return bestValue;
}


Obviously if there exists a previous entry, it is overwritten only if the depth passed in addEntry(...,depth,...) is greater or equal to the depth stored in the entry object.
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


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