Given a strongly connected bipartite digraph with a finite number of black and white nodes. Every edge goes either from a white to a black node, or from a black to a white node. Each black to white edge has a integer weight between -2 and 2. The white to black edges have a weight of 0.
When on a black node the path must be followed that will lead (eventually) to a loop with an average cycle weight that will be as small as possible, taking into account that when on a white node the path must be followed that will lead (eventually) to a loop with an average cycle weight that is as large as possible, and visa versa.
This must lead to a finite choice of cycles that all have the same average weight: no choice of white-to-black edges can make the value of the average cycle weight of followed loops larger and no choice of black-to-white edges can make the average cycle weight of the followed loops smaller.
Can someone figure out an algorithm to find these loops, and explain it to me?
EDIT:
I investigated publications on this matter, and it seems that it has never been studied, let alone solved, before. The studied graphs are usually not bipartite. The whole concept of competing strategies for each of the two colors seems to not have been investigated - at least, I can't find it. Everything is always about minimum mean cycle weights, where the strategy is the same at every node: to follow a path that leads to this minimum.
Background
I am trying to solve a problem on an infinite large chess board. Assuming the pieces are "close together" (ie, distance less than 9 squares in any direction) OR they are infinitely far away in a given direction, provided they can return in a single move. For example, a rook at infinite distance that still cuts through the local area where the more local pieces all are (kings, knights, pawns). The result is a limited state space that is rather easy to brute force by a computer (say, less than 10,000,000 nodes).
Here white tries to make progress by forcing the whole in the north and/or west direction. Lets says that the origin is somewhere in the top-left and we are at coordinates m,n, then a measure for progress is the decrease of m+n. White tries to make that (with an otherwise equal position: the pieces relative to each other) as fast as possible smaller, and black tries to work against this. The position is such that white CAN make progress.
Back to the graph: the finite number of nodes represent all the possible ways the pieces can stand relative to each other (with a maximum allowed distance). It is a bipartite graph because we have alternating black and white nodes (whose turn it is). It is directed because we can seldom return to the previous node (which in general would require the same piece to be put back; but it is the turn of the other player). I can generate the graph, but now I need an algorithm to find the optimal play for both sides:
White wants to approach a position that, once it is reached, will repeat every N moves such that (n + m) / N decreases as fast as possible (ie, as a whole moves the position north/west). Black on the other hand wants to make that as difficult as possible, aka wants to get a repeating loop in the graph where (n + m) / N decreases as slow as possible.
Each edge in my graph has a value for the decrease of n + m (-2, -1, 0, 1 or 2 since n and m are the distance of the black king to the north/west corner). Thus for any given loop I can calculate the decrease of (n + m) / N over a full loop. But what is a loop? Not all existing loops in the graph can be considered because both black and white can refuse to follow it. The existing loops (that will actually be followed) depend on the loops that exists - it's a catch-22 situation :/.