I’m creating a small game, where the computer generate pseudo random number in give range, and the user have to guess it. I also made the option to play computer vs computer. I mean the computer generate random number and the computer should guess it.
The easiest way I found was to create for loop and increase a variable by 1 until it guesses it. But I decided to try to create my own algorithm about this.
Basically the variable that holds the guess number is equal to range / 2, and then the program enters into the while loop where if the random number > the number which is generated by logic(the one which is = to range /2) then 2 it to two and add 1 to it. If the number is < the program * by 2 and add one to it until it guess the number.
Here is code in C++:
void aiVsAI(int range){ // range argument is used to be given to the randome generator func
int random_number = generate_random_number(range); // assigning the random number to variable
int guess = range / 2; // the computer guess number
int tries = 0; // how many tries the computer needed to guess the number
while(guess != random_number){ // while the guess isn't equel to the random number
if(guess > random_number){ // if the guess is > than the random number
guess = guess / 2 + 1; // dev it to 2 and add one to it
}
else if(guess < random_number){ // if the number is < than the number then
guess = guess * 2 + 1; // * it with 2 and add one
}
tries++; // increase the number of tires
}
std::cout << tries;
}
the generate_random_number is function that will generate pseudo-random number.
My question is which algorithm is faster this one or just using for loop and increasing variable with one until it guess the number?
Here is the full code if anyone need it for something:
#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>
//function that will generate random number
int generate_random_number(int range){ // the range argument is used to represent the maximum value of the number
if(range < 10){ // the range couln't be < 10 but can be ==
std::cout << "range can't be less than 10";
exit(1);
}
std::srand(time(NULL)); // making sure that the random number will be different every time
return rand() % range; // returning the random generated number in the specific range
}
//Game computer vs computer
void aiVsAI(int range){ // range argument is used to be given to the randome generator func
int random_number = generate_random_number(range); // assigning the random number to variable
int guess = range / 2; // the computer guess number
int tries = 0; // how many tries the computer needed to guess the number
while(guess != random_number){ // while the guess isn't equel to the random number
if(guess > random_number){ // if the guess is > than the random number
guess = guess / 2 + 1; // dev it to 2 and add one to it
}
else if(guess < random_number){ // if the number is < than the number then
guess = guess * 2 + 1; // * it with 2 and add one
}
tries++; // increase the number of tires
}
std::cout << tries;
}
// Game human vs human
void humanVsAI(int range){ // range argument is given to the generate random function
int random_number = generate_random_number(range); // assigning the random number to variable
int input = 0; // this var represents the user input
int tries = 0; // the number of tries user had make to guess the number
while(input != random_number){
std::cout << "Enter number: "; // alerting the user to enter a number
std::cin >> input; // getting the number
if(input < random_number) // checking if the input > than the random num
std::cout << "You didn't guess it,you are too low..., try again!n"; // alerting the user
else{ // else it will be > than the number
std::cout << "You didn't guess it,you are too high..., try again!n"; // alerting the user
}
tries++; // increasing tries by one for each try//
}
std::cout << "nnYou guess it! You need " << tries << " to do this.nn";
}
//game Human vs Human
void humanVsHuman(int range){
int number_to_guess; // the number which must be guessed
int user_guess; // user input
int guess;
std::cout << "Enter number int range 1- "<< range<<": n"; // alerting the user to enter number
std::cin >> number_to_guess; // entering number
for(int i = 0; i < 100;i++){ //Clearing the screen
std::cout << "n";
}
while(user_guess != number_to_guess){
guess++;
std::cout << "Please enter numer:n"; // alerting the user
std::cin >> user_guess; // Getting the user input
if(user_guess < number_to_guess)
std::cout << "You didn't guess it,you are too low..., try again!n";
else if(user_guess > number_to_guess)
std::cout << "You didn't guess it,you are too high..., try again!n";
}
std::cout << "You guess the numbern";
}
int main(){
std::string game_type;
char play_game;
int range = 0;
while(1){
std::cout << "Please enter range(type 100 to leave it as default)n";
std::cin >> range;
std::cout <<"What you want to play AI vs human, human vs human or AI vs AI ?n";
std::cin.ignore(); // for get line
std::getline(std::cin, game_type); // getting the user input
std::cin.clear(); // clearing
if(game_type == "AI vs AI" || game_type == "ai vs ai"){ // if the user chose AI vs AI
std::cout<<"You choosed AI vs AIn";
aiVsAI(range); // calling the AI function
}
else if(game_type == "human vs ai"
|| game_type == "ai vs human"
|| game_type == "human vs AI"
|| game_type == "Human vs AI"
|| game_type == "Human vs ai"
){ // if the user chossed AI vs human
std::cout << "You choosed human vs AIn";
humanVsAI(range); // calling the human vs human function
}
else if(game_type == "human vs human"
||game_type == "Human vs Human"
||game_type == "Human vs human"
||game_type == "human vs Human"){ // if the user choosed human vs human
std::cout <<"You choose human vs humann";
humanVsHuman(range); // calling the human vs human function
}
else{ // In case of any error
std::cerr << "An error occured!";
}
std::cout << "Do you want to play another game?n"; // do you want another game????
std::cin >> play_game;
if(play_game == 'y' || play_game == 'Y')
std::cout <<" starting another gamen";
else
break; // enough playing for now.
}
return 0;
}
14
As long as the guess is consistently high, your algorithm performs well by roughly halving the guess.
Once you have made a low guess, the algorithm severely deteriorates in performance. By doubling after a low guess, you are guaranteed that the next guess will be too high. Now, the +1 factors come into play (especially the one after halving), which let you walk towards the right number at half the speed of a normal loop.
For performance measurements, I would expect the slow walk up to be the dominant factor, making your algorithm slower on average than the simple loop. Given your measurements, either my expectations are wrong, or the distribution of your pseudo-random values happens to be slightly in favor of your algorithm.
If you want a challenge, you could try to implement a binary search. With a range of 100, that algorithm is able to find any number within 10 steps (given that it knows the range).
1
The more sophisticated algorithm is definitely more efficient: it requires logarithmic time vs. linear time to find the value. Here is a description of binary search; that’s basically what you have reinvented.
3