8

Just finished writing customizing a chess engine by basically adding a bitboard to the freely availably tscp engine. Now I'm testing it out in winboard and notice that often the two machines will play the same game multiple times in a match. I'd like to add some variety to the games by at least having it pick equal moves at random. I'm just using alpha-beta search with simple move ordering. I'm thinking about just adding a small random number to the leaf nodes to break ties but I don't really like this solution because some of the smaller bonuses that the evaluation function uses are 3-5 centipawns. So I don't have enough "room" for random number to break the ties.

my other thought was to have the engine pick randomly which move to keep when it found an evaluation == alpha. I don't really like this because I suspect it favors moves ordered last in the search.

Question is how can I pick from the equal scoring leaf nodes randomly? and also evenly?

7

Note:

It's a good idea for your engine be deterministic. There is no reason to select a move randomly. You would only do it to lower your engine strength. If you make your engine non-deterministic, you will find it very hard to debug and reproduce a bug. My recommendation is not to do it.

You shouldn't modify your engine. You may want to use an opening book, and pick a line randomly. Many chess GUI can do that, for example, the CuteChess software. Arena GUI can do also that.

But if you insist:

Let's take a look at the Stockfish source code.

 Move Skill::pick_best(size_t multiPV) {

    const RootMoves& rootMoves = Threads.main()->rootMoves;
    static PRNG rng(now()); // PRNG sequence should be non-deterministic

    // RootMoves are already sorted by score in descending order
    Value topScore = rootMoves[0].score;
    int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg);
    int weakness = 120 - 2 * level;
    int maxScore = -VALUE_INFINITE;

    // Choose best move. For each move score we add two terms, both dependent on
    // weakness. One is deterministic and bigger for weaker levels, and one is
    // random. Then we choose the move with the resulting highest score.
    for (size_t i = 0; i < multiPV; ++i)
    {
        // This is our magic formula
        int push = (  weakness * int(topScore - rootMoves[i].score)
                    + delta * (rng.rand<unsigned>() % weakness)) / 128;

        if (rootMoves[i].score + push > maxScore)
        {
            maxScore = rootMoves[i].score + push;
            best = rootMoves[i].pv[0];
        }
    }

    return best;   }
  • Stockfish starts multi-PV (not supported in TSCP, so you'll need to code it yourself!)
  • Compute a random number and add it to the score for each PV
  • Compare each weighted PV, and pick the best one

You may find the following links useful:

Recommendation: Don't do it unless you want to weaken your engine.

  • the book approach worked great, thanks! I have posted a follow-up question regarding transposition tables and triangular arrays. – nak3c Feb 12 '17 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.