I assume because it would take a fewer number attempts than one would expect intuitively before the AI finds a successful strategy. Thus severely cutting down on the amount of time (or number of iterations) before a successful strategy is found.
Like with the birthday paradox, one would intuitively think it might take hundreds of people in a room before two had the same birthday, but of course we know that is indeed not the case.
The birthday paradox involves the possibility of random processes coinciding at some point, which feels a bit different from what the AI is doing.
Birthday paradox: different people are coming into the room with different randomly-distributed birthdays; how many people do you expect need to come in before two people in the room will have the same birthday?
Ordinary random search: there are several people in the room with birthdays that are unknown to you. How many birthdays do you expect you'll have to guess before you name a birthday that is actually the birthday of someone present?
Like with the birthday paradox, one would intuitively think it might take hundreds of people in a room before two had the same birthday, but of course we know that is indeed not the case.