Or two different shapes, because there are too many different color blindnesses. Board games started marking counters many years ago. Sometimes their colors are so similar even for non color blind people. I couldn't get a black from dark blue counter two nights ago, the light at the table was not great. And yellow looked a pale gray.

Examples for the game: the red stone could have a empty circle mark on the top it, the green one could have a circle with a dot inside. The destination squares would be marked with the empty circle and the dotted circle.

I have made a very quick-fix for colorblindness at https://kuboble.com/beta/

I'll try to come up with something better in the long term

Yea, even better: distinct iconography.

A circle and a triangle, for example.