HIARCS Chess Forums Forum Index HIARCS Chess Forums
World Championship winning computer chess software program & downloads for chess database, analysis and play on PC, Mac and iPhone
 
 QuestionsQuestions   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Private MessagesPrivate Messages   Log inLog in 

A billion random games

 
Post new topic   Reply to topic    HIARCS Chess Forums Forum Index -> Programming Discussions
View previous topic :: View next topic  
Author
sje
Full Member


Joined: 28 Sep 2013
Posts: 639
Full Name: Steven Edwards
Location: Land of Snow, Mud, and Bugs, NH USA

PostPosted: Wed Feb 19, 2014 8:51 pm    Post subject: A billion random games Reply with quote

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

After a billion random games:
Code:
[] 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.
Back to top
View user's profile Send private message
fourthirty
Member


Joined: 06 Dec 2013
Posts: 277
Full Name: Greg
Location: San Francisco

PostPosted: Thu Feb 20, 2014 12:23 am    Post subject: Reply with quote

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?
Back to top
View user's profile Send private message
fourthirty
Member


Joined: 06 Dec 2013
Posts: 277
Full Name: Greg
Location: San Francisco

PostPosted: Thu Feb 20, 2014 2:08 am    Post subject: Reply with quote

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?
Back to top
View user's profile Send private message
sje
Full Member


Joined: 28 Sep 2013
Posts: 639
Full Name: Steven Edwards
Location: Land of Snow, Mud, and Bugs, NH USA

PostPosted: Thu Feb 20, 2014 11:46 am    Post subject: Code snippets Reply with quote

Code:
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 (ui64 index = 0; index < limit; index++)
    {
      ptvec[position.RandomGame()]++;
      totalply += position.GetHistoryCount();
    };
    analysis.UpdateTotalTimes();

    ForEachPosTerm(posterm)
      if (posterm != PosTermUnterminated)
      {
        const ui64 count = ptvec[posterm];
        const double ratio = count / (double) limit;

        oss <<
          std::setw(12) << PosTermNameVec[posterm] << ' ' <<
          std::setw(8) << count << ' ' <<
          std::setprecision(6) << ratio;
        DIPtr->WriteLn(oss.str());
        oss.str("");
      };

    oss << "Average ply length: " << totalply / (double) limit;
    DIPtr->WriteLn(oss.str());
    oss.str("");

    DIPtr->WriteLn(analysis.EncodeStats());
  };
}
Back to top
View user's profile Send private message
fourthirty
Member


Joined: 06 Dec 2013
Posts: 277
Full Name: Greg
Location: San Francisco

PostPosted: Sat Feb 22, 2014 4:27 pm    Post subject: Re: Code snippets Reply with quote

sje wrote:
Code:

  else
    move = gmvec[RandomPick(gmvec.GetCount())].GetMove();
  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
Back to top
View user's profile Send private message
sje
Full Member


Joined: 28 Sep 2013
Posts: 639
Full Name: Steven Edwards
Location: Land of Snow, Mud, and Bugs, NH USA

PostPosted: Sat Feb 22, 2014 5:12 pm    Post subject: Re: Code snippets Reply with quote

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:
ui RandomPick(const ui bound)
{
  const ui adjbound = -bound % bound;
  ui value;

  do
    value = (ui) random();
  while (value < adjbound);
  return value % bound;
}
Back to top
View user's profile Send private message
fourthirty
Member


Joined: 06 Dec 2013
Posts: 277
Full Name: Greg
Location: San Francisco

PostPosted: Sat Feb 22, 2014 6:23 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
sje
Full Member


Joined: 28 Sep 2013
Posts: 639
Full Name: Steven Edwards
Location: Land of Snow, Mud, and Bugs, NH USA

PostPosted: Tue Feb 25, 2014 2:23 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
fourthirty
Member


Joined: 06 Dec 2013
Posts: 277
Full Name: Greg
Location: San Francisco

PostPosted: Sat Mar 01, 2014 2:08 am    Post subject: Reply with quote

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/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf
Back to top
View user's profile Send private message
WorldChessNews



Joined: 13 Jun 2014
Posts: 1

PostPosted: Sat Jun 14, 2014 12:09 am    Post subject: Re: A billion random games Reply with quote

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

After a billion random games:
Code:
[] 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.


WOW! I am Amazed you had the time to Run that (RNG) ?
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    HIARCS Chess Forums Forum Index -> Programming Discussions All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Protected by Anti-Spam ACP