I use a slightly different random selection: choosing a random number between 1/3 and 2/3 of the way between min and max. To do this I set two variables at the start of NextGuess(): limitLo = min + (max-min)/3, and limitHi = max - (max-min)/3. Then I choose a number using Random.Range(limitLo, limitHi);
This way its first guess will rarely be 500, but will never be 8.
Also, I set it up for 9 guesses, since that gives just a little better than 50/50 chance of picking your number.
https://www.gamebucket.io/game/1f5422c1-a24e-4e9a-acc2-72c79491aef8