How is it possible that an app stores its data even though I clear the cache and uninstall? I have downloaded an app (its a game), made some test progress, and then deleted the game data. I have also cleared the cache and uninstalled the game, but whenever I install it again from the Google Play Store, the progress is still there.

I have also tried installing the app after clearing its data, offline from the .apk-file.

How is it possible to retain the app data like this and how can I clear the data?
It's possible that the game progress is saved in the cloud, if you are using Google Play Games.

The Google help page says you can clear this progress / data, but note that it will clear for ALL games:


  If you want to delete your saved data from all games that use Cloud
  Save, visit the Google Settings app and select  Menu > Clear app data.
  This will clear all your data from all accounts.
  
  Depending on your device, your Menu icon may look different.