search: fixed a bug in NULL move pruning

[owl.git] / trans.c

/*
 *      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 2 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, write to the Free Software
 *      Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
#include "common.h"
#include "board.h"
#include "engine.h"
#include "trans.h"

uint64_t pawn_hash_mask;
uint64_t main_hash_mask;

struct pawn_hash_entry_t *pawn_hash[2];
struct main_hash_entry_t *main_hash;

uint16_t hashtable_age;

int
initialize_main_hashtable(void)
{
        int max_elements;

        main_hash = 0;

        if (!e.main_hash_size || !e.main_hash_enabled)
                return 0;

        main_hash_mask = 0;

        max_elements = (e.main_hash_size * 1024 * 1024 / 4) / \
                sizeof(struct main_hash_entry_t);

        /* calculate hashmask */
        while (max_elements >>= 1)
                main_hash_mask = (main_hash_mask << 1) | 1;

        /* allocate memory */
        if (!(main_hash = malloc(4 * (main_hash_mask + 1) * \
                        sizeof(struct main_hash_entry_t))))
                return -1;

#ifdef CONSOLE_DEBUG
        fprintf(stdout, "Allocated main hashtable: %lluk entries, %lluMB\n",
                        (4 * main_hash_mask) >> 10, (4 * main_hash_mask *
                                sizeof(struct main_hash_entry_t)) >> 20);
#endif

        return 0;
}

int
initialize_pawn_hashtable(void)
{
        int max_elements;

        pawn_hash[0] = 0;
        pawn_hash[1] = 0;

        if (!e.pawn_hash_size || !e.pawn_hash_enabled)
                return 0;

        pawn_hash_mask = 0;
        pawn_hash[WHITE] = 0;
        pawn_hash[BLACK] = 0;

        max_elements = (e.pawn_hash_size * 1024 * 1024 / 2) / \
                sizeof(struct pawn_hash_entry_t);

        /* calculate hashmask */
        while (max_elements >>= 1)
                pawn_hash_mask = (pawn_hash_mask << 1) | 1;

        /* allocate memory */
        if (!(pawn_hash[WHITE] = malloc((pawn_hash_mask + 1) * \
                        sizeof(struct pawn_hash_entry_t))))
                return -1;
        if (!(pawn_hash[BLACK] = malloc((pawn_hash_mask + 1) * \
                        sizeof(struct pawn_hash_entry_t)))) {
                free(pawn_hash[WHITE]);
                return -1;
        }

#ifdef CONSOLE_DEBUG
        fprintf(stdout, "Allocated pawn hashtable: %lluk entries, %lluMB\n",
                        (2 * pawn_hash_mask) >> 10, (2 * pawn_hash_mask *
                                sizeof(struct pawn_hash_entry_t)) >> 20);
#endif
        return 0;
}

int 
hashtable_get(int side, int depth, int ply, int *move, int *score)
{
        int i;
        int found;
        int entry_depth;
        struct main_hash_entry_t *mhe;
   
        found = FALSE;
        mhe = main_hash + (brd.hash_key & main_hash_mask) * 4;

        for (i = 0; i < 4; i++, mhe++) {
                if (mhe->key == brd.hash_key) {
                        found = TRUE;
                        break;
                }
        }

        if (!found) {
                *move = 0;
                return INVALID;
        }

        entry_depth = (mhe->mdf >> 21) & 0xFF;
        *move = mhe->mdf & 0x1FFFFF;

        if (entry_depth < depth)
                return INVALID;

        *score = mhe->score;

        if (SCORE_IS_MATE(*score))
                *score += *score > 0 ? -ply : ply;

        return mhe->mdf >> 29;
}

void 
hashtable_put(int side, int depth, int ply, int flag, int move, int score)
{
        int i;
        int entry_depth;
        int replace_depth;
        struct main_hash_entry_t *mhe;
        struct main_hash_entry_t *replace;

        mhe = main_hash + (brd.hash_key & main_hash_mask) * 4;
        replace = mhe;

        for (i = 0; i < 4; i++, mhe++) {
                if (mhe->key == brd.hash_key) {
                        mhe->mdf = move | (depth << 21) | (flag << 29);
                        mhe->score = score;

                        if (SCORE_IS_MATE(score))
                                mhe->score += score > 0 ? ply : -ply;
                        return;
                }
                
                entry_depth = (mhe->mdf >> 21) & 0xFF;
                replace_depth = (replace->mdf >> 21) & 0xFF;

                if (replace->age == hashtable_age) {
                        if (mhe->age != hashtable_age || entry_depth < replace_depth)
                                replace = mhe;
                } else if (mhe->age != hashtable_age && entry_depth < replace_depth)
                        replace = mhe;
        }

        replace->key = brd.hash_key;
        replace->score = score;
        replace->mdf = move | (depth << 21) | (flag << 29);

        if (SCORE_IS_MATE(score))
                replace->score += score > 0 ? ply : -ply;
}

void
free_main_hashtable(void)
{
        free(main_hash);
}

void
free_pawn_hashtable(void)
{
        free(pawn_hash[WHITE]);
        free(pawn_hash[BLACK]);
}

/* clear hashtables */
void
clear_main_hashtable(void)
{
        hashtable_age = 0;

        if (main_hash)
                memset(main_hash, 0, 4 * (main_hash_mask + 1) * \
                        sizeof(struct main_hash_entry_t));
}

void
clear_pawn_hashtable(void)
{
        if (pawn_hash[WHITE])
                memset(pawn_hash[WHITE], 0, (pawn_hash_mask + 1) * \
                        sizeof(struct pawn_hash_entry_t));
        if (pawn_hash[BLACK])
                memset(pawn_hash[BLACK], 0, (pawn_hash_mask + 1) * \
                        sizeof(struct pawn_hash_entry_t));
}