A billion random games

You can discuss all aspects of programming and technical matters here.

Moderators: Harvey Williamson, Watchman

Post Reply
User avatar
sje
Full Member
Posts: 639
Joined: Sat Sep 28, 2013 2:28 am
Location: Land of Snow, Mud, and Bugs, NH USA

A billion random games

Post by sje »

If each move in a chess game is picked at random, how does the game end?

After a billion random games:

Code: Select all

[] rg 1000000000
   checkmate 153073649 0.153074
  fiftymoves 193423592 0.193424
insufficient 567109826 0.56711
  repetition  25189704 0.0251897
   stalemate  61203229 0.0612032
Average ply length: 334.347
Count: 1,000,000,000   Pt: 2:07:24:31.709   Wt: 2:07:24:32.760   5.01322 KHz   199.473 us
That took 2 days 7+ hours running on a single thread on a 3.2 GHz Intel Core i5 CPU with a rate of about 5,000 games per second.

Interestingly, the random number generator used about one fifth of the total processing time.
User avatar
fourthirty
Full Member
Posts: 762
Joined: Fri Dec 06, 2013 8:46 pm
Location: San Francisco

Post by fourthirty »

This is very interesting. I'm assuming all moves were programmed to be legal chess moves. Slightly similar to the novice game "No Stress Chess" where the piece to move is dictated by a random card draw - but in this case on steroids...

How were pawn promotions handled - did it default to a Queen? Or, was it programmed to under-promote to avoid stalemate situations?

Was there any significant statistical difference on the white versus black checkmate? Curious to know if white had a slight advantage with the first move.

It would be interesting to see how a couple of checkmates occurred (out of the 153 million) . I wonder what percentage were just brute force traps by major pieces versus a lucky random move of a minor piece or pawn. Did you have a chance to view the details of any of the games?
User avatar
fourthirty
Full Member
Posts: 762
Joined: Fri Dec 06, 2013 8:46 pm
Location: San Francisco

Post by fourthirty »

fourthirty wrote: I'm assuming all moves were programmed to be legal chess moves.
To clarify - I'm trying to understand if the random generator FIRST randomly picked the piece to move, and THEN picked one of the legal moves (if available).

Or, did the random generator look at ALL the possible legal moves from ALL the pieces on the board and choose from that population?
User avatar
sje
Full Member
Posts: 639
Joined: Sat Sep 28, 2013 2:28 am
Location: Land of Snow, Mud, and Bugs, NH USA

Code snippets

Post by sje »

Code: Select all

PosTerm Position::CalcPosTerm(void) const
{
  PosTerm posterm;

  if (HasNoMoves())
  {
    if (inch)
      posterm = PosTermCheckmate;
    else
      posterm = PosTermStalemate;
  }
  else
  {
    if (IsDrawnFiftyMoves())
      posterm = PosTermFiftyMoves;
    else
    {
      if (IsDrawnInsufficient())
        posterm = PosTermInsufficient;
      else
      {
        if (IsDrawnRepetition())
          posterm = PosTermRepetition;
        else
          posterm = PosTermUnterminated;
      };
    };
  };
  return posterm;
}

Move Position::SelectRandomMove(void) const
{
  Move move;
  GMVec gmvec;

  Generate(gmvec);
  if (gmvec.GetCount() == 0)
    move.SetVoid();
  else
    move = gmvec[RandomPick(gmvec.GetCount())].GetMove();
  return move;
}

PosTerm Position::RandomGame()
{
  RetractAll();
  while (!IsGameOver())
    Execute(SelectRandomMove());
  return CalcPosTerm();
}

void IntCoPro::DoCrg(void)
{
  if (tokens.GetCount() != 2)
    UserError("Need exactly one parameter");
  else
  {
    const ui64 limit = (ui64) strtoll(tokens.GetHead()->GetNext()->RefStr().c_str(), 0, 10);
    Position position;
    ui64 ptvec[PosTermLen];
    ui64 totalply = 0;
    Analysis analysis;
    std::ostringstream oss;

    position.LoadInitialArray();
    ForEachPosTerm(posterm)
      ptvec[posterm] = 0;

    analysis.PutNc(limit);
    for &#40;ui64 index = 0; index < limit; index++&#41;
    &#123;
      ptvec&#91;position.RandomGame&#40;&#41;&#93;++;
      totalply += position.GetHistoryCount&#40;&#41;;
    &#125;;
    analysis.UpdateTotalTimes&#40;&#41;;

    ForEachPosTerm&#40;posterm&#41;
      if &#40;posterm != PosTermUnterminated&#41;
      &#123;
        const ui64 count = ptvec&#91;posterm&#93;;
        const double ratio = count / &#40;double&#41; limit;

        oss <<
          std&#58;&#58;setw&#40;12&#41; << PosTermNameVec&#91;posterm&#93; << ' ' <<
          std&#58;&#58;setw&#40;8&#41; << count << ' ' <<
          std&#58;&#58;setprecision&#40;6&#41; << ratio;
        DIPtr->WriteLn&#40;oss.str&#40;&#41;&#41;;
        oss.str&#40;""&#41;;
      &#125;;

    oss << "Average ply length&#58; " << totalply / &#40;double&#41; limit;
    DIPtr->WriteLn&#40;oss.str&#40;&#41;&#41;;
    oss.str&#40;""&#41;;

    DIPtr->WriteLn&#40;analysis.EncodeStats&#40;&#41;&#41;;
  &#125;;
&#125;
User avatar
fourthirty
Full Member
Posts: 762
Joined: Fri Dec 06, 2013 8:46 pm
Location: San Francisco

Re: Code snippets

Post by fourthirty »

sje wrote:

Code: Select all

  else
    move = gmvec&#91;RandomPick&#40;gmvec.GetCount&#40;&#41;&#41;&#93;.GetMove&#40;&#41;;
  return move;
sje,

Thanks for sharing parts of your code! I do not speak C++ very well (FORTRAN 77 was my last programming class). However, one of my fellow engineers is somewhat fluent, and we reviewed the code yesterday.

We assumed that gmvec function is the set of ALL the legal moves computed from your chess engine. Then, instead of your engine calculating the relative strength of the legal moves, the RandomPick function selects one move from the set & assigns the vector to the variable "move".

Greg
User avatar
sje
Full Member
Posts: 639
Joined: Sat Sep 28, 2013 2:28 am
Location: Land of Snow, Mud, and Bugs, NH USA

Re: Code snippets

Post by sje »

fourthirty wrote:We assumed that gmvec function is the set of ALL the legal moves computed from your chess engine. Then, instead of your engine calculating the relative strength of the legal moves, the RandomPick function selects one move from the set & assigns the vector to the variable "move".
And here's the random number selector interface:

Code: Select all

ui RandomPick&#40;const ui bound&#41;
&#123;
  const ui adjbound = -bound % bound;
  ui value;

  do
    value = &#40;ui&#41; random&#40;&#41;;
  while &#40;value < adjbound&#41;;
  return value % bound;
&#125;
User avatar
fourthirty
Full Member
Posts: 762
Joined: Fri Dec 06, 2013 8:46 pm
Location: San Francisco

Post by fourthirty »

Got it. We were unable to find the C++ random function in the code, so we assumed that happened elsewhere in your engine code.

Makes sense now.

With 57% of the games ending due to insufficient material, it appears both sides (randomly) fought each other to the death quite often!

Very interesting experiment - thanks for sharing.
User avatar
sje
Full Member
Posts: 639
Joined: Sat Sep 28, 2013 2:28 am
Location: Land of Snow, Mud, and Bugs, NH USA

Post by sje »

The program is now working on a ten billion game run which should take a total of about 23 days of single core CPU time.

However, that may be too long of a run since the random number generator in use has a period of about 2^34 (ca. 34 billion). Each random game requires on average about 334 random numbers.

The arc4random() routine is better than the earlier random() routine, but is not part of the built-in library on Linux or on older versions of OpenBSD. So I don't use it as my code must remain as portable as possible.

The arc4routine() is somewhat tainted, however. Designed by RSA back in the 1990s, it has become suspect due to very recent revelations by Edward Snowden that the NSA paid RSA to deliberately compromise some of their products to make government intercepts easier.

On nearly all Unix systems, the pseudo device /dev/urandom produces good quality random bytes quickly. But its stream is different each time it's accessed, so hash codes built from it will also be different each time they are constructed.

I have my own C++ random bit stream generator, a high quality source which is used to make hash codes which are independent of the host platform. But it runs much, much slower than random() and so is a poor choice for billion game runs.
User avatar
fourthirty
Full Member
Posts: 762
Joined: Fri Dec 06, 2013 8:46 pm
Location: San Francisco

Post by fourthirty »

sje wrote:The program is now working on a ten billion game run which should take a total of about 23 days of single core CPU time.
It will be interesting to see how the outcome statistics change (I wouldn't expect much). However, if you are a believer in the Shannon Number, 10 billion is a small statistical sample of the number of possible games.

http://archive.computerhistory.org/proj ... 303002.pdf
User avatar
WorldChessNews
Posts: 1
Joined: Fri Jun 13, 2014 10:39 pm

Re: A billion random games

Post by WorldChessNews »

sje wrote:If each move in a chess game is picked at random, how does the game end?

After a billion random games:

Code: Select all

&#91;&#93; rg 1000000000
   checkmate 153073649 0.153074
  fiftymoves 193423592 0.193424
insufficient 567109826 0.56711
  repetition  25189704 0.0251897
   stalemate  61203229 0.0612032
Average ply length&#58; 334.347
Count&#58; 1,000,000,000   Pt&#58; 2&#58;07&#58;24&#58;31.709   Wt&#58; 2&#58;07&#58;24&#58;32.760   5.01322 KHz   199.473 us
That took 2 days 7+ hours running on a single thread on a 3.2 GHz Intel Core i5 CPU with a rate of about 5,000 games per second.

Interestingly, the random number generator used about one fifth of the total processing time.
WOW! I am Amazed you had the time to Run that (RNG) ?
Post Reply