4 ms·

About a year ago I wrote an AI to play the board game "Hive" (shares some similarities with chess). Because I scored all wins equally, it behaved almost exactl

About a year ago I wrote an AI to play the board game "Hive" (shares some similarities with chess). Because I scored all wins equally, it behaved almost exactly like this. It would simply try to minimize my advantage while always keeping open the possibility for it to win, almost like a cat toying with prey. It never actually would make the winning move – however obvious – until it had no other options! I fixed this behavior by scoring earlier wins higher than later wins. Now it will actually finish games (and win), but almost invariably its edge is very small, no matter how well or poorly I play. Because of the new win scoring, it willingly sacrifices its own advantage if it means securing a win even one turn earlier. (And since scoring is symmetrical, this has the added advantage of working to delay any win it sees for me, thus increasing the possibility of me making a mistake!) I suppose I could try modifying the scoring rules again, to weight them by positional advantage. A "show off" mode if you like :) And again, with the flip side of working to create the least humiliating losses for itself.

reacweb 11y ago
In go, the purpose is to have more territory than the opponent. There is no point in humiliating the opponent by having a big advantage. I think the aim of the strange moves was to increase the confidence of the program in its advance, not to increase the advance.
- hutzlibu 11y ago
  But you could indeed humiliate the opponent by actually capturing ALL of his stones. But that won't happen, if the enemy knows at least the basic concepts ... Still, if you play well, you cover much ground - while trying to supress the area of the enemy and even crushing him. But classic go is nice in a way, that it gives weaker opponents a start bonus of some stones - so the game is balanced and domination usually won't happen ...
  - lmm 11y ago
    My brother once played the (then) British Youth Go Champion on a 13x13 board, and lost by around 180 points - literally scoring worse than if he hadn't played at all.
- cjbprime 11y ago
  > I think the aim of the strange moves was to increase the confidence of the program in its advance, not to increase the advance. Absolutely. Also worth noting that it may be simply unable to distinguish between good and bad moves if both outcomes lead to a win, since it has no conception of the margin of victory being important. So it might not be that it increased win probability, but that both paths led to 100% win probability and it started playing "stupidly" due to lacking a score-maximizing bias.
- colanderman 11y ago
  Sorry, I didn't mean the intent would be to humiliate, just the appearance. Humans, I think, have the natural instinct to "hedge" themselves in games like go and chess, by creating positional/material advantages now to offset unknowns later. Of course, that advantage becomes useless in the end game, when all that matters is the binary win/lose. An AI, which may have a deeper/broader view of the game tree than its human opponent (despite evaluating individual position strength in roughly the same manner), may see less of a need to "hedge" now, and instead spend moves creating more of a guaranteed advantage later (as you suggest). And indeed, my experience with my AI is that during the endgame (in which an AI generally knows with certainty the eventual outcome of each of its moves), it tends to retain the smallest advantage possible to win, preferring instead to spend moves to win sooner.
  - jacquesm 11y ago
    > Humans, I think, have the natural instinct to "hedge" themselves in games like go and chess, by creating positional/material advantages now to offset unknowns later. Of course, that advantage becomes useless in the end game, when all that matters is the binary win/lose. That's actually an excellent way to win chess games. Keep your eye on the mate while the other person is focusing on position and material.
philh 11y ago
> It never actually would make the winning move – however obvious – until it had no other options! I'm confused. Why would 'make the winning move' not be the way to maximise probability of winning?
- germanier 11y ago
  That happens if the winning probability of the other move is 1 as well.
- awl130 11y ago
  maybe he's defining a "winning move" as something with > 50% chance of winning
- a1k0n 11y ago
  Usually it's because as it searches the move tree, it finds ways for the opponent to maximize their own winning probability and so has to hedge against that. In minimax games sometimes the evaluator finds a long chain of moves that leads to a win, and once it finds that, doesn't necessarily bother trying to find a shorter one. It can be frustrating to tune that out.
- colanderman 11y ago
  The AI is based on the minimax algorithm [1]. Because of the way Minimax works, the only way for a possible next move to be designated a "win" is if it is a guaranteed win. (The tree is (effectively) fully explored, and the opponent is given the benefit of the doubt in the face of incomplete information.) So, if there are multiple such winning moves, and care is not taken to distinguish the "magnitude" of the win, the AI will choose one arbitrarily. I suppose that, in Hive, it is more likely that a path to a win is longer rather than shorter. Hence, when my AI was arbitrarily choosing "winning" moves, it statistically chose those that drew the game out. [1] https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Minimax
  - ant6n 11y ago
    But once you have guaranteed winning moves, why not pick the shortest one available (in terms of turns)?
VikingCoder 11y ago
Thank you for this. Your post should be required reading in this discussion. People forget how literal computers are.

reacweb 11y ago

In go, the purpose is to have more territory than the opponent. There is no point in humiliating the opponent by having a big advantage. I think the aim of the strange moves was to increase the confidence of the program in its advance, not to increase the advance.

hutzlibu 11y ago
But you could indeed humiliate the opponent by actually capturing ALL of his stones. But that won't happen, if the enemy knows at least the basic concepts ... Still, if you play well, you cover much ground - while trying to supress the area of the enemy and even crushing him. But classic go is nice in a way, that it gives weaker opponents a start bonus of some stones - so the game is balanced and domination usually won't happen ...
- lmm 11y ago
  My brother once played the (then) British Youth Go Champion on a 13x13 board, and lost by around 180 points - literally scoring worse than if he hadn't played at all.
cjbprime 11y ago
> I think the aim of the strange moves was to increase the confidence of the program in its advance, not to increase the advance. Absolutely. Also worth noting that it may be simply unable to distinguish between good and bad moves if both outcomes lead to a win, since it has no conception of the margin of victory being important. So it might not be that it increased win probability, but that both paths led to 100% win probability and it started playing "stupidly" due to lacking a score-maximizing bias.
colanderman 11y ago
Sorry, I didn't mean the intent would be to humiliate, just the appearance. Humans, I think, have the natural instinct to "hedge" themselves in games like go and chess, by creating positional/material advantages now to offset unknowns later. Of course, that advantage becomes useless in the end game, when all that matters is the binary win/lose. An AI, which may have a deeper/broader view of the game tree than its human opponent (despite evaluating individual position strength in roughly the same manner), may see less of a need to "hedge" now, and instead spend moves creating more of a guaranteed advantage later (as you suggest). And indeed, my experience with my AI is that during the endgame (in which an AI generally knows with certainty the eventual outcome of each of its moves), it tends to retain the smallest advantage possible to win, preferring instead to spend moves to win sooner.
- jacquesm 11y ago
  > Humans, I think, have the natural instinct to "hedge" themselves in games like go and chess, by creating positional/material advantages now to offset unknowns later. Of course, that advantage becomes useless in the end game, when all that matters is the binary win/lose. That's actually an excellent way to win chess games. Keep your eye on the mate while the other person is focusing on position and material.

philh 11y ago

> It never actually would make the winning move – however obvious – until it had no other options! I'm confused. Why would 'make the winning move' not be the way to maximise probability of winning?

germanier 11y ago
That happens if the winning probability of the other move is 1 as well.
awl130 11y ago
maybe he's defining a "winning move" as something with > 50% chance of winning
a1k0n 11y ago
Usually it's because as it searches the move tree, it finds ways for the opponent to maximize their own winning probability and so has to hedge against that. In minimax games sometimes the evaluator finds a long chain of moves that leads to a win, and once it finds that, doesn't necessarily bother trying to find a shorter one. It can be frustrating to tune that out.
colanderman 11y ago
The AI is based on the minimax algorithm [1]. Because of the way Minimax works, the only way for a possible next move to be designated a "win" is if it is a guaranteed win. (The tree is (effectively) fully explored, and the opponent is given the benefit of the doubt in the face of incomplete information.) So, if there are multiple such winning moves, and care is not taken to distinguish the "magnitude" of the win, the AI will choose one arbitrarily. I suppose that, in Hive, it is more likely that a path to a win is longer rather than shorter. Hence, when my AI was arbitrarily choosing "winning" moves, it statistically chose those that drew the game out. [1] https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Minimax
- ant6n 11y ago
  But once you have guaranteed winning moves, why not pick the shortest one available (in terms of turns)?

VikingCoder 11y ago

Thank you for this. Your post should be required reading in this discussion. People forget how literal computers are.