Here's my 5 cents worth:
The B777 has a light on the nose gear indicating the park brake level position(on/off) and another light indicating the brake system pressure(pressurize or not),they are different in colour.
My SOP only ask us to put the brakes on when a/c come to a stop to shut engines down then look for the ground crew to confirm chocks in and release the brakes.So the brake is on for 1 minute.Prior to push back,if the brakes have been released since arrival,there is no reason to set it as chocks should still be there(There's one thing to look for during external walk around check)
If the ground crew removed the chocks,they'd have had the tow truck connected with truck's brakes set.If the a/c moved that's not your problem.
We operate to places where the only word that grond crew say is "OK",DO NOT switch on the anti-co light till push back clearence received and brakes RELEASED.The very second he sees the red light,he pushs back!!!
Cheers.