Implement faster winner check

[tonypr]

Reworks the logic that checks for a winner. The new implementation checks after the end of each turn for the current player vs. the current implementation that loops over each player and checks if there's a winner.

Currently, the code loops over each player after each tick to determine if there's a winner. However, we can simply check if a player has won in their turn and store that information. This saves us from looping over the players after each tick which accounts for 5% of the runtime.

I found this by running a profiler and viewing the output through snakeviz:

$ python3.9 -m cProfile -o profile play.py --num=1000
$ snakeviz ./profile

We can notice a speed improvement in the overall runtime by running time python3.9 play.py --num=1000

At commit aa43d9, the current head commit, my machine computes an average duration per game of 0.023s.

In this commit, the average duration per game is 0.022s. Roughly a 4.5% improvement which correlates with the snakeviz graph.

The updated snakeviz profile shows that winning_color now accounts for only 0.21% of the runtime.

[netlify[bot]]

✅ Deploy Preview for catanatron-staging canceled.

Name	Link
🔨 Latest commit	218d8e3ab901009caaf7428f2d31244cd0c4073d
🔍 Latest deploy log	https://app.netlify.com/sites/catanatron-staging/deploys/631e0e650cb67d000a975c64

[coveralls]

Pull Request Test Coverage Report for Build 3032549836

• 11 of 11 (100.0%) changed or added relevant lines in 3 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage increased (+0.006%) to 95.804%

---

Totals
Change from base Build 3023738925:	0.006%
Covered Lines:	1370
Relevant Lines:	1430

---

💛 - Coveralls

[tonypr]

There is a caveat, I believe, it's possible for a player to win out-of-turn though extremely unlikely. The only case I can think of where this could happen is: players: A,B,C Player A has the longest road. Player B would have longest if player A didn't have longest. And player B has 8 or 9 victory points. Player C's turn. Player C builds a settlement cutting A's longest road thus making B the player with the longest road, in turn, making B the winner.

I haven't included handling for this case since it's so rare. But can look into it.

[bcollazo]

Hey! Yes, that's what I was going to say (that classic other-player-triggering 10 points scenario). Tho in Catan you can only win in your turn. That is, even if another player makes me have 10 points, I don't win right then and there, I have to wait for my turn for the win condition to trigger. This is more relevant in 6+ player games.

Can we make it so that it checks at the end of each action? I think what we have here is correct in terms of having people only win on their turn, but I'd be nice if the player doesn't have to click "END TURN" to win. Ideally, as soon as they build their last house, or get that last VP they win. Right?

Maybe we can at the very least only check (after each action) the player whose turn is it (current_turn_index) instead of looping through everyone?

[pachewise]

in general I like this direction. I do agree we should check if the player has won after every action taken. Catan does require that you win in your turn, so I think for now we can keep that assumption, though it may be useful later to be able to toggle whether you have to win on your turn or not.