You could still do it with two colors if it remembered the previous color as well, and if you didn't allow "keep going straight" or "move back in the direction you came from" as options.
(Imagine the ant as a space-ship, and every time it turns, it also changes its pitch/yaw, so the directions are based on its direction of travel.)
Current | Previous | Action
white | white | go starboard
white | black | go port
black | white | go down
black | black | go up