Joust game taking place and it reaches the beginning of the challenge phase.

As soon as Shadow Politics comes out of shadows can he initiate an intrigue ?

Does the card have to come out at the beginning of the challenge phase ?

Yes, the only time you can bring Shadow Politics out of Shadows is at the beginning of the phase.

That said, the card lets you initiate an INT challenge as a player action during that phase. So the first opportunity in the challenge phase is after all cards come out of Shadows at the beginning of the phase - and after other players in turn order have a chance to play a player action (if you are not the First Player).

But you don't have to do it then. You can do it any time you can take a player action - unless another challenge is already in progress.

Actually, you can bring Shadow Politics out at the beginning of any phase, not just the Challenges phase.