Databases
StackOverflow2013
Postsdbo
POgraph-game algorithm
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POgraph-game algorithm
    primarykey
    data
    text
    <p>I'm trying to simulate the following game: The game is played with 2 players. Imagine you have a graph, with vertices and edges. Each turn you can remove one edge, if you isolate a vertex you get a point and you can remove another one. You play until there are no more edges at which point the player with the most point wins the game.</p> <p>I represent the graph by an array, which I read from a separate file generated that's generated by another program, for example this one:</p> <pre><code>0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 </code></pre> <p>Player 1 can win with 4/0, but so can player 2. The best result is 1/3 for player 1.</p> <p>EDIT: "how can a player win with 4/0?" :</p> <pre><code>A--B--D | / c A--B--D | C A B--D | C </code></pre> <p>As you can see the first player will get 4 points if the middle edge is removed, otherwise the other player will get 4 points.</p> <p>I can get the best result for each player, but then the other player would not choose his best turn each turn. I've spent a lot of time experimenting with it, but I always get the same problem. </p> <p>EDIT: I think I'm pretty close to solving this now (then again I have been thinking that all the time), I just need to save 2 scores for each turn, and then somehow I have to make it so that only the highest score of the current player is accepted. That way I should be able to make it so that the player will ignore the 4/0 move.. </p> <p>EDIT: I've tried to implement the suggestion but unfortunately I'm stuck again. I either get a strange output that's way too high, or the function simply gives me -2 as an answer, but it doesn't work on other, bigger graphs. I've tried a lot of things to fix it, but it just doesn't work. The code below is what I'm trying now, unfortunately it doesn't work either:</p> <pre><code>int Matrix::getTurn (bool** array) { if (edges == 0) return 0; for (int i=0; i&lt;edges; i++) { for (int j=0; j&lt;edges; j++) { if (array[i][j] == true) { array[i][j] = false; array[j][i] = false; score = getScore (array, i, j); if (score &gt; 0) score += getTurn (array); else score -= getTurn (array); if (score &gt; maxScore) maxScore = score; array[i][j] = true; array[j][i] = true; } } } return maxScore; } </code></pre> <p>With maxScore and score being member-variables of the class. Could someone please point out what part of it needs correction?</p> <p>Another EDIT, still not working, now I just don't see the error at all. It keeps outputting 1, it's like it never changed maxScore... Takken is the number of edges left, I tried using the boundaries of the array but it does not make any difference..</p> <pre><code>int Matrix::berekenZet (bool** array) { if (takken == 0) return 0; int maxScore = 0, score = 0; for (int i=0; i&lt;takken; i++) { for (int j=0; j&lt;takken; j++) { if (array[i][j] == true) { array[i][j] = false; array[j][i] = false; takken -= 1; score = berekenScore (array, i, j); if (score &gt; 0) score += berekenZet (array); else score -= berekenZet (array); if (score &gt; maxScore) maxScore = score; array[i][j] = true; array[j][i] = true; takken += 1; score = 0; } } } return maxScore; } </code></pre> <p>Thanks in advance.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USuser2180680
    1. USuser2180680
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POgraph-game algorithm
      1. USuser2180680
      1. VTFavorite
    1. COI think you mean "vertex/vertices" rather than "vector".
      singulars
      1. POgraph-game algorithm
      1. USus2012
    2. COThanks, changed that.
      singulars
      1. POgraph-game algorithm
      1. USuser2180680
    3. COYes, but I want to have the correct scores as well.
      singulars
      1. POgraph-game algorithm
      1. USuser2180680
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload