Well I did:

shuffle another genre
down
down
down
select

This will do the trick for now but if someone knows of a more direct way to do this please let me know.
It looks like alpha search will only do artists, albums and songs but not genres.
Is this correct?
Thanks