Euclid's game (also known as the Game of Euclid) is played as follows:
the players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.
I was researching optimal strategies for this and found that several sources promoted the formula a/gcd(a,b), where a > b. If this number is odd, the first player wins, and if it is even, the second player wins.
However, I was never able to utilize this strategy as either it or my understanding of it is faulty. I did find another, working, strategy, but I'm still curious as to why this simple strategy wasn't working.
Here's one example of when it doesn't seem to work:
28 20. gcd(28,20) = 4. 28/4 = 7, meaning that the starting player will win.
28 20 - Starting numbers
8 20 - Player A
8 4 - Player B
0 4 - Player A wins
However, since any multiple can be removed in this game Player B can force a win by removing only one multiple of 8 in his first move:
28 20
8 20 - Player A, forced move
8 12 - Player B
8 4 - Player A, forced move
0 4 - Player B wins
Is the strategy not working, or am I missing some underlying assumption?
It doesn't work because it is simply incorrect. The example you have provided is a perfect example of why it is wrong.
What is correct: the first player wins iff $$\frac{a}{b}>\frac{1+\sqrt{5}}{2}$$
As a hint towards proving this, if you are interested, think continued fractions.