GNOME Bugzilla – Bug 708179
ComputerPlayer does pointless extra work
Last modified: 2014-09-03 20:17:17 UTC
The calculate_heuristic () and around () methods in ComputerPlayer.vala do their calculations based on the state of the game at the beginning of the search, not the state after the hypothetical moves have been played. This only matters for the BEST strategy (which is most of the time). On the line: tile_difference + around () + eval_heuristic () around () and eval_heuristic () always result in the same number for a given search, so not this has the same effect as not calling them at all (which is what the PERFECT strategy does). I changed these to take the current hypothetical game state. When just eval_heuristic was changed, the AI was much better- however when I changed the around () method to use the hypothetical game state as well the AI got much worse. In both cases, the AI spent more time looking for a move. This should change to either eliminate the extra work which would speed things up a bit, or to implement these methods properly. I'm happy to submit a patch if someone wants to choose an option.
(In reply to comment #0) > around () and eval_heuristic () always result in the same number for a given > search, so not this has the same effect as not calling them at all (which is > what the PERFECT strategy does). Good catch. Surely they need to be passed the current game, g, and operate on that instead of on the global game. > I changed these to take the current hypothetical game state. When just > eval_heuristic was changed, the AI was much better- however when I changed the > around () method to use the hypothetical game state as well the AI got much > worse. In both cases, the AI spent more time looking for a move. That's interesting. If around() makes the AI worse, I guess it should just be removed? Also, let's keep Bug #601596 in mind: I'd rather not increase the difficulty of Easy mode (or "level one"). So when we fix BEST, let's switch to using PERFECT instead if playing easy? (These strategy names are pretty confusing....) > I'm happy to submit a patch if someone wants to choose an option. Thanks! If you're interested in the effectiveness of the AI, you might also look at Bug #707730.
(In reply to comment #0) > however when I changed the > around () method to use the hypothetical game state as well the AI got much > worse. I just noticed that is_empty() needs to be changed as well: if you missed that, it would probably explain why fixing around() made the AI worse.
(In reply to comment #1) > (In reply to comment #0) > > around () and eval_heuristic () always result in the same number for a given > > search, so not this has the same effect as not calling them at all (which is > > what the PERFECT strategy does). > > Good catch. Surely they need to be passed the current game, g, and operate on > that instead of on the global game. > > > I changed these to take the current hypothetical game state. When just > > eval_heuristic was changed, the AI was much better- however when I changed the > > around () method to use the hypothetical game state as well the AI got much > > worse. In both cases, the AI spent more time looking for a move. > > That's interesting. If around() makes the AI worse, I guess it should just be > removed? > > Also, let's keep Bug #601596 in mind: I'd rather not increase the difficulty of > Easy mode (or "level one"). So when we fix BEST, let's switch to using PERFECT > instead if playing easy? (These strategy names are pretty confusing....) Done, level 1 plays exactly the same. > > > I'm happy to submit a patch if someone wants to choose an option. > > Thanks! > > If you're interested in the effectiveness of the AI, you might also look at Bug > #707730. Submitted a pull request on github: https://github.com/GNOME/iagno/pull/1 Let me know of any changes you want, or if you'd rather I submit the patch a different way. I'm happy to play around with the AI some more... I hacked together a simple binary for playing around with this, see https://github.com/dpaul/iagno/blob/aitest/src/aitest.vala - not sure if this is something we'd like to clean up and put in the official repository as well, can continue that discussion elsewhere.
(In reply to comment #2) > (In reply to comment #0) > > however when I changed the > > around () method to use the hypothetical game state as well the AI got much > > worse. > > I just noticed that is_empty() needs to be changed as well: if you missed that, > it would probably explain why fixing around() made the AI worse. Nope, caught that :) My guess is that the signal it gets from around() is too high, and swamping out other useful information. Hold off on merging for now though, I want to do some more investigating first.
Ok- turns out that calculate_heuristic() wants to *minimize* the number returned. I had my testing backwards above, except for around(). So, negating the results from around() and eval_heuristic() results in much better play. New pull request submitted with more information: https://github.com/GNOME/iagno/pull/2 Trying to balance everything and getting the AI where we want it could turn into a large project, so not sure how much time we want to spend on this. We could always just keep the current behavior and remove the extra work :)
> Submitted a pull request on github: https://github.com/GNOME/iagno/pull/1 > Let me know of any changes you want, or if you'd rather I submit the patch a > different way. Can you please attach it as a patch to this bug (using 'git format-patch')? Our GitHub repository is just a mirror, so pull requests unfortunately don't work. > I'm happy to play around with the AI some more... I hacked together a simple > binary for playing around with this, see > https://github.com/dpaul/iagno/blob/aitest/src/aitest.vala - not sure if this > is something we'd like to clean up and put in the official repository as well, > can continue that discussion elsewhere. I would love to have that upstream; can you file another bug for it once it's cleaned up? > Trying to balance everything and getting the AI where we want it could turn > into a large project, so not sure how much time we want to spend on this. We > could always just keep the current behavior and remove the extra work :) Patches accepted. :) I'd personally be happy if the code was simply sane (which means I want to solve Bug #707730).
Created attachment 255152 [details] [review] simple patch with some improvements
(In reply to comment #6) > > Submitted a pull request on github: https://github.com/GNOME/iagno/pull/1 > > Let me know of any changes you want, or if you'd rather I submit the patch a > > different way. > > Can you please attach it as a patch to this bug (using 'git format-patch')? > Our GitHub repository is just a mirror, so pull requests unfortunately don't > work. Done. > > I'm happy to play around with the AI some more... I hacked together a simple > > binary for playing around with this, see > > https://github.com/dpaul/iagno/blob/aitest/src/aitest.vala - not sure if this > > is something we'd like to clean up and put in the official repository as well, > > can continue that discussion elsewhere. > > I would love to have that upstream; can you file another bug for it once it's > cleaned up? Sure- I'd like to get some feedback on the approach, maybe we can talk about it on the mailing list. > > Trying to balance everything and getting the AI where we want it could turn > > into a large project, so not sure how much time we want to spend on this. We > > could always just keep the current behavior and remove the extra work :) > > Patches accepted. :) > > I'd personally be happy if the code was simply sane (which means I want to > solve Bug #707730). I'm definitely interested in playing around with this some more, but can't commit a whole lot of time :). I'll update #707730 if I make any progress.
Created attachment 255153 [details] [review] patch v2, removed outdated comment
Review of attachment 255153 [details] [review]: Looks good. We're currently frozen until 3.10 is released, but I'll put this into 3.10.1.
Backporting this to gnome-3-10 as well, thanks for the fix!
Created attachment 284786 [details] [review] Rework the existing AI. I think there is more than one false conclusion in this bug, so I reopen it instead of creating another. (And it’s more fun with many people! =D ) > When just eval_heuristic was changed, the AI was much better- however > when I changed the around () method to use the hypothetical game state > as well the AI got much worse. I’m not surprised with that, because… around() is bugged. Here is the utility code of it’s last C implementation: static gint around0 (gint xy) { gint count = 0; int i; for (i = 0; i < NDIRS; i++) if (board0[xy + dirs[i]] == BLANK) count--; if (!count) count = 2; return count; } The important thing to notice is of course the `count--`… Yes, it’s another mistake in the vala port. Secondly, I don't understand the “Ok- turns out that calculate_heuristic() wants to *minimize* the number returned” thing. Yeah, the choice selected is the minimum, because the initial depth is odd (that’s a bad thing, but well, I’ll discuss that later). But the goal of the function should be to maximize things! (Did the negamax notation change something about that? I don’t think so, but hey, let’s say it’s not impossible.) And this, you can test it. Disable alternative strategies, set depth to 1 (odd), use only ‘eval_heuristic’: try it with + & -, you’ll know which one is better, or if you prefer which one takes the corners rapidly (65 is cool) and which one offer them to you… For the same reason, I don’t understand why when it’s Player.DARK turn, tile_difference is `g.n_light_tiles - g.n_dark_tiles` and not the opposite. And when you try it (disabling the things like explained), there’s clearly one of the two settings that motivate it to take only 1 token, and one where it takes more than 1… And the last C code was: static gint p_evaluation (void) { if (whose_turn == WHITE_TURN) return wcount - bcount; return bcount - wcount; } So, here is a patch that inverts many things, and, I think, gives a better AI. Without adding my custom functions, that’s another story. ;-)
Review of attachment 284786 [details] [review]: I guess we have to commit this now. When you do the long ternaries (two in this patch), please wrap the whole expression in an extra (unnecessary) set of parenthesis to make it easier to read. ::: src/computer-player.vala @@ +74,3 @@ } + var depth = level * 2 + 1; Er... yes. Yes. Yes. :p But a separate patch. @@ +238,3 @@ a = 2; + count += g.get_owner (x, y) == g.current_color ? a : -a; Consider also this form, longer than the others, but my favorite: if (g.get_owner (x, y) == g.current_color) count += a; else count -= a;
Created attachment 284900 [details] [review] Complicated things are complicated.
Created attachment 284901 [details] [review] Rework the existing AI. I didn’t change the count+/-=a thing, because I think it’s a quite simple expression, but changed the other that was maybe a little difficult to re-read. ^^’
Review of attachment 284900 [details] [review]: For something like this, a snarky comment is appropriate... I mean, not much else to say... but on the second line of the commit message. Be serious with the first line please!
Review of attachment 284901 [details] [review]: ::: src/computer-player.vala @@ +242,3 @@ a = 2; + count = g.get_owner (x, y) == g.current_color ? a : -a; This is not what you had before. ^^ It's no longer a count....
Created attachment 284910 [details] [review] Rework the existing AI. (In reply to comment #17) > This is not what you had before. ^^ It's no longer a count.... Ooops… ^^’
Created attachment 284911 [details] [review] Calculate depth a simpler way.
HOPING FOR THE BEST. Really uncomfortable with pushing AI changes without regression tests. Alas. Attachment 284910 [details] pushed as a6b54f4 - Rework the existing AI. Attachment 284911 [details] pushed as 9d580a2 - Calculate depth a simpler way.
I ran two times Dave’s aitest with master’s AI[1] and with the one before my changes in the main loop[2]; the current AI wins 236-6 (2 draws) when playing dark, and 229-12 (3 draws) when playing light, at level 2 in the two runs. [1] ea316ea0e236af9a1cb68ea94dc014bebf94257e [2] 2ea1fb41fc5296beb19213c614932435d2a9abde
Yay, great!