An Introduction to OSL

Size: px

Start display at page:

Download "An Introduction to OSL"

ちとらしげまつ
4 years ago
Views:

1 .... An Introduction to OSL TeamGPS CSA (TeamGPS) An Introduction to OSL CSA 1 / 45

2 : (TeamGPS) An Introduction to OSL CSA 2 / 45

3 Disclaimer: OSL Bonanza Crafty (pruning/cut, ) bitboard OSL GPS (i.e., ) osl::rating::standardfeatureset gps normal osl::eval::progresseval gps l osl::eval::experimental::testeval!? (TeamGPS) An Introduction to OSL CSA 3 / 45

4 GPS OSL GPS : GPS game programing seminar ( ) , , , 1 6, ( ) : Bonanza! 0 OSL ( ) Microsoft Windows (TeamGPS) An Introduction to OSL CSA 4 / 45

5 OSL (Open Shogi Library) GPS BSD osl-for-csa OSL CSA CSA BSD GPS OSL GPL ( ) (TeamGPS) An Introduction to OSL CSA 5 / 45

6 ( ) osl-for-csa gpsshogi/index.php?osl%2fosl-for-csa OSL/GPSShogi : http: //gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi/ : u-tokyo.ac.jp/cgi-bin/viewvc.cgi/ (Download GNU tarball ) : (TeamGPS) An Introduction to OSL CSA 6 / 45

7 A: : : ( ) B: C: (c.f. ) (e.g., alphabeta2.cc, alphabeta3.cc) (TeamGPS) An Introduction to OSL CSA 7 / 45

8 : osl/sample/random play.cc NumEffectState state; // std::string line; while (true) { MoveVector moves; // LegalMoves::generate(state, moves); // if (moves.empty()) Move my move = moves[random()]; // ApplyMoveOfTurn::doMove(state, my move); // std::getline(std::cin, line); Move op move=csa::strtomove(line, state); // ApplyMoveOfTurn::doMove(state, op move); // } (TeamGPS) An Introduction to OSL CSA 8 / 45

9 C++ a.b() a::b() a b a::b() namespace a b C++ C++ 3 (TeamGPS) An Introduction to OSL CSA 9 / 45

10 : template (1) template (2) template.. : (TeamGPS) An Introduction to OSL CSA 10 / 45

11 : : e.g., : C++ template e.g., boost e.g., cppunit, boost::test, gtest (TeamGPS) An Introduction to OSL CSA 11 / 45

12 (1) template ( )...3 (TeamGPS) An Introduction to OSL CSA 12 / 45

13 (turn, state, kingx, kingy) { // y = (turn == )? kingy-2 : kingy+2; if ((kingx, y) ) { promote = (turn == )? y<=4 : y >= 6; if (promote) }... }! (TeamGPS) An Introduction to OSL CSA 13 / 45

14 : (1) if (turn == ) { y = kingy-2; if ((kingx, y) ) { if (y<=4) } } else { y = kingy+2; if ((kingx, y) ) { if (y>=6) } 2 (TeamGPS) An Introduction to OSL CSA 14 / 45

15 : (2) (turn, state, kingx, kingy) { // y = kingy+front king[turn]; if ((kingx, y) ) { promote = y*to black y[turn][y]<=4; if (promote) }... } 1 (TeamGPS) An Introduction to OSL CSA 15 / 45

16 : template turn template Turn template Player Turn (state, kingx, kingy) { // y = (Turn == )? kingy-2 : kingy+2; if ((kingx, y) ) { promote = (Turn == )? y<=4 : y >= 6; if (promote) }... } (TeamGPS) An Introduction to OSL CSA 16 / 45

17 : template (state, 4, 6); Turn // y = (Turn == )? kingy-2 : kingy+2; if ((kingx, y) ) { promote = (Turn == )? y<=4 : y >= 6; if (promote) } (TeamGPS) An Introduction to OSL CSA 17 / 45

18 : template (state, 4, 6); Turn // y = ( == )? kingy-2 : kingy+2; if ((kingx, y) ) { promote = ( == )? y<=4 : y >= 6; if (promote) } (TeamGPS) An Introduction to OSL CSA 18 / 45

19 : template (state, 4, 6); Turn // y = kingy-2; if ((kingx, y) ) { promote = y<=4; if (promote) } (TeamGPS) An Introduction to OSL CSA 19 / 45

20 : template template Turn template Turn ( ) template Player Turn (state, kingx, kingy) { // y = (Turn == )? kingy-2 : kingy+2; if ((kingx, y) ) { promote = (Turn == )? y<=4 : y >= 6; if (promote)... }... (TeamGPS) An Introduction to OSL CSA 20 / 45

21 template : partial specialization Fibonacci: template int A struct Fib {static const int val=fib A-1 ::val+fib A-2 ::val; }; A=1 template struct Fib 1 {static const int val=1;}; A=0 template struct Fib 0 {static const int val=0;};? int fib3() { return Fib 3 ::val; } Fib 3 (TeamGPS) An Introduction to OSL CSA 21 / 45

22 Fibonacci template int A struct Fib {static const int val=fib A-1 ::val+fib A-2 ::val; }; A=1 template struct Fib 1 {static const int val=1;}; A=0 template struct Fib 0 {static const int val=0;};? int fib3() { return Fib 3 ::val; } Fib 3 ::val = Fib 2 ::val + Fib 1 ::val; (TeamGPS) An Introduction to OSL CSA 22 / 45

23 Fibonacci template int A struct Fib {static const int val=fib A-1 ::val+fib A-2 ::val; }; A=1 template struct Fib 1 {static const int val=1;}; A=0 template struct Fib 0 {static const int val=0;};? int fib3() { return Fib 3 ::val; } // Fib 3 ::val = Fib 2 ::val + Fib 1 ::val; // Fib 2 ::val = Fib 1 ::val + Fib 0 ::val; return (1+0)+1; (TeamGPS) An Introduction to OSL CSA 23 / 45

24 partial specialization : 10 template! (kingx, kingy); PtypeTraits (osl/include/ptypetraits.h) (TeamGPS) An Introduction to OSL CSA 24 / 45

25 template : : : : : (*) template : (TeamGPS) An Introduction to OSL CSA 25 / 45

26 template : : (A): (B):?? A B 1: A B...1 2: ( ) for ( ) (TeamGPS) An Introduction to OSL CSA 26 / 45

27 template template typename X () { m X(m) } X : () () : osl/include/osl/move action/store.h (TeamGPS) An Introduction to OSL CSA 27 / 45

28 ( int)...4 enum: Player, Ptype, PtypeO, class: Position, Offset, Move : (TeamGPS) An Introduction to OSL CSA 28 / 45

29 enum Player Player: BLACK (0), WHITE (-1) // -1? : include/osl/player.h : Player pl = BLACK, pl2 = alt(pl); // pl2 == WHITE int v = 10 * playertomul(pl); // (pl == BLACK && v = 10) (pl == WHITE && v = 10) int a[2] = { 100, 200 }; int b = a[playertoindex(pl)]; // (pl == BLACK && b = 100) (pl == WHITE && b = 200) (TeamGPS) An Introduction to OSL CSA 29 / 45

30 template class CArray template typename T, size t Capacity class CArray; : C +assert : include/osl/misc/carray.h : CArray int,2 a; // int a[2]; ( ) CArray char,3 b; // char b[2]; ( ) CArray int,2 c = {{5,8}}; // int c[2] = {5,8}; // c[0] == 5, c[1] == 8 // c[playertoindex(black)] == 5, c[playertoindex(white)] == 8 // c[black] == 5, c[white] == 8 (TeamGPS) An Introduction to OSL CSA 30 / 45

31 enum Ptype Ptype KING, GOLD, PAWN, LANCE, KNIGHT, GOLD, SILVER, BISHOP, ROOK (EMPTY, EDGE) P PPAWN,... PROOK (c.f., Bonanza Dragon) : 8 : include/osl/ptype.h : Ptype rook = ROOK, prook = promote(rook); // prook == PROOK // unpromote(prook) == ROOK // unpromote(pawn) == PAWN // unpromote(gold) == GOLD (TeamGPS) An Introduction to OSL CSA 31 / 45

32 enum PtypeO PtypeO Ptype + Player (O Owner) : BLACK, WHITE : include/osl/ptype.h : PtypeO ptypeo = newptypeo(black, PROOK); // getptype(ptypeo) == PROOK // getowner(ptypeo) == BLACK // captured(ptypeo) == newptypeo(white, ROOK) // eval.value(newptypeo(black, PAWN)) // == -eval.value(newptypeo(white, PAWN)) (TeamGPS) An Introduction to OSL CSA 32 / 45

33 class Position, Offset Position: file + rank ( Square?) : x*16+y+1 Offset: Position include/osl/{position,offset}.h, lib/offset.cc : Position p27(2,7), p26(2,6); // p26.x() == 2, p26.y() == 6; Offset o(0, -1), o2 = p26 - p27; // o == o2; // p27+o == p26, (p26+o) == Position(2,5); // p27.canpromote(black) == false // p27.canpromote(white) == true // p27.canpromote BLACK () == false (TeamGPS) An Introduction to OSL CSA 33 / 45

34 enum Direction Direction 10 : UL, U, UR, L, R, DL, D, DR, UUL, UUR, : LONG UL, LONG U,..., LONG DR : include/osl/direction,directiontraits.h : // shorttolong(u) == LONG U // longtoshort(long U) == U : // DirectionPlayerTraits BLACK,U ::offset() // == -DirectionPlayerTraits WHITE,U ::offset() // DirectionPlayerTraits BLACK,U ::offset() == Offset(0,1) (TeamGPS) An Introduction to OSL CSA 34 / 45

35 class Piece Piece: (Position+PtypeO ) : include/osl/piece.h,lib/piece.cc : Piece p =.getpieceat(position(7,7)); // p.position() == Position(7,7) // p.ptypeo() == newptypeo(black, PAWN) // p.owner() == BLACK // p.ptype() == ROOK (TeamGPS) An Introduction to OSL CSA 35 / 45

36 class Move Move: : include/osl/move.h,lib/move.cc : Move m76(position(7,7), Position(7,6), PAWN, PTYPE EMPTY, false, BLACK); // m76.to() == Position(7,6) // m76.to() == Position(7,7) // m76.ptype() == PAWN // m76.captureptype() == PTYPE EMPTY // m76.ispromote() == false // m76.isdrop() == false // m76.player() == BLACK (TeamGPS) An Introduction to OSL CSA 36 / 45

37 C++ Q. OSL PtypeO enum Piece class PtypeO class getowner class? A. (TeamGPS) An Introduction to OSL CSA 37 / 45

38 : (TeamGPS) An Introduction to OSL CSA 38 / 45

39 : (c.f. YSS) : include/osl/state/{simple,numeffect}state.{h,tcc} : CArray PieceMask,2 stand mask; CArray Piece,Position::SIZE board; CArray Piece,Piece::SIZE pieces; x bitset CArray BitXmask,2 pawnmask; CArray PieceMask,2 onboardmask; PieceMask promoted; (TeamGPS) An Introduction to OSL CSA 39 / 45

40 : include/osl/effect/numsimpleeffect.{h,tcc} : 0-39 : : : (sentinel 6bit) : (sentinel 6bit) : popcount cpu bit 1 (TeamGPS) An Introduction to OSL CSA 40 / 45

41 : include/osl/move generator/escape.{h,tcc} (TeamGPS) An Introduction to OSL CSA 41 / 45

42 Q&A ( ) Q. template inline? A. GPS inline Q. A. Q. gps l? A. osl/include/osl/eval/experimental/testeval.h osl/lib/eval/experimental/testeval.cc osl-for-csa OSL ( 6 ) (TeamGPS) An Introduction to OSL CSA 42 / 45

43 Q&A ( ) Q. gps l? A. gps normal gps l opteron Q.? A.? Q.? A. 2 5x5 Q. A. floodgate (TeamGPS) An Introduction to OSL CSA 43 / 45

44 Q&A ( ) Q. (J )? A. GPW2008 = 1 T ( ξ(i) ξ( ) ) i (ξ T(x) T(x) = 1/(1 + exp( 3x/128)) 128 ) ( ) Q. J =2.9? A. 3 k-fold cross validation (TeamGPS) An Introduction to OSL CSA 44 / 45

45 Q&A ( ) Q. A. GPW08 l 1 Q ? A. Q. A. % root Q. mpn A. beta cut beta cut alpha (TeamGPS) An Introduction to OSL CSA 45 / 45

The 15th Game Programming Workshop 2010 Magic Bitboard Magic Bitboard Bitboard Magic Bitboard Bitboard Magic Bitboard Magic Bitboard Magic Bitbo

The 15th Game Programming Workshop 2010 Magic Bitboard Magic Bitboard Bitboard Magic Bitboard Bitboard Magic Bitboard Magic Bitboard Magic Bitbo Magic Bitboard Magic Bitboard Bitboard Magic Bitboard Bitboard Magic Bitboard 64 81 Magic Bitboard Magic Bitboard Bonanza Proposal and Implementation of Magic Bitboards in Shogi Issei Yamamoto, Shogo Takeuchi,