main.cpp - harmless - a gomoku engine - Google Project Hosting

Source path: svn/ trunk/ main.cpp

‹r8

//
// press zM before doing ANYTHING or looking ANYWHERE, 
//  - if you're using VIM
//
// 
// Author:         If ( www.if-yu.info | if.html@gmail.com )
// Last edit date: Dec 31st, 2010
// Version:        unknown... Orz
// License:        GPL v3
//
// {{{ license
/*
 *                  Harmless: a harmless GoMoku AI
 *
 *  Copyright (C) 2010 If
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
// }}}


#include <utility>
#include <exception>
#include <stdexcept>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cmath>
#include <time.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#ifdef DEBUG_GOMOKU
using std::cout;
using std::cerr;
using std::endl;
using std::flush;
#endif

#ifdef DEBUG_GOMOKU
#define dbg(...)   fprintf(stderr, __VA_ARGS__)
#define dexec(...) __VA_ARGS__
#else
#define dbg(...)   /* nothing at all */
#define dexec(...) /* nothing at all */
#endif

#ifdef DEBUG_GOMOKU
const clock_t    timeLimit=240*CLOCKS_PER_SEC/1000;
#else
const clock_t    timeLimit=830*CLOCKS_PER_SEC/1000;
#endif

#define MAX_VALUE  1000000
#define WIN_VALUE  900000
#define HTCAPACITY 2097152
#define X 'X'
#define O 'O'
// i am always O


// {{{ data structs
typedef uint32_t uint;
struct Pos {
    uint8_t row:4,
            col:4;
    inline Pos() { }
    inline Pos(uint8_t r, uint8_t c):
        row(r), col(c)
    { }
    inline Pos(uint32_t u):
        row((u>>4)&15), col(u&15)
    { }
    inline Pos(Pos const& p):
        row(p.row), col(p.col)
    { }
    inline uint8_t u8() const {
        return (row<<4)|col;
    }
    inline Pos&operator=(Pos const& p){
        *reinterpret_cast<uint8_t*>(this)=*reinterpret_cast<uint8_t const*>(&p);
        return *this;
    }
    inline bool operator==(Pos const& p) const {
        return this->row==p.row && this->col==p.col;
    }
};
std::ostream& operator<<(std::ostream& os, Pos const&p) {
    return os<<"("<<(int)p.row<<", "<<(int)p.col<<")";
}
struct Threat {
    Pos      p;   // position
    uint16_t lvl; // level ( same as it difined in maskTable )
};
inline bool operator<(Threat const& a, Threat const& b) {
    return a.lvl>b.lvl; // to make sort easier
}
struct HashKey {
    uint64_t k64;
    uint16_t type; // 0:exact; 1:alpha; 2:beta; 3:unknown;
    uint16_t depth;
    int32_t  v;
};
// }}}
// {{{ the game board
namespace board {
    typedef uint16_t BoardT[16];
    typedef uint16_t RotBoardT[32];

    // bit board X
    //        |  rotated X      
    //        V      V
    BoardT    bX,   rbX;

    //     left-top X
    //         |  right-top X
    //         V      V
    RotBoardT ltbX, rtbX;

    // same as above
    BoardT    bO,   rbO;
    RotBoardT ltbO, rtbO;

    //    each direction -----+
    //      ( 0: summerize    |
    //        1: horizontal   |
    //        2: vertical     |
    //        3: \ diagnal    |
    //        4: / diagnal )  |
    //    side ----+          |
    //             |          |
    //             V          V
    uint16_t  mark[2][16][16][5];
    //                ^   ^
    //                |   |
    //                +---+--- coordinate
    // summerize:
    // mark[r][c][1] | mark[r][c][2] | ...

    // goodMoves[depth][threatLevel] records good moves
    // threatLevel 3 : 4s / 4-3s like #OO-O, O#-OO &etc.
    // threatLevel 2 : 3s / 3-2s like -O-O#, #-O-O &etc.
    // threatLevel 1 : 2s / 2-1s like ---O#, -#-O- &etc.
    // threatLevel 0 : 1s        like ---#-, --#-- &etc.
    Threat    goodMoves[32][4][256];
    // size of above array
    int       gmSize[32][4];

    // all moves going to be checked in alphaBeta function
    // should be sorted after generate
    Threat    availableMoves[32][256];
    // size of above array
    int       amSize[32];

    // positions ---------------+
    //                          |
    // level     -----------+   |
    // [0] : 6 || 7         |   |
    // [1] : 8              |   |
    //                      |   |
    // depth     -------+   |   |
    //                  |   |   |
    //                  V   V   V
    uint8_t   tssStack[256][2][256];
    uint8_t   tssSize [256][2];

    // statistical info
    // statistic[0]: myself
    // statistic[1]: enimy
    int       statistic[2][32][8];

    // zobrist hash
    uint64_t  hash;
    uint8_t   win;
    // not used so far
    uint16_t  nThreats;
    uint16_t  ply;
    // not used at contest
    Pos       winLine[5];
    uint8_t   vfo,vfx,vto,vtx;
    Pos       steps[256];
    int8_t    i8Steps[256][2]; // for opening-book searching
    bool      obNotFound;      // current moves is not in opening book
    int       obIndex;         // index of current move in opening book - if exist
    int       iFirst;          // i am black

    clock_t   startTime;
    clock_t   endTime;

    // for debug:
#ifdef DEBUG_GOMOKU
    int       nodesSearched; 
    int       tssNodeSearched;
#endif
}
// }}}
// {{{ hash
static HashKey  hashTable[HTCAPACITY+3]={{0}};
static uint64_t zobristKeys[2][256]={{0},{0}};

inline uint64_t hash(uint64_t h, char who, Pos p) {
    return h^zobristKeys[who==O?0:1][(p.row<<4)|p.col];
}
inline void htupdate(uint64_t k64, int16_t type, int16_t depth, int32_t v) {
    uint32_t k32=((uint32_t)(k64^(k64>>32)))&(HTCAPACITY-1);
    HashKey *key=hashTable+k32;
    if(key->depth > depth) return;
    key->k64=k64;
    key->type=type;
    key->depth=depth;
    key->v=v;
}
inline HashKey const* htget(uint64_t k64) {
    uint32_t k32=((uint32_t)((k64>>32)^k64))&(HTCAPACITY-1);
    HashKey*pos=hashTable+k32;
    if(pos->k64==k64) return pos;
    return 0;
}
// }}}
// {{{ cached threats
// cachedThreats:
// cached every combination of nine pieces, for example -XOOO-O-X
//                                                          ^
//                                                          |
//                                                          +-------+
//                                                                  |
// what stores in the 32-bit data field is about the center piece  -+
// 
// 0001 010 0000 0 0000 0000 0 1000
// |    |   |      |    |      |
// |    |   |      |    +------+-------> places of threats of level 4 ( OOO#O )
// |    |   +------+-------------------> places of threats of level 3 ( OOO## )
// |    +-----------------> threat level ( 0 for not a threat, 1 for 3s, 2 for 4s, 4 for win )
// +----------------------> number of threats
uint32_t cachedThreats[512][512]={{0}};
// }}}
// {{{ constants
// {{{ bit operation
static const int bitsInChar[256]={
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,
2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
static const int highestBit[256]={
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};
static const int lowestBit[256]={
8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,
3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,
3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,
3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
};
// }}}
// {{{ threat level
// 0 : occupied || no value at all
// 1 : 1        || broken 2      eg.    O---#  ||  O--#
// 2 : 2        || broken 2      eg.    O-#    ||  O#     ||  X-OO#-X
// 3 : broken 3 || blocked 3     eg.    OO--#  ||  O#--O  ||  #O--O
// 4 : broken 3                  eg.    OO-#   ||  O#-O   ||  #O-O
// 5 : open 3                    eg.    OO#    ||  O#O
// 6 : 4                         eg.    OOO-#  ||  OO-#O  ||  XOO#O- &etc.
// 7 : open 4                    ie.    -OOO#-
// 8 : 5                         ie.    OOOO# &etc.
static const uint8_t maskTable[4][32][6] = {
{
//  safe shift amount (TODO)
//         |    
//         V    
{0,0,0,0,0,1}, // 0  -----
{1,1,2,2,0,1}, // 1  ----O
{1,2,2,0,2,1}, // 2  ---O-
{3,4,5,0,0,1}, // 3  ---OO
{2,2,0,2,2,1}, // 4  --O--
{2,4,0,5,0,1}, // 5  --O-O
{3,4,0,0,4,1}, // 6  --OO-
{6,7,0,0,0,1}, // 7  --OOO
{2,0,2,2,1,1}, // 8  -O---
{3,0,4,4,0,1}, // 9  -O--O
{4,0,5,0,4,1}, // 10 -O-O-
{6,0,7,0,0,1}, // 11 -O-OO
{5,0,0,5,4,1}, // 12 -OO--
{6,0,0,7,0,1}, // 13 -OO-O
{7,0,0,0,7,1}, // 14 -OOO-
{8,0,0,0,0,1}, // 15 -OOOO
{0,2,2,1,1,1}, // 16 O----
{0,3,3,3,0,1}, // 17 O---O
{0,4,4,0,3,1}, // 18 O--O-
{0,6,6,0,0,1}, // 19 O--OO
{0,5,0,4,3,1}, // 20 O-O--
{0,6,0,6,0,1}, // 21 O-O-O
{0,7,0,0,6,1}, // 22 O-OO-
{0,8,0,0,0,1}, // 23 O-OOO
{0,0,5,4,3,1}, // 24 OO---
{0,0,6,6,0,1}, // 25 OO--O
{0,0,7,0,6,1}, // 26 OO-O-
{0,0,8,0,0,1}, // 27 OO-OO
{0,0,0,7,6,1}, // 28 OOO--
{0,0,0,8,0,1}, // 29 OOO-O
{0,0,0,0,8,1}, // 30 OOOO-
{0,0,0,0,0,4}  // 31 OOOOO
},
{
{0,0,0,0,0,1}, // 0  x-----
{0,1,2,2,0,1}, // 1  x----O
{1,2,2,0,2,1}, // 2  x---O-
{3,4,5,0,0,1}, // 3  x---OO
{1,2,0,2,2,1}, // 4  x--O--
{1,4,0,5,0,1}, // 5  x--O-O
{3,5,0,0,5,1}, // 6  x--OO-
{6,7,0,0,0,1}, // 7  x--OOO
{1,0,2,2,1,1}, // 8  x-O---
{1,0,4,4,0,1}, // 9  x-O--O
{3,0,5,0,4,1}, // 10 x-O-O-
{6,0,7,0,0,1}, // 11 x-O-OO
{3,0,0,5,4,1}, // 12 x-OO--
{6,0,0,7,0,1}, // 13 x-OO-O
{6,0,0,0,7,1}, // 14 x-OOO-
{8,0,0,0,0,1}, // 15 x-OOOO
{0,1,1,1,0,1}, // 16 xO----
{0,3,3,3,0,1}, // 17 xO---O
{0,3,3,0,3,1}, // 18 xO--O-
{0,6,6,0,0,1}, // 19 xO--OO
{0,3,0,3,3,1}, // 20 xO-O--
{0,6,0,6,0,1}, // 21 xO-O-O
{0,6,0,0,6,1}, // 22 xO-OO-
{0,8,0,0,0,1}, // 23 xO-OOO
{0,0,3,3,3,1}, // 24 xOO---
{0,0,6,6,0,1}, // 25 xOO--O
{0,0,6,0,6,1}, // 26 xOO-O-
{0,0,8,0,0,1}, // 27 xOO-OO
{0,0,0,6,6,1}, // 28 xOOO--
{0,0,0,8,0,1}, // 29 xOOO-O
{0,0,0,0,8,1}, // 30 xOOOO-
{0,0,0,0,0,3}  // 31 xOOOOO
},
{
{0,0,0,0,0,1}, // 0  -----x
{0,1,1,1,0,1}, // 1  ----Ox
{1,2,2,0,1,1}, // 2  ---O-x
{3,3,3,0,0,1}, // 3  ---OOx
{2,2,0,2,1,1}, // 4  --O--x
{3,3,0,3,0,1}, // 5  --O-Ox
{4,4,0,0,3,1}, // 6  --OO-x
{6,6,0,0,0,1}, // 7  --OOOx
{2,0,2,2,1,1}, // 8  -O---x
{3,0,3,3,0,1}, // 9  -O--Ox
{4,0,5,0,3,1}, // 10 -O-O-x
{6,0,6,0,0,1}, // 11 -O-OOx
{5,0,0,5,3,1}, // 12 -OO--x
{6,0,0,6,0,1}, // 13 -OO-Ox
{7,0,0,0,6,1}, // 14 -OOO-x
{8,0,0,0,0,1}, // 15 -OOOOx
{0,2,2,1,0,1}, // 16 O----x
{0,3,3,3,0,1}, // 17 O---Ox
{0,4,4,0,3,1}, // 18 O--O-x
{0,6,6,0,0,1}, // 19 O--OOx
{0,5,0,4,3,1}, // 20 O-O--x
{0,6,0,6,0,1}, // 21 O-O-Ox
{0,7,0,0,6,1}, // 22 O-OO-x
{0,8,0,0,0,1}, // 23 O-OOOx
{0,0,5,4,3,1}, // 24 OO---x
{0,0,6,6,0,1}, // 25 OO--Ox
{0,0,7,0,6,1}, // 26 OO-O-x
{0,0,8,0,0,1}, // 27 OO-OOx
{0,0,0,7,6,1}, // 28 OOO--x
{0,0,0,8,0,1}, // 29 OOO-Ox
{0,0,0,0,8,1}, // 30 OOOO-x
{0,0,0,0,0,3}  // 31 OOOOOx
},
{
{0,0,0,0,0,5}, // 0  x-----x
{0,1,1,1,0,5}, // 1  x----Ox
{0,1,1,0,0,5}, // 2  x---O-x
{3,3,3,0,0,5}, // 3  x---OOx
{1,1,0,1,1,5}, // 4  x--O--x
{3,3,0,3,0,5}, // 5  x--O-Ox
{3,3,0,0,3,5}, // 6  x--OO-x
{6,6,0,0,0,5}, // 7  x--OOOx
{1,0,1,1,0,5}, // 8  x-O---x
{3,0,3,3,0,5}, // 9  x-O--Ox
{3,0,3,0,3,5}, // 10 x-O-O-x
{6,0,6,0,0,5}, // 11 x-O-OOx
{3,0,0,3,3,5}, // 12 x-OO--x
{6,0,0,6,0,5}, // 13 x-OO-Ox
{6,0,0,0,6,5}, // 14 x-OOO-x
{8,0,0,0,0,5}, // 15 x-OOOOx
{0,2,1,1,1,5}, // 16 xO----x
{0,2,2,2,0,5}, // 17 xO---Ox
{0,3,3,0,3,5}, // 18 xO--O-x
{0,6,6,0,0,5}, // 19 xO--OOx
{0,3,0,3,3,5}, // 20 xO-O--x
{0,6,0,6,0,5}, // 21 xO-O-Ox
{0,6,0,0,6,5}, // 22 xO-OO-x
{0,8,0,0,0,5}, // 23 xO-OOOx
{0,0,3,3,3,5}, // 24 xOO---x
{0,0,6,6,0,5}, // 25 xOO--Ox
{0,0,6,0,6,5}, // 26 xOO-O-x
{0,0,8,0,0,5}, // 27 xOO-OOx
{0,0,0,6,6,5}, // 28 xOOO--x
{0,0,0,8,0,5}, // 29 xOOO-Ox
{0,0,0,0,8,5}, // 30 xOOOO-x
{0,0,0,0,0,5}  // 31 xOOOOOx
}
};
// }}}
// {{{ power
static const int
SM_10=2,
SM_11=137,
SM_20=5,
SM_21=526,
SM_22=2464,
SM_30=778,
SM_31=1104,
SM_32=5408,
SM_33=459,
SM_43=2,
SM_44=4,
SM_4x=3,
SO_10=8,
SO_11=2,
SO_20=18,
SO_21=14,
SO_22=2802,
SO_30=1424,
SO_31=811,
SO_32=708,
SO_33=3522,
SO_43=213,
SO_44=1546,
SO_4x=11873;
// }}}
// {{{ opening book
//             position -----------------+
//             index    -----------+     |
//             who wins --------+  |     |
//             ( 0: black;      |  |     |
//               1: white. )    V  V     V
static int8_t openingBook[2][8*1024][64][2] = {
// black win
{
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{6,9},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{9,6},{8,6},{9,5},{10,8},{7,5},{11,9},{12,10},{11,7},{10,7},{11,8},{11,10},{12,8},{13,8},{12,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{9,6},{8,6},{9,5},{10,8},{7,5},{11,9},{12,10},{11,7},{10,7},{11,8},{11,6},{11,10},{11,11},{9,8},{10,9},{12,8},{13,8},{9,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{9,6},{8,6},{9,5},{10,8},{11,9},{7,5},{6,4},{7,6},{7,4},{10,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{10,5},{10,7},{11,7},{9,8},{9,9},{7,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{10,5},{10,7},{11,7},{9,8},{9,5},{10,9},{7,6},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{10,5},{10,7},{11,7},{9,8},{9,5},{10,9},{11,10},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{6,9},{10,7},{11,7},{10,5},{11,4},{9,5},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{7,6},{8,6},{9,5},{10,7},{11,7},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{6,9},{8,6},{9,5},{7,5},{10,8},{6,4},{5,3},{7,4},{7,6},{8,4},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{6,9},{8,6},{9,5},{7,5},{6,4},{7,6},{7,4},{9,6},{10,6},{9,8},{10,9},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{8,8},{9,7},{9,9},{10,7},{11,7},{7,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{8,8},{9,7},{9,5},{10,7},{11,7},{10,9},{7,6},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{8,8},{9,7},{9,5},{10,7},{11,7},{10,9},{11,10},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{10,8},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{6,9},{9,8},{8,8},{7,6},{6,5},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{6,9},{9,8},{8,8},{7,6},{10,9},{10,5},{11,4},{6,5},{5,4},{7,5},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{7,6},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{6,6},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{4,7},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{4,8},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{4,9},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{6,10},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{9,8},{8,6},{9,5},{7,9},{7,10},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{9,8},{8,6},{9,5},{7,9},{7,6},{7,11},{7,10},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{5,8},{8,6},{9,5},{7,6},{7,5},{8,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{5,8},{8,6},{9,5},{7,6},{7,9},{7,5},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{5,8},{9,8},{10,8},{9,9},{6,6},{7,9},{7,6},{8,9},{6,9},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{5,8},{9,8},{10,8},{9,9},{6,6},{7,9},{7,10},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{5,8},{9,8},{10,8},{9,9},{10,10},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{9,8},{7,9},{7,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{9,8},{7,9},{7,6},{7,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,7},{8,8},{9,8},{7,9},{7,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,7},{8,8},{9,8},{7,9},{7,6},{7,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,6},{7,11},{7,10},{6,10},{4,8},{6,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,6},{7,11},{7,10},{6,10},{8,12},{6,9},{8,9},{6,11},{6,12},{4,8},{3,7},{4,9},{3,9},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,10},{6,9},{4,9},{7,6},{7,5},{8,6},{9,5},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,10},{6,9},{8,9},{7,6},{7,5},{8,6},{9,5},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,10},{8,6},{9,5},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,6},{6,9},{4,9},{8,9},{9,9},{8,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,6},{6,9},{8,9},{8,6},{9,5},{9,7},{6,10},{8,7},{9,6},{7,10},{7,11},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,6},{6,9},{8,9},{8,6},{9,5},{9,7},{10,6},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,10},{8,6},{9,5},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{5,8},{8,6},{9,5},{10,8},{9,8},{7,5},{15,15}},

{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{6,12},{5,10},{5,12},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{6,12},{5,10},{5,8},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{2,8},{5,10},{5,12},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{2,8},{5,10},{5,8},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{1,7},{5,11},{6,12},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{4,6},{1,7},{0,6},{1,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{6,11},{1,7},{0,6},{1,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{2,7},{3,10},{2,10},{6,11},{7,12},{7,10},{6,10},{5,12},{4,13},{7,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{2,7},{3,10},{2,10},{6,11},{7,12},{7,10},{6,10},{5,12},{8,9},{2,11},{1,12},{4,13},{3,14},{1,7},{0,6},{1,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{2,7},{3,10},{6,10},{1,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,10},{3,6},{3,5},{4,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{6,10},{7,8},{5,8},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{6,10},{7,8},{8,8},{3,8},{5,8},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{6,10},{7,8},{3,8},{8,8},{5,8},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{2,6},{5,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{5,10},{2,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{6,10},{4,7},{4,6},{2,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{2,8},{6,4},{7,3},{6,6},{4,4},{6,10},{7,11},{6,11},{5,10},{6,9},{6,12},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{2,8},{6,4},{7,3},{6,6},{8,8},{4,4},{3,3},{3,4},{5,4},{3,6},{3,5},{6,10},{7,11},{6,11},{5,10},{6,9},{6,12},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{6,4},{8,8},{6,6},{6,10},{7,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{6,4},{8,8},{9,9},{6,10},{7,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{6,4},{8,8},{4,4},{6,10},{7,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{7,8},{5,8},{2,8},{4,7},{4,6},{6,9},{7,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{7,8},{5,8},{2,8},{4,7},{4,6},{6,9},{3,6},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{5,11},{3,10},{6,10},{2,10},{1,10},{2,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{5,11},{3,10},{2,10},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{3,9},{3,10},{2,10},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{3,9},{3,10},{6,10},{2,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,10},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,8},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,8},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,12},{3,9},{6,12},{4,8},{4,7},{2,8},{1,7},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,12},{3,9},{2,8},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,8},{6,11},{7,12},{3,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,8},{6,11},{3,8},{7,12},{8,13},{6,12},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,8},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{6,12},{3,8},{6,11},{2,8},{1,7},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{6,12},{3,8},{2,7},{2,8},{1,7},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{2,8},{3,10},{2,10},{6,10},{7,10},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{2,8},{3,10},{6,10},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,8},{3,9},{6,12},{6,10},{3,10},{4,8},{7,11},{2,11},{1,7},{3,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,8},{3,9},{6,12},{6,10},{3,10},{4,8},{3,7},{7,11},{8,12},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,8},{3,9},{6,12},{6,10},{7,10},{2,8},{1,7},{2,9},{1,9},{2,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{5,12},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,11},{3,9},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{5,8},{7,6},{5,7},{5,6},{6,6},{7,5},{7,4},{9,5},{10,4},{9,7},{10,8},{9,6},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{7,6},{8,5},{8,7},{9,5},{10,4},{9,6},{7,4},{9,4},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{7,8},{7,6},{7,5},{9,6},{10,6},{9,8},{9,7},{8,7},{10,9},{8,5},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{7,8},{7,6},{7,5},{9,6},{10,6},{9,8},{9,7},{8,7},{6,5},{8,9},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{8,7},{9,5},{10,4},{7,6},{7,5},{6,6},{5,6},{8,8},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{6,9},{7,6},{7,8},{9,5},{10,4},{9,6},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{8,5},{7,6},{7,8},{9,5},{10,4},{9,6},{10,6},{9,7},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{9,8},{6,6},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{6,5},{10,6},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{4,9},{3,9},{5,10},{9,8},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{4,9},{3,9},{5,9},{9,8},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{9,5},{8,7},{8,8},{9,8},{10,7},{10,9},{11,10},{9,9},{11,9},{10,6},{7,6},{9,11},{9,10},{8,10},{7,9},{7,11},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{9,5},{8,7},{8,8},{9,8},{9,7},{10,7},{7,10},{10,9},{7,6},{11,6},{12,5},{11,10},{12,11},{11,9},{9,9},{11,8},{11,7},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{8,8},{5,9},{8,6},{6,9},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{5,6},{8,6},{5,9},{8,8},{8,7},{9,9},{6,6},{10,10},{11,11},{10,9},{11,9},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{5,6},{8,6},{9,5},{8,8},{8,7},{9,9},{10,10},{11,9},{10,9},{10,8},{9,7},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{7,10},{8,6},{5,9},{8,8},{8,7},{9,6},{9,5},{9,9},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{7,10},{8,6},{9,5},{9,9},{8,8},{5,9},{4,10},{7,9},{6,9},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,9},{5,5},{6,6},{7,5},{7,4},{6,5},{8,5},{8,6},{5,9},{8,7},{9,8},{6,4},{5,3},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,9},{5,5},{6,6},{7,5},{7,4},{6,5},{8,5},{8,6},{5,9},{8,7},{9,8},{6,4},{10,8},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,9},{5,5},{7,5},{8,8},{6,6},{8,7},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,5},{5,9},{8,6},{4,9},{7,9},{4,10},{3,11},{4,8},{4,7},{4,11},{4,12},{6,9},{5,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,9},{7,9},{7,10},{5,7},{8,10},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,9},{7,9},{7,6},{5,8},{4,8},{8,8},{9,8},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{4,7},{8,8},{5,8},{9,8},{10,8},{9,9},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{4,7},{8,8},{9,8},{7,9},{7,6},{5,9},{8,6},{4,10},{3,11},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{4,7},{7,8},{5,9},{8,8},{9,8},{7,9},{7,10},{9,7},{10,6},{9,9},{6,6},{8,9},{10,9},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{8,6},{5,9},{5,8},{4,9},{4,10},{7,9},{6,9},{7,10},{7,8},{8,10},{9,11},{9,10},{10,10},{5,10},{6,10},{6,11},{7,12},{5,12},{8,9},{2,7},{3,8},{4,11},{5,11},{2,9},{3,10},{2,8},{2,10},{2,6},{2,5},{4,6},{5,7},{1,9},{15,15}},
{{7,7},{6,7},{6,8},{8,6},{5,9},{6,9},{4,10},{3,11},{5,8},{4,8},{5,7},{5,6},{7,9},{8,10},{7,8},{7,10},{8,8},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{9,7},{8,5},{8,6},{7,6},{5,8},{9,8},{10,9},{10,7},{7,10},{7,4},{9,6},{6,5},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{9,7},{8,5},{8,6},{7,6},{5,8},{9,8},{6,5},{10,7},{11,6},{10,9},{11,10},{9,9},{7,9},{10,10},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{5,7},{7,9},{9,7},{10,9},{9,9},{7,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{5,7},{7,9},{9,7},{10,9},{6,9},{7,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{8,7},{7,8},{5,6},{7,9},{7,6},{8,6},{4,6},{3,6},{9,8},{7,11},{7,10},{9,10},{10,11},{10,9},{6,5},{5,4},{9,9},{8,11},{7,12},{5,11},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{8,7},{9,8},{6,5},{10,7},{7,10},{10,8},{6,4},{6,7},{9,6},{10,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{8,10},{5,7},{10,6},{9,6},{7,9},{8,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{8,10},{5,7},{10,6},{9,6},{8,7},{5,8},{5,9},{4,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{7,9},{8,10},{8,11},{9,10},{7,10},{9,9},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,6},{7,9},{7,6},{9,6},{6,9},{6,7},{9,7},{7,10},{5,6},{4,6},{10,8},{7,11},{7,8},{11,9},{7,5},{6,4},{9,9},{6,11},{5,12},{8,10},{8,11},{7,12},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,6},{7,9},{6,9},{6,10},{9,7},{8,10},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,7},{7,9},{6,5},{6,9},{5,9},{9,9},{10,9},{10,10},{11,11},{6,10},{5,11},{9,8},{6,4},{6,7},{6,3},{6,2},{9,7},{7,8},{7,10},{9,10},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,9},{8,10},{8,7},{7,10},{6,9},{6,10},{5,10},{7,8},{6,5},{6,7},{9,10},{9,8},{6,11},{10,8},{11,8},{9,9},{11,7},{7,11},{6,12},{10,10},{11,11},{8,12},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,9},{8,10},{8,7},{7,10},{6,9},{6,10},{5,10},{7,8},{6,5},{6,7},{9,10},{9,8},{6,11},{10,8},{11,8},{9,9},{7,11},{10,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,8},{8,10},{8,7},{6,9},{9,9},{8,11},{8,12},{7,10},{5,8},{9,10},{4,8},{3,8},{6,10},{10,9},{11,8},{10,10},{11,10},{10,13},{9,12},{10,11},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{6,7},{6,9},{9,9},{8,7},{8,10},{8,5},{8,6},{9,6},{7,8},{10,7},{11,8},{9,8},{11,6},{6,5},{9,7},{7,4},{6,3},{7,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{6,7},{6,9},{9,9},{8,7},{8,10},{8,5},{8,6},{9,6},{7,8},{10,7},{11,8},{9,8},{11,6},{6,5},{7,6},{9,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{5,7},{4,9},{7,5},{4,8},{6,5},{6,9},{6,4},{6,7},{8,4},{9,3},{6,3},{6,2},{9,9},{7,8},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{5,7},{4,9},{7,5},{4,8},{6,9},{6,7},{8,4},{9,3},{7,8},{8,7},{15,15}},
{{7,7},{6,8},{8,8},{9,9},{6,6},{7,6},{5,5},{4,4},{7,5},{4,6},{9,7},{4,5},{4,7},{4,3},{4,2},{5,7},{7,9},{6,10},{8,7},{15,15}},
{{7,7},{6,8},{8,8},{9,9},{6,6},{7,9},{5,7},{8,9},{5,5},{4,4},{6,9},{5,6},{7,5},{4,8},{6,5},{8,5},{6,7},{15,15}},
{{7,7},{6,8},{8,8},{8,9},{6,6},{9,9},{5,7},{7,5},{5,5},{4,4},{5,6},{5,4},{6,7},{4,7},{7,6},{15,15}},

{{7,7},{5,7},{9,7},{16,16}},
{{7,7},{5,8},{6,6},{5,5},{5,7},{16,16}},
{{7,7},{5,9},{8,8},{6,6},{8,7},{16,16}}
},
// white win
{
{{7,7},{6,6},{5,5},{6,7},{15,15}},
{{7,7},{6,6},{6,7},{5,7},{7,5},{6,8},{16,16}},
{{7,7},{6,6},{7,9},{7,8},{16,16}},
{{7,7},{6,6},{5,7},{4,7},{16,16}},
{{7,7},{6,6},{5,6},{6,7},{16,16}},
{{7,7},{6,6},{7,8},{7,6},{7,9},{5,7},{7,5},{5,4},{16,16}}
}
};
int obSize[2] = {
    144,
    6
};
// }}}
// {{{ affine
static const uint8_t affineLT[32][16] = {
{255, 255, 255, 255, 255, 255, 255,  14, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,  13,  30, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,  12,  29,  46, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,  11,  28,  45,  62, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,  10,  27,  44,  61,  78, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   9,  26,  43,  60,  77,  94, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   8,  25,  42,  59,  76,  93, 110, 255, 255, 255, 255, 255},
{255, 255, 255,   7,  24,  41,  58,  75,  92, 109, 126, 255, 255, 255, 255, 255},
{255, 255, 255,   6,  23,  40,  57,  74,  91, 108, 125, 142, 255, 255, 255, 255},
{255, 255,   5,  22,  39,  56,  73,  90, 107, 124, 141, 158, 255, 255, 255, 255},
{255, 255,   4,  21,  38,  55,  72,  89, 106, 123, 140, 157, 174, 255, 255, 255},
{255,   3,  20,  37,  54,  71,  88, 105, 122, 139, 156, 173, 190, 255, 255, 255},
{255,   2,  19,  36,  53,  70,  87, 104, 121, 138, 155, 172, 189, 206, 255, 255},
{  1,  18,  35,  52,  69,  86, 103, 120, 137, 154, 171, 188, 205, 222, 255, 255},
{  0,  17,  34,  51,  68,  85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255},
{ 16,  33,  50,  67,  84, 101, 118, 135, 152, 169, 186, 203, 220, 237, 255, 255},
{255,  32,  49,  66,  83, 100, 117, 134, 151, 168, 185, 202, 219, 236, 255, 255},
{255,  48,  65,  82,  99, 116, 133, 150, 167, 184, 201, 218, 235, 255, 255, 255},
{255, 255,  64,  81,  98, 115, 132, 149, 166, 183, 200, 217, 234, 255, 255, 255},
{255, 255,  80,  97, 114, 131, 148, 165, 182, 199, 216, 233, 255, 255, 255, 255},
{255, 255, 255,  96, 113, 130, 147, 164, 181, 198, 215, 232, 255, 255, 255, 255},
{255, 255, 255, 112, 129, 146, 163, 180, 197, 214, 231, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 128, 145, 162, 179, 196, 213, 230, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 144, 161, 178, 195, 212, 229, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 160, 177, 194, 211, 228, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 176, 193, 210, 227, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 192, 209, 226, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 208, 225, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 224, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
};
static const uint8_t affineRT[32][16] = {
{255, 255, 255, 255, 255, 255, 255,   0, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,   1,  16, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,   2,  17,  32, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,   3,  18,  33,  48, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,   4,  19,  34,  49,  64, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   5,  20,  35,  50,  65,  80, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   6,  21,  36,  51,  66,  81,  96, 255, 255, 255, 255, 255},
{255, 255, 255,   7,  22,  37,  52,  67,  82,  97, 112, 255, 255, 255, 255, 255},
{255, 255, 255,   8,  23,  38,  53,  68,  83,  98, 113, 128, 255, 255, 255, 255},
{255, 255,   9,  24,  39,  54,  69,  84,  99, 114, 129, 144, 255, 255, 255, 255},
{255, 255,  10,  25,  40,  55,  70,  85, 100, 115, 130, 145, 160, 255, 255, 255},
{255,  11,  26,  41,  56,  71,  86, 101, 116, 131, 146, 161, 176, 255, 255, 255},
{255,  12,  27,  42,  57,  72,  87, 102, 117, 132, 147, 162, 177, 192, 255, 255},
{ 13,  28,  43,  58,  73,  88, 103, 118, 133, 148, 163, 178, 193, 208, 255, 255},
{ 14,  29,  44,  59,  74,  89, 104, 119, 134, 149, 164, 179, 194, 209, 224, 255},
{ 30,  45,  60,  75,  90, 105, 120, 135, 150, 165, 180, 195, 210, 225, 255, 255},
{255,  46,  61,  76,  91, 106, 121, 136, 151, 166, 181, 196, 211, 226, 255, 255},
{255,  62,  77,  92, 107, 122, 137, 152, 167, 182, 197, 212, 227, 255, 255, 255},
{255, 255,  78,  93, 108, 123, 138, 153, 168, 183, 198, 213, 228, 255, 255, 255},
{255, 255,  94, 109, 124, 139, 154, 169, 184, 199, 214, 229, 255, 255, 255, 255},
{255, 255, 255, 110, 125, 140, 155, 170, 185, 200, 215, 230, 255, 255, 255, 255},
{255, 255, 255, 126, 141, 156, 171, 186, 201, 216, 231, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 142, 157, 172, 187, 202, 217, 232, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 158, 173, 188, 203, 218, 233, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 174, 189, 204, 219, 234, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 190, 205, 220, 235, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 206, 221, 236, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 222, 237, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 238, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
};
// }}}
// }}} constants
// {{{ init on startup's
class ZobristKeyInitizer {
public:
    ZobristKeyInitizer(){
        for(int i=0;i<2;++i) {
            for(int j=0;j<256;++j) {
                uint64_t 
                k64 =rand();
                k64^=(uint64_t)rand() << 15;
                k64^=(uint64_t)rand() << 30;
                k64^=(uint64_t)rand() << 45;
                k64^=(uint64_t)rand() << 60;
                zobristKeys[i][j]=k64;
            }
        }
    }
} zobristKeyInitizer;

class CachedThreatsInitizer {
public:
    CachedThreatsInitizer() {
        for(uint o=0;o<512;++o) {
            if(bitsInChar[o&255]+bitsInChar[(o>>8)&255]<=2)
                continue;
            for(uint x=0;x<512;++x) {
                if(x&o) // impossible
                    continue;
                uint c=0,lv=0,msk=0;
                for(int pos=0;pos<5;++pos) {
                    if ((x>>pos)&31) continue; // interrupted
                    uint tmp=(o>>pos)&31;
                    if (!tmp) continue;
                    int left=0,right=0;
                    if (pos==0) left=1;
                    else        left=x>>(pos-1)&1;
                    if (pos==4) right=1;
                    else        right=x>>(pos+5)&1;
                    uint8_t const*S=maskTable[(left<<1)|right][tmp&31]+4;
                    if(tmp==31) {
                        lv|=4;
                    } else {
                        for(int i=0;i<5;++i) {
                            uint8_t v=*S--;
                            if(v==8) {
                                lv|=2;
                                ++c;
                                msk|=1<<(pos+i);
                            } else if(v>=6) {
                                lv|=1;
                                ++c;
                                msk|=1<<(pos+i+9);
                            }
                        }
                    }
                }
                cachedThreats[o][x]=c<<21|lv<<18|msk;
            }
        }
    }
} cachedThreatsInitizer;

// }}}
// {{{ misc functions
inline int bitCount16(uint16_t n) {
    return bitsInChar[n&0xffu]+bitsInChar[(n>>8)&0xffu];
}
inline int bitCount32(uint32_t n) {
    return bitsInChar[n&0xffu]+bitsInChar[(n>>8)&0xffu]+bitsInChar[(n>>16)&0xffu]+bitsInChar[(n>>24)&0xffu];
}

inline char get(int row, int col) {
#ifdef DEBUG_GOMOKU
    if ((board::bX[row]>>col)&1 && (board::bO[row]>>col)&1)
        return '@';
#endif
    if ((board::bX[row]>>col)&1)
        return X;
    else if((board::bO[row]>>col)&1)
        return O;
    return 0;
}
inline char get(Pos p) {
    return get(p.row,p.col);
}
inline int getX(int row, int col) {
    return (board::bX[row]>>col)&1;
}
inline int getO(int row, int col) {
    return (board::bO[row]>>col)&1;
}

inline void set(int row, int col, char value) {
    Pos p(row,col);
#ifdef DEBUG_GOMOKU
    if(get(row,col)) {
        cerr<<"Error: set("<<row<<", "<<col<<", "<<value<<")\n";
    }
#endif
    switch(value) {
    case X:
        board::bX[row]  |= 1<<col;
        board::rbX[col] |= 1<<row;
        board::ltbX[row-col+14] |= 1<<((row+col)>>1);
        board::rtbX[row+col]    |= 1<<((row-col+14)>>1);
        break;
    case O:
        board::bO[row]  |= 1<<col;
        board::rbO[col] |= 1<<row;
        board::ltbO[row-col+14] |= 1<<((row+col)>>1);
        board::rtbO[row+col]    |= 1<<((row-col+14)>>1);
        break;
    }
    board::hash=hash(board::hash,value,p);
    board::steps[board::ply++]=Pos(row,col);
}

inline void setLite(Pos p, char value) {
    int row=p.row, col=p.col;
#ifdef DEBUG_GOMOKU
    if(get(row,col)) {
        cerr<<"Error: setLite("<<p<<", "<<value<<")\n";
    }
#endif
    switch(value) {
    case X:
        board::bX[row]  |= 1<<col;
        board::rbX[col] |= 1<<row;
        board::ltbX[row-col+14] |= 1<<((row+col)>>1);
        board::rtbX[row+col]    |= 1<<((row-col+14)>>1);
        break;
    case O:
        board::bO[row]  |= 1<<col;
        board::rbO[col] |= 1<<row;
        board::ltbO[row-col+14] |= 1<<((row+col)>>1);
        board::rtbO[row+col]    |= 1<<((row-col+14)>>1);
        break;
    }
}

inline void unset(int row, int col, char value) {
#ifdef DEBUG_GOMOKU
    if(!get(row,col)) {
        cerr<<"Error: unset("<<row<<", "<<col<<", "<<value<<")\n";
    }
#endif
    switch(value) {
    case X:
        board::bX[row]  &= ~(1<<col);
        board::rbX[col] &= ~(1<<row);
        board::ltbX[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbX[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    case O:
        board::bO[row]  &= ~(1<<col);
        board::rbO[col] &= ~(1<<row);
        board::ltbO[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbO[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    }
    board::hash=hash(board::hash,value,Pos(row,col));
    --board::ply;
}

inline void unsetLite(Pos p, char value) {
    int row=p.row,
        col=p.col;
#ifdef DEBUG_GOMOKU
    if(!get(row,col)) {
        cerr<<"Error: unsetlite("<<row<<", "<<col<<", "<<value<<")\n";
    }
#endif

    switch(value) {
    case X:
        board::bX[row]  &= ~(1<<col);
        board::rbX[col] &= ~(1<<row);
        board::ltbX[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbX[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    case O:
        board::bO[row]  &= ~(1<<col);
        board::rbO[col] &= ~(1<<row);
        board::ltbO[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbO[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    }
}

#ifdef DEBUG_GOMOKU
void print(Pos hl) {
    int r,c;
    cout<<"   0 1 2 3 4 5 6 7 8 9 a b c d e\n";
    for(r=0;r<15;++r) {
        cout.width(2);
        cout<<"0123456789abcde"[r];
        for(c=0;c<15;++c) {
            cout.width(2);
            char w=get(r, c);
            if(r==hl.row && c==hl.col) {
                if(w) {
                    cout<<"*"<<w;
                } else {
                    cout<<"*";
                }
            } else {
                if(w) {
                    cout<<w;
                } else {
                    cout<<'.';
                }
            }
        }
        cout<<endl;
    }
}
#endif

bool searchOpeningBook(Pos& p) {
    namespace b=board;
    if(b::obNotFound)
        return false;
    int i=b::obIndex, ob4me=b::iFirst?0:1, j;
    bool notFound=false;
    uint16_t const* ps=reinterpret_cast<uint16_t const*>(b::i8Steps);
    for(;i<obSize[ob4me];++i) {
        uint16_t const* pob=reinterpret_cast<uint16_t const*>(openingBook[ob4me][i]);
        notFound=false;
        for(j=0;j<b::ply;++j) {
            if( pob[j]!=ps[j] ) {
                notFound=true;
                break;
            }
        }
        if(notFound) {
            continue;
        } else {
            b::obIndex=i;
            p=Pos(openingBook[ob4me][i][j][0], openingBook[ob4me][i][j][1]);
            if(openingBook[ob4me][i][j+1][0]>=15) { // end
                b::obNotFound=true;
            }
            return true;
        }
    }
    b::obIndex=i;
    b::obNotFound=true;
    return false;
}

void flipH(int8_t (*to)[2], int8_t (*from)[2]) {
    int8_t (*t)[2]=to,(*f)[2]=from;
    for(;**f<15;++f,++t) {
        **t=**f;
        (*t)[1]=14-(*f)[1];
    }
    (*t)[0]=(*t)[1]=15;
}
void rotate90(int8_t (*to)[2], int8_t (*from)[2]) {
    int8_t (*t)[2]=to,(*f)[2]=from;
    for(;**f<15;++f,++t) {
        (*t)[0]=(*f)[1];
        (*t)[1]=14-(*f)[0];
    }
    (*t)[0]=(*t)[1]=15;
}

void initOpeningBook() {
    int i,j,k,l;
    for(i=0;i<2;++i) {
        for(j=0;j<obSize[i];++j) {
            // 1
            k=j;
            l=j+obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);

            // 2
            l+=obSize[i];
            rotate90(openingBook[i][l], openingBook[i][k]);

            // 3
            k=l;
            l+=obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);

            // 4
            l+=obSize[i];
            rotate90(openingBook[i][l], openingBook[i][k]);

            // 5
            k=l;
            l+=obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);

            // 6
            l+=obSize[i];
            rotate90(openingBook[i][l], openingBook[i][k]);

            // 7
            k=l;
            l+=obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);
        }
        obSize[i]*=8;
    }
}
class OpeningBookInitizer {
public:
    OpeningBookInitizer() {
        initOpeningBook();
    }
} openingBookInitizer;

inline void initBoard() {
    namespace b=board;
    memset(b::bX,0,sizeof(b::bX));
    memset(b::rbX,0,sizeof(b::rbX));
    memset(b::ltbX,0,sizeof(b::ltbX));
    memset(b::rtbX,0,sizeof(b::rtbX));

    memset(b::bO,0,sizeof(b::bO));
    memset(b::rbO,0,sizeof(b::rbO));
    memset(b::ltbO,0,sizeof(b::ltbO));
    memset(b::rtbO,0,sizeof(b::rtbX));

    memset(b::mark,0,sizeof(b::mark));
    memset(b::goodMoves,0,sizeof(b::goodMoves));
    memset(b::gmSize,0,sizeof(b::gmSize));
    memset(b::availableMoves,0,sizeof(b::availableMoves));
    memset(b::amSize,0,sizeof(b::amSize));
    memset(b::statistic,0,sizeof(b::statistic));

    memset(b::winLine,0,sizeof(b::winLine));
    memset(b::steps,0,sizeof(b::steps));

    memset(b::i8Steps,0,sizeof(b::i8Steps));
    b::obNotFound=false;
    b::obIndex=0;
    b::iFirst=0;

    b::hash=0;
    b::win=0;
    b::nThreats=0;
    b::ply=0;
    b::vfo=b::vfx=b::vto=b::vtx=0;

    b::startTime=0;
    b::endTime=0;

#ifdef DEBUG_GOMOKU
    b::nodesSearched=0; 
    b::tssNodeSearched=0;
#endif
}

inline void initEverything() {
    initBoard();
    memset(hashTable, 0, sizeof(HashKey)*HTCAPACITY);
}
// }}}
// {{{ core functions
// {{{ mark threats
// {{{ re-mark all
void markThreats() {
    namespace b=board;
    static const uint16_t s[]={0,1,2,4,8,16,32,64,128,-1,-1,-1};
    uint16_t *p16 =b::bO, 
             *xp16=b::bX;
    uint8_t   now=O;
    int       row,col;
    int       turn;
    int       playerIdx=0;
    b::win=0;
    memset(b::mark, 0, sizeof(b::mark));
    b::vto=b::vtx=b::vfo=b::vfx=0;
    for(turn=0; turn<2; ++turn, xp16=b::bO, p16=b::bX, now=X, playerIdx=1) {
        for(row=0;row<15;++row) {
            if (!p16[row]) continue;
            for(col=0;col<11;) {
                uint intr = (xp16[row]>>col)&31; // interrupted
                if(intr) {
                    ++col;
                    continue;
                }
                uint left,right;
                if (col>0) left =xp16[row]>>(col-1)&1;
                else       left =1;
                if (col<10)right=xp16[row]>>(col+5)&1;
                else       right=1;
                uint tmp = p16[row]>>col;
                uint16_t (*m)[5]=b::mark[playerIdx][row]+col;
                uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    col+=S[1];
                    continue;
                default:
                    m[0][1]|=s[*S--];
                    m[1][1]|=s[*S--];
                    m[2][1]|=s[*S--];
                    m[3][1]|=s[*S--];
                    m[4][1]|=s[*S--];
                }
                col+=S[6];
            }
        }
    }
    for(turn=0, p16=b::rbO, xp16=b::rbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, xp16=b::rbO, p16=b::rbX, now=X, playerIdx=1) {
        for(col=0;col<15;++col) {
            if (!p16[col]) continue;
            for(row=0;row<11;) {
                uint intr = (xp16[col]>>row)&31; // interrupted
                if(intr) {
                    ++row;
                    continue;
                }
                uint up,down;
                if (row>0) up=xp16[col]>>(row-1)&1;
                else       up=1;
                if(row<10) down=xp16[col]>>(row+5)&1;
                else       down=1;
                uint tmp = p16[col]>>row;
                uint8_t const *S=maskTable[(up<<1)|down][tmp&31]+4;
                uint16_t (*m)[16][5]=b::mark[playerIdx];
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    row+=S[1];
                    continue;
                default:
                    m[row  ][col][2]|=s[*S--];
                    m[row+1][col][2]|=s[*S--];
                    m[row+2][col][2]|=s[*S--];
                    m[row+3][col][2]|=s[*S--];
                    m[row+4][col][2]|=s[*S--];
                }
                row+=S[6];
            }
        }
    }
    for(turn=0, p16=b::ltbO, xp16=b::ltbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::ltbX, xp16=b::ltbO, now=X, playerIdx=1) {
        int x,y;
        for(y=4;y<25;++y) {
            if(!p16[y]) continue;
            for(x=0;x<11;) {
                if((xp16[y]>>x)&31){ // interrupted
                    ++x;
                    continue;
                }
                row=affineLT[y][x];
                col=row&15;
                row>>=4;
                if(row<0||row>=11||col<0||col>=11) {
                    ++x;
                    continue;
                }
                uint left,right;
                if (row>0&&col>0) left =xp16[y]>>(x-1)&1;
                else     left =1;
                if (row<10&&col<10)right=xp16[y]>>(x+5)&1;
                else     right=1;
                uint tmp = p16[y]>>x;
                uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
                uint16_t (*m)[16][5]=b::mark[playerIdx];
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    x+=S[1];
                    continue;
                default:
                    m[row  ][col  ][3]|=s[*S--];
                    m[row+1][col+1][3]|=s[*S--];
                    m[row+2][col+2][3]|=s[*S--];
                    m[row+3][col+3][3]|=s[*S--];
                    m[row+4][col+4][3]|=s[*S--];
                }
                x+=S[6];
            }
        }
    }
    for(turn=0, p16=b::rtbO, xp16=b::rtbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::rtbX, xp16=b::rtbO, now=X, playerIdx=1) {
        int x,y;
        for(y=4;y<25;++y) {
            if(!p16[y]) continue;
            for(x=0;x<11;) {
                if((xp16[y]>>x)&31){ // interrupted
                    ++x;
                    continue;
                }
                row=affineRT[y][x];
                col=row&15;
                row>>=4;
                if(row<0||row>=11||col<4||col>=15) {
                    ++x;
                    continue;
                }
                uint left,right;
                if (row<10&&col>4) left=xp16[y]>>(x+5)&1;
                else     left =1;
                if (row>0&&col<14)right=xp16[y]>>(x-1)&1;
                else     right=1;
                uint tmp = p16[y]>>x;
                uint8_t const *S=maskTable[(left)|(right<<1)][tmp&31]+4;
                uint16_t (*m)[16][5]=b::mark[playerIdx];
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    x+=S[1];
                    continue;
                default:
                    m[row  ][col  ][4]|=s[*S--];
                    m[row+1][col-1][4]|=s[*S--];
                    m[row+2][col-2][4]|=s[*S--];
                    m[row+3][col-3][4]|=s[*S--];
                    m[row+4][col-4][4]|=s[*S--];
                }
                x+=S[6];
            }
        }
    }
}
// }}} re-mark all
// {{{ update 4 lines
void updateLines(Pos p) {
    namespace b=board;
    static const uint16_t s[]={0,1,2,4,8,16,32,64,128,-1,-1,-1};
    uint16_t *p16 =b::bO, 
             *xp16=b::bX;
    uint8_t   now=O;
    int       row=p.row,col=p.col;
    int       turn;
    int       playerIdx=0;

    // init...
    b::win=0;
    b::vto=b::vtx=b::vfo=b::vfx=0;
    for(row=p.row, col=0; col<15; ++col) {
        b::mark[0][row][col][0] =
        b::mark[1][row][col][0] =
        b::mark[0][row][col][1] = 
        b::mark[1][row][col][1] = 0;
    }
    for(row=0, col=p.col; row<15; ++row) {
        b::mark[0][row][col][0] =
        b::mark[1][row][col][0] =
        b::mark[0][row][col][2] = 
        b::mark[1][row][col][2] = 0;
    }
    if(p.row>p.col) {
        row = p.row-p.col;
        col = 0;
        for(;row<15;++row, ++col) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][3] =
            b::mark[1][row][col][3] = 0;
        }
    } else {
        row = 0;
        col = p.col-p.row;
        for(;col<15;++row, ++col) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][3] =
            b::mark[1][row][col][3] = 0;
        }
    }
    row = p.row, col=p.col;
    if(row+col<14) {
        col+=row;
        row=0;
        for(;col>=0; --col, ++row) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][4] = 
            b::mark[1][row][col][4] = 0;
        }
    } else {
        row+=col;
        row-=14;
        col=14;
        for(;row<15; --col, ++row) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][4] = 
            b::mark[1][row][col][4] = 0;
        }
    }

    for(turn=0; turn<2; ++turn, xp16=b::bO, p16=b::bX, now=X, playerIdx=1) {
        row=p.row;
        if (!p16[row]) continue;
        for(col=0;col<11;) {
            uint intr = (xp16[row]>>col)&31; // interrupted
            if(intr) {
                ++col;
                continue;
            }
            uint left,right;
            if (col>0) left =xp16[row]>>(col-1)&1;
            else       left =1;
            if (col<10)right=xp16[row]>>(col+5)&1;
            else       right=1;
            uint tmp = p16[row]>>col;
            uint16_t (*m)[5]=b::mark[playerIdx][row]+col;
            uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                col+=S[1];
                continue;
            default:
                m[0][1]|=s[*S--];
                m[1][1]|=s[*S--];
                m[2][1]|=s[*S--];
                m[3][1]|=s[*S--];
                m[4][1]|=s[*S--];
            }
            col+=S[6];
        }
    }
    for(turn=0, p16=b::rbO, xp16=b::rbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, xp16=b::rbO, p16=b::rbX, now=X, playerIdx=1) {
        col=p.col;
        if (!p16[col]) continue;
        for(row=0;row<11;) {
            uint intr = (xp16[col]>>row)&31; // interrupted
            if(intr) {
                ++row;
                continue;
            }
            uint up,down;
            if (row>0) up=xp16[col]>>(row-1)&1;
            else       up=1;
            if(row<10) down=xp16[col]>>(row+5)&1;
            else       down=1;
            uint tmp = p16[col]>>row;
            uint8_t const *S=maskTable[(up<<1)|down][tmp&31]+4;
            uint16_t (*m)[16][5]=b::mark[playerIdx];
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                row+=S[1];
                continue;
            default:
                m[row  ][col][2]|=s[*S--];
                m[row+1][col][2]|=s[*S--];
                m[row+2][col][2]|=s[*S--];
                m[row+3][col][2]|=s[*S--];
                m[row+4][col][2]|=s[*S--];
            }
            row+=S[6];
        }
    }
    row=p.row, col=p.col;
    for(turn=0, p16=b::ltbO, xp16=b::ltbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::ltbX, xp16=b::ltbO, now=X, playerIdx=1) {
        int x,y;
        y=row-col+14;
        if(y<4 || y>=25)
            continue;
        if(!p16[y]) continue;
        for(x=0;x<11;) {
            if((xp16[y]>>x)&31){ // interrupted
                ++x;
                continue;
            }
            row=affineLT[y][x];
            col=row&15;
            row>>=4;
            if(row<0||row>=11||col<0||col>=11) {
                ++x;
                continue;
            }
            uint left,right;
            if (row>0&&col>0) left =xp16[y]>>(x-1)&1;
            else     left =1;
            if (row<10&&col<10)right=xp16[y]>>(x+5)&1;
            else     right=1;
            uint tmp = p16[y]>>x;
            uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
            uint16_t (*m)[16][5]=b::mark[playerIdx];
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                x+=S[1];
                continue;
            default:
                m[row  ][col  ][3]|=s[*S--];
                m[row+1][col+1][3]|=s[*S--];
                m[row+2][col+2][3]|=s[*S--];
                m[row+3][col+3][3]|=s[*S--];
                m[row+4][col+4][3]|=s[*S--];
            }
            x+=S[6];
        }
    }
    row=p.row, col=p.col;
    for(turn=0, p16=b::rtbO, xp16=b::rtbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::rtbX, xp16=b::rtbO, now=X, playerIdx=1) {
        int x,y;
        y=row+col;
        if(y<4 || y>=25)
            continue;
        if(!p16[y]) continue;
        for(x=0;x<11;) {
            if((xp16[y]>>x)&31){ // interrupted
                ++x;
                continue;
            }
            row=affineRT[y][x];
            col=row&15;
            row>>=4;
            if(row<0||row>=11||col<4||col>=15) {
                ++x;
                continue;
            }
            uint left,right;
            if (row<10&&col>4) left=xp16[y]>>(x+5)&1;
            else     left =1;
            if (row>0&&col<14)right=xp16[y]>>(x-1)&1;
            else     right=1;
            uint tmp = p16[y]>>x;
            uint8_t const *S=maskTable[(left)|(right<<1)][tmp&31]+4;
            uint16_t (*m)[16][5]=b::mark[playerIdx];
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                x+=S[1];
                continue;
            default:
                m[row  ][col  ][4]|=s[*S--];
                m[row+1][col-1][4]|=s[*S--];
                m[row+2][col-2][4]|=s[*S--];
                m[row+3][col-3][4]|=s[*S--];
                m[row+4][col-4][4]|=s[*S--];
            }
            x+=S[6];
        }
    }
}
// }}} update 4 lines
// }}}
// {{{ generate moves
// call me after markThreats
void genMoves(int depth, char who) {
    namespace b=board;
    int    r,c;
    uint16_t (*mark)[16][5]=b::mark[who==O?0:1];
    uint16_t (*markopp)[16][5]=b::mark[who==O?1:0];

    memset(b::gmSize[depth], 0, sizeof(b::gmSize[depth]));
    b::amSize[depth]=0;
    memset(b::statistic[0][depth], 0, sizeof(b::statistic[0][depth]));
    memset(b::statistic[1][depth], 0, sizeof(b::statistic[1][depth]));

    Threat *moves=b::availableMoves[depth];
    for(r=0;r<15;++r) {
        for(c=0;c<15;++c) {
            uint16_t *m=mark[r][c];
            m[0] = m[1]|m[2]|m[3]|m[4];
            Threat t={ Pos(r,c), m[0] };
            if(m[0] & 224) { // 6,7,8. ie. 4 or 5
                b::goodMoves[depth][3][b::gmSize[depth][3]++] = t;
            } else if(m[0] & 24) { // 4,5
                b::goodMoves[depth][2][b::gmSize[depth][2]++] = t;
            } 
#if 0 // ignore them
            else if(m[0] & 6) { // 2,3
                b::goodMoves[depth][1][b::gmSize[depth][1]++] = t;
            } else if(m[0]) { // 1
                b::goodMoves[depth][0][b::gmSize[depth][0]++] = t;
            }
#endif
            uint16_t *mopp=markopp[r][c];
            mopp[0] = mopp[1]|mopp[2]|mopp[3]|mopp[4];
            t.lvl = m[0];
            t.lvl<<=1;
            t.lvl+= mopp[0];
            if (t.lvl>0) {
                moves[b::amSize[depth]++] = t;
            }

            // statistic
            ++b::statistic[0][depth][highestBit[m[0]]];
            ++b::statistic[1][depth][highestBit[mopp[0]]];
        }
    }
    std::sort(moves, moves+b::amSize[depth]);
}
// }}}
// {{{ VCF finder
#if 1
// {{{ mark threat briefly - see threats in 8 lines only
// return: 
//  ( n directions ) <<4 | ( max threat level )
// arg threats:
//  threats[0] holds the size of array
//  threats[1 .. n] holds the pos of newly formed threats
uint8_t markThreatsBriefly(Pos p, char who, uint8_t* t4, uint8_t* t3) {
    namespace b=board;
    int      row=p.row,
             col=p.col,
             i,tmp,dx,dy;
    uint16_t o=b::bO[row],
             x=b::bX[row];
    uint16_t lv=0,c4=0,c3=0,
             idxO=(col>=4?o>>(col-4):o<<(4-col))&511,
             idxX=(col>=4?x>>(col-4):x<<(4-col))&511;
    uint32_t n,dir=0;

    // horizontal
    n=who==O?
        cachedThreats[idxO][idxX]:
        cachedThreats[idxX][idxO];
    if(n) {
        for(i=0;i<9;++i) {
            tmp=col-4+i;
            if((n>>i)&1 && tmp>=0 && tmp<15) {
                t4[++c4]=row<<4 | tmp;
            }
        }
        for(;i<18;++i) {
            tmp=col-4+i-9;
            if((n>>i)&1 && !((n>>(i-9))&1) && tmp>=0 && tmp<15) {
                t3[++c3]=row<<4 | tmp;
            }
        }
        ++dir;
        lv|=(n>>18)&7;
    }

    // vertical
    o=b::rbO[col];
    x=b::rbX[col];
    idxO=(row>=4?o>>(row-4):o<<(4-row))&511;
    idxX=(row>=4?x>>(row-4):x<<(4-row))&511;
    n=who==O?
        cachedThreats[idxO][idxX]:
        cachedThreats[idxX][idxO];
    if(n) {
        for(i=0;i<9;++i) {
            tmp = row-4+i;
            if((n>>i)&1 && tmp>=0 && tmp<15) {
                t4[++c4]=tmp<<4 | col;
            }
        }
        for(;i<18;++i) {
            tmp = row-4+i-9;
            if((n>>i)&1 && !((n>>(i-9))&1) && tmp>=0 && tmp<15) {
                t3[++c3]=tmp<<4 | col;
            }
        }
        ++dir;
        lv|=(n>>18)&7;
    }

    // \ diagnal
    dx=(row+col)>>1,dy=row-col+14;
    if(dy>=4 && dy<25) {
        o=b::ltbO[dy];
        x=b::ltbX[dy];
        idxO=(dx>=4?o>>(dx-4):o<<(4-dx))&511;
        idxX=(dx>=4?x>>(dx-4):x<<(4-dx))&511;
        n=who==O?
            cachedThreats[idxO][idxX]:
            cachedThreats[idxX][idxO];
        if(n) {
            for(i=0;i<9;++i) {
                tmp = dx-4+i;
                if((n>>i)&1 && affineLT[dy][tmp]!=255) {
                    t4[++c4]=affineLT[dy][tmp];
                }
            }
            for(;i<18;++i) {
                tmp = dx-4+i-9;
                if((n>>i)&1 && !((n>>(i-9))&1) && affineLT[dy][tmp]!=255) {
                    t3[++c3]=affineLT[dy][tmp];
                }
            }
            ++dir;
            lv|=(n>>18)&7;
        }
    }

    // / diagnal
    dx=(row-col+14)>>1,dy=row+col;
    if(dy>=4 && dy<25) {
        o=b::rtbO[dy];
        x=b::rtbX[dy];
        idxO=(dx>=4?o>>(dx-4):o<<(4-dx))&511;
        idxX=(dx>=4?x>>(dx-4):x<<(4-dx))&511;
        n=who==O?
            cachedThreats[idxO][idxX]:
            cachedThreats[idxX][idxO];
        if(n) {
            for(i=0;i<9;++i) {
                tmp = dx-4+i;
                if((n>>i)&1 && affineRT[dy][tmp]!=255) {
                    t4[++c4]=affineRT[dy][tmp];
                }
            }
            for(;i<18;++i) {
                tmp = dx-4+i-9;
                if((n>>i)&1 && !((n>>(i-9))&1) && affineRT[dy][tmp]!=255) {
                    t3[++c3]=affineRT[dy][tmp];
                }
            }
            ++dir;
            lv|=(n>>18)&7;
        }
    }

    t4[0]=c4;
    t3[0]=c3;
    return dir<<4|lv;
}
// }}}
// {{{ vcf
struct Threat4 {
    Pos attack;
    Pos defend;
};
class AutoSet {
    Pos p;
    char whoami;
    AutoSet(AutoSet const&);
    AutoSet& operator=(AutoSet const&);
public:
    AutoSet(Pos p, char whoami):
        p(p),
        whoami(whoami)
    {
        setLite(p, whoami);
    }
    ~AutoSet()
    {
        unsetLite(p, whoami);
    }
};

int tss(int nodeLimit, char whoami, uint8_t *t3, int  nt3, Pos* whereToGo=0);

// return: 0                 if no vcf exists
//         steps remained    if vcf exists
int hasVCF(char whoami, Threat4* threats, int len, int nodeLimit, Pos& whereToGo) {
    namespace b=board;
    if(nodeLimit<0) {
        dbg("hasVCF : reached limit\n");
        return 0;
    }
    dexec(++b::tssNodeSearched);
    uint8_t t4[16],t3[16],m;
    uint8_t ct4[16],ct3[16];
    char opp=X+O-whoami;
    int  res=0;
    bool chain=false;
    for(;;) {
        Threat4 t=*threats;
        ++threats;
        if(--len<0)
            break;
        if(get(t.attack) || get(t.defend))
            continue;
        for(int j=0;j<2;++j) {
            AutoSet att(t.attack, whoami);
            AutoSet def(t.defend, opp);
            chain=false;
            if(--nodeLimit<0) {
                return 0;
            }
            m=markThreatsBriefly(t.attack, whoami, t4, t3);
            if(m&4) {
                whereToGo=t.attack;
                return 1;
            }
            if(t4[0]>0) {
                if(markThreatsBriefly(t.defend, opp, ct4, ct3)&4) {
                    goto badLuck;
                } else {
                    whereToGo=t.attack;
                    return 3;
                }
            }
            if(t3[0]) {
                if(t3[0]!=2) {
                    uint8_t check=markThreatsBriefly(t.defend, opp, ct4, ct3);
                    int r;
                    if(check&4)
                        goto badLuck;
                    if(ct4[0] && !(markThreatsBriefly(Pos(ct4[1]), whoami, ct4, ct3)&6))
                        goto badLuck;
                    r=tss(nodeLimit,whoami,t3+1,t3[0]);
                    if(r>0) {
                        dbg("Yeah!\n");
                        whereToGo=t.attack;
                        return r+2;
                    }
                } else {
                    markThreatsBriefly(Pos(t3[1]), whoami, ct4, ct3);
                    if(ct4[0]>0 && (
                      (ct4[1]==t3[2]) || 
                      (ct4[0]>=2 && ct4[2]==t3[2]) || 
                      (ct4[0]>=3 && ct4[3]==t3[2]) )) {
                        --threats;
                        threats->attack=Pos(t3[1]);
                        threats->defend=Pos(t3[2]);
                        ++threats;
                        chain=true;
                    }
                }
            }
            if(chain)
                res=hasVCF(whoami, threats-1, len+1, nodeLimit, whereToGo);
            else
                res=hasVCF(whoami, threats,   len,   nodeLimit, whereToGo);
            if(res) {
                if(markThreatsBriefly(t.defend, opp, ct4, ct3)&4)
                    goto badLuck;
                if(ct4[0] && !(markThreatsBriefly(Pos(ct4[1]), whoami, ct4, ct3)&6))
                    goto badLuck;
                whereToGo=t.attack;
                return res+2;
            }
badLuck:
            std::swap(t.attack, t.defend);
        }
        *(threats-1)=t;
    }
    return 0;
}

int tss(int nodeLimit, char whoami, uint8_t* t3, int nt3, Pos* whereToGo) {
    Threat4 threats[128];
    uint8_t t4[16],t3_[16],m;
    int    threatCount=0;
    bool   alreadyIn;
    Pos    tmp;
    for(int i=0;i<nt3;++i) {
        Pos p(t3[i]);
        alreadyIn=false;
        for(int j=0;j<threatCount;++j) {
            if(p==threats[j].attack || p==threats[j].defend) {
                alreadyIn=true;
                break;
            }
        }
        if(alreadyIn)
            continue;
                
        AutoSet as(p, whoami);
        m=markThreatsBriefly(p, whoami, t4, t3_);
        if(t4[0]!=1) {
            if(t4[0]>1) {
                dbg("@_@ double-threat already exists!\n");
                if(whereToGo)
                    *whereToGo=p;
                return 3;
            }
        } else {
            threats[threatCount].attack=p;
            threats[threatCount].defend=Pos(t4[1]);
            ++threatCount;
        }
    }
    int res=hasVCF(whoami, threats, threatCount, nodeLimit, tmp);
    if(whereToGo!=0)
        *whereToGo=tmp;
    return res;
}
// }}}
#endif
// }}} VCF
// {{{ alpha-beta
// {{{ score
int score(uint16_t* mark, bool attacker) {
    static int const vTable[2][9] = { // 0 for me, 1 for opp
    //   1  2  3  4   5   6   7   8
        {0, 2, 7, 20, 80, 100,990,10000},
        {0, 1, 5, 16, 45, 98, 580,9000}
    };
    int res=0,t=0;
    int const *v=attacker?vTable[0]:vTable[1];
    int t3=0;

    if(mark[0]&96) { // has 4
        t3=t=0;
        if(mark[1]&96)++t;
        else if(mark[1]&24)++t3;
        if(mark[2]&96)++t;
        else if(mark[2]&24)++t3;
        if(mark[3]&96)++t;
        else if(mark[3]&24)++t3;
        if(mark[4]&96)++t;
        else if(mark[4]&24)++t3;
        if(t>1) { // double 4
            return attacker?10000:9000;
        } else if(t3) { // 4-3
            return attacker?9000:6000;
        }
    } else if(mark[0]&24) { // has open/broken - none blocked 3
        t=0;
        if(mark[1]&24)++t;
        if(mark[2]&24)++t;
        if(mark[3]&24)++t;
        if(mark[4]&24)++t;
        if(t>1) { // double 3
            return attacker?1000:800;
        }
    }

    res=v[highestBit[mark[1]]];
    t  =v[highestBit[mark[2]]];
    if(t&&res) {
        res+=t;
        res<<=1;
    } else {
        res+=t;
    }
    t  =v[highestBit[mark[3]]];
    if(t&&res) {
        res+=t;
        res<<=1;
    } else {
        res+=t;
    }
    t  =v[highestBit[mark[4]]];
    if(t&&res) {
        res+=t;
        res<<=1;
    } else {
        res+=t;
    }
    return res;
}
// }}}
// {{{ evaluate
int evaluate(int depth,char whoami) {
    using  board::mark;
    int    size=board::amSize[depth], me=whoami==O?0:1, opp, res=0;
    Threat *moves=board::availableMoves[depth];
    uint16_t *m;
    opp=1-me;

    for(int i=0;i<size;++i) {
        m=mark[me][moves[i].p.row][moves[i].p.col];
        res+=score(m, true);
        m=mark[opp][moves[i].p.row][moves[i].p.col];
        res-=score(m, false);
    }
    return res;
}
// }}} evaluate
int alphaBeta(int depth,int alpha,int beta,char whoami) {
    namespace b=board;
    dexec(++b::nodesSearched);
    HashKey const*key=htget(b::hash);
    int res=0;
    if(key&&key->depth>=depth) {
        res=key->v;
        if(res>WIN_VALUE) {
            res-=b::ply;
        } else if(res<-WIN_VALUE) {
            res+=b::ply;
        }
        switch(key->type) {
        case 0: // exact
            return res; 
            break;
        case 1: // alpha
            if(res<=alpha) return alpha;
            break;
        case 2: // beta
            if(res>=beta) return beta;
            break;
        }
    }
    res=0;
    int val,type=3;
    char opp=(whoami==O?X:O), foundPv=0;
    int const* statistic=b::statistic[0][depth],
             * oppStatistic=b::statistic[1][depth];

    // Null-Move Heuristic
    if (depth>=4&&b::steps[b::ply-1].row!=15) {
        b::steps[b::ply++]=Pos(15,15);
        b::hash^=0xfedcba9876543210ull;
        val=-alphaBeta(depth-3,-beta,std::min(-beta+1,-alpha),opp);
        b::hash^=0xfedcba9876543210ull;
        --b::ply;
        if(val>=beta) {
            return beta;
        }
    }
    // markThreats();
    if (b::win) {
        res=(whoami==b::win?MAX_VALUE:-MAX_VALUE);
        type=0;
        goto thatsit;
    } 
    genMoves(depth,whoami);
    type=0;
    if(statistic[7]) {           // has 4 already
        res=MAX_VALUE-1-b::ply;
        goto direct;
    } else if(statistic[6] &&    // can form a open 4 next move
             !oppStatistic[7]){  // cannnot defend
        res=MAX_VALUE-3-b::ply;
        goto direct;
    } else if(oppStatistic[5] && oppStatistic[7] ) {
        res=-MAX_VALUE+4+b::ply;
        goto direct;
    }

#if 1
    if(!oppStatistic[7]) {
        uint8_t *t3=b::tssStack[depth][0], nt3=0;
        Threat  *trt=b::goodMoves[depth][3];
        Pos     whereToGo;
        for(;nt3<b::gmSize[depth][3];++nt3) {
            t3[nt3]=trt[nt3].p.u8();
        }
        res=tss(64, whoami, t3, nt3, &whereToGo);
        if(res>0) {
#ifdef DEBUG_GOMOKU
            cout<<"Found TSS within "<<res<<" steps! (i am "<<whoami<<")\n";
            print(whereToGo);
            cout<<endl;
#endif
            res=-res-b::ply;
            res+=MAX_VALUE;
            goto direct;
        }
    }
#endif
    if (depth==0) {
        type=0;
        res=evaluate(0,whoami);
        goto thatsit;
    }
    for(int i=0,I=b::amSize[depth];i<I;++i) {
        if (clock()>b::endTime) {
            return beta+1;
        }

        Pos p(b::availableMoves[depth][i].p);
        set(p.row,p.col,whoami);
        updateLines(p);
        if(foundPv) {
            val=-alphaBeta(depth-1,-alpha-1,-alpha,opp);
            if((val>alpha)&&(val<beta)) {
                val=-alphaBeta(depth-1,-beta,-alpha,opp);
            }
        } else {
            val=-alphaBeta(depth-1,-beta,-alpha,opp);
        }
        unset(p.row,p.col,whoami);
        updateLines(p);

        if (val>=beta) {
            res=beta;
            type=2;
            goto thatsit;
        } else if (val>alpha) {
            alpha=val;
            foundPv=true;
        }
    }
    res=alpha;
    type=1;

thatsit:
    val=res;
    if(res>WIN_VALUE) {
        --val;
    } else if(res<-WIN_VALUE) {
        ++val;
    }
    htupdate(b::hash, type, depth, val);
    return val;

direct:
    val=res;
    if(res>WIN_VALUE) {
        val += b::ply;
    } else if(res<-WIN_VALUE) {
        val -= b::ply;
    }
    htupdate(b::hash, type, depth, val);
    
    return res;
}
// }}}
// {{{ make move
bool gt(std::pair<int,Pos>const&a,std::pair<int,Pos>const&b){
    return a.first>b.first;
}

Pos move() {
    namespace b=board;
    b::startTime=clock();
    b::endTime=b::startTime+timeLimit;
    std::pair<int,Pos> arr2[256];
    std::pair<int,Pos> *ia2=arr2,*eia2=arr2;
    int alpha=-MAX_VALUE,beta=MAX_VALUE,val;
    Pos bestMove(15,15),coor;
    int depth=1;
    if(searchOpeningBook(bestMove)) {
        dbg("Found in openingBook!\n");
        goto thatsit;
    }
    markThreats();
    genMoves(31,O);
#ifdef DEBUG_GOMOKU
    b::nodesSearched=0;
    b::tssNodeSearched=0;
#endif
    if (b::win) {
        return bestMove;
    }
    if(!b::statistic[1][31][7] && b::gmSize[31][3]) {
        uint8_t *t3=b::tssStack[31][0], nt3=0;
        Threat  *trt=b::goodMoves[31][3];
        for(;nt3<b::gmSize[31][3];++nt3) {
            t3[nt3]=trt[nt3].p.u8();
        }
        int res=tss(512, O, t3, nt3, &bestMove);
        if(res>0) {
#ifdef DEBUG_GOMOKU
            alpha=WIN_VALUE+1;
            dbg("Found TSS within %d steps!\n",res);
            print(bestMove);
            cout<<endl;
#endif
            goto thatsit;
        }
    }


    bestMove=Pos(b::availableMoves[31][0].p);
    for(depth=1;depth<16;++depth) {
        ia2=eia2=arr2;
        bool foundPv=false;
        for(int i=0,I=b::amSize[31];i<I;++i) {
            coor=b::availableMoves[31][i].p;
            set(coor.row,coor.col,O);
            updateLines(coor);
            if(foundPv) {
                val=-alphaBeta(depth-1,-alpha-1,-alpha,X);
                if(val>alpha&&val<beta) {
                    val=-alphaBeta(depth-1,-beta,-alpha,X);
                }
            } else {
                val=-alphaBeta(depth-1,-beta,-alpha,X);
            }
            unset(coor.row,coor.col,O);
            updateLines(coor);
            if (val>alpha) {
                alpha=val;
                bestMove=coor;
                foundPv=true;
            }
            *eia2++=std::make_pair(val,coor);
        }
        if(clock()>b::endTime) 
            break;
        std::sort(ia2,eia2,gt);
        for(b::amSize[31]=0;ia2!=eia2;++ia2) {
            if(ia2->first<=-WIN_VALUE)
                continue;
            b::availableMoves[31][b::amSize[31]++].p=ia2->second;
        }
        if(b::amSize[31]>10) {
            b::amSize[31]-=b::amSize[31]/6;
        }
    }

thatsit:
#ifdef DEBUG_GOMOKU
    if(alpha>WIN_VALUE)
        cout<<"I will win!"<<endl;
    else if(alpha<-WIN_VALUE)
        cout<<"Bad luck.."<<endl;
    cout<<"\n["<<(int)bestMove.col<<", "<<(int)bestMove.row<<"]\tAB: "<<b::nodesSearched<<" nodes; tss: "<<b::tssNodeSearched<<" nodes; max depth: "<<depth<<"; total time: "<<clock()-b::startTime<<"ms"<<endl;
#endif
    b::i8Steps[b::ply][0]=bestMove.row;
    b::i8Steps[b::ply][1]=bestMove.col;
    set(bestMove.row,bestMove.col,O);
    updateLines(bestMove);
    return bestMove;
}
// }}}
// }}} core functions
// {{{ PKU contest interface
void initAI() {
    char tmp[64];
    int  m,row,col;
    if(scanf("%d",&m)!=1)
        fprintf(stderr,"WTF\n");
    initEverything();
    if(scanf("%s%d%d",tmp,&col,&row)!=3)
        fprintf(stderr,"WTF\n");
    if(m == 2) {
        set(row, col, X);
        board::i8Steps[0][0]=row;
        board::i8Steps[0][1]=col;
        board::iFirst=false;
    } else if(m == 1) {
        board::iFirst=true;
    }
}

inline int random(int a, int b) {
    return a+rand()%(b-a+1);
}

void fightBack() {
    Pos p=move();
    printf("%d %d\n",p.col,p.row);
    fflush(stdout);
}

#ifndef USING_LINUX
int main() {
    char cmd[64];
    srand(time(0));
    while(scanf("%s",cmd)!=-1) {
        int row,col;
        if(!strcmp(cmd,"[START]")) {
            initAI();
            fightBack();
        } else if(!strcmp(cmd,"[PUT]")) {
            if(scanf("%d%d",&col,&row)!=2) {
                fprintf(stderr,"WTF\n");
            }
            board::i8Steps[board::ply][0]=row;
            board::i8Steps[board::ply][1]=col;
            set(row,col,X);
            fightBack();
        }
    }
    return 0;
}
#endif
// }}} interface

// vi:ts=4:et:sts=4:sw=4:foldmethod=marker:foldmarker={{{,}}}:foldlevel=0

Show details Hide details

Change log

r9 by iamyuguo on Jan 5, 2011 Diff

added updateLines function, which is 6
times faster than markThreats

Go to:

Project members, sign in to write a code review

Older revisions

r8 by iamyuguo on Jan 2, 2011 Diff

silly as before

r4 by iamyuguo on Dec 31, 2010 Diff

that's it

All revisions of this file

File info

Size: 79098 bytes, 2172 lines

View raw file