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.
The rule of thumb for this sort of thing is to never rely on color alone to convey important information. Shapes and patterns and textures are much preferable to simple color variations.
This would be great. It looks like at the top end there might be a third stone. So square, triangle, circle. And where they go on the board marked with the same shape would be very intuitive even with no color at all.
I think square, circle, octagon would make the most sense. Or maybe diamond (rotated square) instead of octagon. That way adjacent stone would always touch.