A's job is to distinguish F from G, based on making queries to the oracle that it's given.
We want to compare the DES instance with an idealized 64-bit block cipher, meaning a permutation selected at random from the (264)!
Call this randomly selected permutation G. Note from Stirling's approximation that (264)!
, so even specifying which permutation is selected requires writing down a number too large to represent exactly in any real computer.
Viewed another way, G is an instance of a "cipher" whose "key length" is about 1021 bits, which again is too large to fit in a computer.
(We can, however, implement G with storage space proportional to the number of queries, using a random oracle).
Note that because the oracles we're given encrypt any plaintext of our choosing, we're modelling a chosen-plaintext attack or CPA, and the advantage we're calculating can be called the CPA-advantage of a given adversary.
If we also had decryption oracles available, we'd be doing a chosen-ciphertext attack or CCA and finding the CCA-advantage of the adversary.
It simply flips a coin and returns 1 or 0 with equal probability and without making any oracle calls.
If we're cipher designers, our desire (maybe not achievable) is to make it so that it's computationally infeasible for any adversary to do significantly better than this.
We will have succeeded if we can make a cipher for which there's no distinguisher faster than brute force search.
This adversary (call it A1) will attempt to cryptanalyze its input by brute force.
It gives a single query to its oracle, asking for the 64-bit string of all zeroes to be encrypted.
The algorithm looks like this: This searches the entire 56-bit DES keyspace and returns "1" if it probably finds a matching key.
If the input oracle is DES, this exhaustive search is certain to find the key, so Pr[A1(F)=1] = 1.
If the input oracle is a random permutation, there are 264 possible values of E0, and at most 256 of them will get examined in the DES keysearch.