The client–server architecture is still popular due to its high predictable service and performance. However, it is not bandwidth scalable. An alternative setup for Internet video-streaming is offered by the peer-to-peer architecture, in which peers are servers as well as clients. Peers basically communicate in a three-level based policy. First, they meet other peers with common interests: this is called swarming. Then, each peer selects a small number of them for cooperation, called the peer selection strategy. In the last step peers cooperate sending pieces, defining the piece selection strategy. This paper is focused on piece selection strategies. We propose an in-depth analysis of a simple cooperative model. In this model the issue is to find the best order in which pieces should be obtained. In the first stage, we introduce a Combinatorial Optimization Problem (COP), which maximizes the average user experience for video streaming services, and has a permutation as the decision variable. Its hardness motivates us to approximately solve it via an Ant Colony Optimization-based heuristic. The main theoretical contributions are twofold: the introduction of a new piece selection strategy with better results in contrast with the ones found in the literature, and a systematic way of computing new piece selection strategies with high quality. The practical contribution is the incorporation of a new piece selection strategy in a live peer-to-peer streaming platform, with remarkable performance in relation with classical strategies.