I'm looking for this short story:
"Second Game", a novelette by Katherine MacLean and Charles V. De Vet, the first story in their Kalin Trobt series; first published in Astounding Science Fiction, March 1958, available at the Internet Archive; also the answer to this old question and this one. Later expanded into a novel with the same title.
A game-playing man is recruited to voyage to an alien species which humanity doesn't know much about.
I had come to this world called Velda two weeks earlier. My job was to find why its humanlike inhabitants refused all contacts with the Federation.
Earth's colonies had expanded during the last several centuries until they now comprised a loose alliance known as the Ten Thousand Worlds. They were normally peaceful—and wanted peace with Velda. But you cannot talk peace with a people who won't talk back. Worse, they had obliterated the fleet bringing our initial peace overtures. As a final gesture, I had been smuggled in—in an attempt to breach that standoff stubbornness. This booth at their fair was my best chance—to secure audience with the men in authority. And with luck it would serve a double purpose.
They are very similar to humans, except something about their nose is different - it can be bent inwards.
Suddenly his eyes widened. His glance swept upward to my face and what he saw there caused his expression to change to one of mingled dismay and astonishment. There was but one move he could make. When he made it his entire left flank would be exposed. He had lost the game.
Abruptly he reached forward, touched his index finger to the tip of my nose and pressed gently.
After a minute during which neither of us spoke, I said, "You know?"
He nodded. "Yes," he said. "You're a human."
[. . . .]
I suppressed an ineffectual impulse to deny what I was. The time was past for that. "How did you find out?" I asked Trobt.
"Your game. No one could play like that and not be well known. And now your nose."
"My nose?" I repeated.
"Only one physical difference between a human and a Veldian is apparent on the surface. The nose cartilage. Yours is split—mine is single." He rose to his feet. "You will come with me please?"
They play a chess-like game which this human is good at. He plays them, gradually meeting tougher and tougher opponents, until he gets to one who really challenges him, and he tries something that's never succeeded before - a "triple fake".
The following evening when we began to play I was prepared to give my best. I was rested and eager. And I had a concrete plan. Playing the way I had been doing I would never beat Yondtl, I'd decided after long thought. A stand off was the best I could hope for. Therefore the time had come for more consummate action. I would engage him in a triple decoy gambit!
I had no illusion that I could handle it—the way it should be handled. I doubt that any man, human or Veldian, could. But at least I would play it with the greatest skill I had, giving my best to every move, and push the game up the scale of reason and involution—up and up—until either Yondtl or I became lost in its innumerable complexities, and fell.