Segmentation fault instead of playing blocking move

[fvoichick]

When there is no good move, it seems like MoHex should play the "least bad" or "most blocking" move. I've been getting an issue where it segfaults instead, which I expect is not the intended behavior.

Steps to reproduce:

1. Install the needed tools. I'm using NixOS, so to make this as reproducible as possible, I used the following shell.nix file:

   
   { pkgs ? import (fetchTarball "https://github.com/NixOS/nixpkgs/archive/refs/tags/21.11.tar.gz") {} }:

pkgs.mkShell { buildInputs = with pkgs; [ git gcc cmake boost db ]; }

The interactive Nix shell is then started with the `nix-shell` command.

2. Set up and build the project, following the instructions in the README:

git clone git@github.com:cgao3/benzene-vanilla-cmake.git cd benzene-vanilla-cmake/ mkdir build cd build cmake ../ make -j4

3. Run MoHex and try to play moves:

./src/mohex/mohex --boardsize 3 --seed 0 showboard play b b2 showboard genmove w

Expected behavior: generates and returns the "most blocking" move for white, most likely a3, b1, b3, or c1. Or, resigns.

Actual behavior: segmentation fault.

stdout:

=

e987fcd3b3ce7cac a b c
1. . .\1 2. . .\2 3. . .\3 a b c

=

=

733426b921ba3269 a b c
1. . .\1 2. B .\2 3. . .\3 a b c

stderr:

MoHex 2.0.CMake Jan 1 1980 Copyright (C) 2007-2012 by the authors of the Benzene project. This program comes with ABSOLUTELY NO WARRANTY. This is free software and you are welcome to redistribute it under certain conditions. Type `benzene-license' for details.

SgRandom::SetSeed: 1643022978 SgUctSearch: system memory 16521846784, using 1000000000 (5681818 nodes) SgRandom::SetSeed: 1 SgRandom::SetSeed: 1643022978 2bb6b info: Prior Patterns: 2bb6b info: Global: 2bb6b info: Size = 565 32648 2bb6b info: TableEntries = 65932 65910 2bb6b info: MirrorsAdded = 0 0 2bb6b info: PrunableCount = 30593 30629 2bb6b info: LargestGamma = 5820.77 2bb6b info: SmallestGamma = 6.6e-05 2bb6b info: Local: 2bb6b info: Size = 550 5318 2bb6b info: TableEntries = 11602 11588 2bb6b info: MirrorsAdded = 0 0 2bb6b info: PrunableCount = 3659 3667 2bb6b info: LargestGamma = 11281.8 2bb6b info: SmallestGamma = 0.026235 2bb6b info: Playout Patterns: 2bb6b info: Global: 2bb6b info: Size = 565 32648 2bb6b info: TableEntries = 70329 70329 2bb6b info: MirrorsAdded = 4397 4419 2bb6b info: PrunableCount = 30593 30629 2bb6b info: LargestGamma = 5820.77 2bb6b info: SmallestGamma = 6.6e-05 2bb6b info: Local: 2bb6b info: Size = 550 5318 2bb6b info: TableEntries = 11602 11588 2bb6b info: MirrorsAdded = 0 0 2bb6b info: PrunableCount = 3659 3667 2bb6b info: LargestGamma = 11281.8 2bb6b info: SmallestGamma = 0.026235 2bb6b info: Fillin caused win! Removing... 2bb6b info: Opponent has won; playing most blocking move. 2bb6b warning: curMostHits == 0!!

Exit status: `139`

[fvoichick]

Are you able to reproduce this issue? Am I using your software correctly? Do you know of any workarounds?

[fvoichick]

I ran it with --logfile-level=fine and it outputted this:

76eab config: MoHex v2.0.CMake Jan  1 1980.
76eab config: ============ InitializeSystem ============
76eab config: BenzeneProgram::InitRandom()
76eab config: Seed = 0
76eab fine: --InitializeOppMiai
76eab info: Prior Patterns:
76eab info: Global:
76eab info: Size            = 565 32648 
76eab info: TableEntries    = 65932 65910
76eab info: MirrorsAdded    = 0 0
76eab info: PrunableCount   = 30593 30629
76eab info: LargestGamma    = 5820.77
76eab info: SmallestGamma   = 6.6e-05
76eab info: Local:
76eab info: Size            = 550 5318 
76eab info: TableEntries    = 11602 11588
76eab info: MirrorsAdded    = 0 0
76eab info: PrunableCount   = 3659 3667
76eab info: LargestGamma    = 11281.8
76eab info: SmallestGamma   = 0.026235
76eab info: Playout Patterns:
76eab info: Global:
76eab info: Size            = 565 32648 
76eab info: TableEntries    = 70329 70329
76eab info: MirrorsAdded    = 4397 4419
76eab info: PrunableCount   = 30593 30629
76eab info: LargestGamma    = 5820.77
76eab info: SmallestGamma   = 6.6e-05
76eab info: Local:
76eab info: Size            = 550 5318 
76eab info: TableEntries    = 11602 11588
76eab info: MirrorsAdded    = 0 0
76eab info: PrunableCount   = 3659 3667
76eab info: LargestGamma    = 11281.8
76eab info: SmallestGamma   = 0.026235
76eab fine: --- ConstBoard (3 x 3)
76eab fine: Game::NewGame()
76eab fine: Game::NewGame()
76eab config: IcePatternSet: reading from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/ice-patterns.txt'.
76eab config: IcePatternSet: parsed 1136 patterns.
76eab fine: Data does not exist. Creating...
76eab fine: PatternMatcherData::Initialize (3 x 3)
76eab config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
76eab config: VCS:: parsed 1 patterns.
76eab config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
76eab config: VCS:: parsed 1 patterns.
76eab config: IcePatternSet: reading from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/ice-patterns.txt'.
76eab config: IcePatternSet: parsed 1136 patterns.
76eab config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
76eab config: VCS:: parsed 1 patterns.
76eab config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
76eab config: VCS:: parsed 1 patterns.
76eab fine:   7.9e-05s to find inferior cells.
76eab fine: VCPattern::CreatePatterns(3, 3)
76eab config: VCPattern: loading pattern templates from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-patterns.txt'.
76eab fine: Combining start(4) and end(16)...
76eab fine: Constructed 15.
76eab fine: Parsed 0 complete.
76eab fine: Translating, rotating, mirroring...
76eab fine: 66 total patterns
76eab fine: Done.
76eab fine:   0.000945s to build vcs.
76eab fine:   0.000165s to build vcs.
76eab fine: 0.001391s to compute all.
76eab info: Fillin caused win! Removing...
76eab fine:   4.2e-05s to find inferior cells.
76eab fine:   9.6e-05s to build vcs.
76eab fine:   9.6e-05s to build vcs.
76eab fine: 0.000305s to compute all.
76eab info: Opponent has won; playing most blocking move.
76eab fine: Intersection of smallest set is:
76eab fine:  invalid resign swap-pieces north east south west a1 b1 c1 d1 e1 f1 g1 h1 i1 j1 k1 l1 m1 a2 b2 c2 d2 e2 f2 g2 h2 i2 j2 k2 l2 m2 a3 b3 c3 d3 e3 f3 g3 h3 i3 j3 k3 l3 m3 a4 b4 c4 d4 e4 f4 g4 h4 i4 j4 k4 l4 m4 a5 b5 c5 d5 e5 f5 g5 h5 i5 j5 k5 l5 m5 a6 b6 c6 d6 e6 f6 g6 h6 i6 j6 k6 l6 m6 a7 b7 c7 d7 e7 f7 g7 h7 i7 j7 k7 l7 m7 a8 b8 c8 d8 e8 f8 g8 h8 i8 j8 k8 l8 m8 a9 b9 c9 d9 e9 f9 g9 h9 i9 j9 k9 l9 m9 a10 b10 c10 d10 e10 f10 g10 h10 i10 j10 k10 l10 m10 a11 b11 c11 d11 e11 f11 g11 h11 i11 j11 k11 l11 m11 a12 b12 c12 d12 e12 f12 g12 h12 i12 j12 k12 l12 m12 a13 b13 c13 d13 e13 f13 g13 h13 i13 j13 k13 l13 m13
76eab fine: After elimination of inferior cells:
76eab fine:  invalid resign swap-pieces north east south west d1 e1 f1 g1 h1 i1 j1 k1 l1 m1 b2 d2 e2 f2 g2 h2 i2 j2 k2 l2 m2 d3 e3 f3 g3 h3 i3 j3 k3 l3 m3 a4 b4 c4 d4 e4 f4 g4 h4 i4 j4 k4 l4 m4 a5 b5 c5 d5 e5 f5 g5 h5 i5 j5 k5 l5 m5 a6 b6 c6 d6 e6 f6 g6 h6 i6 j6 k6 l6 m6 a7 b7 c7 d7 e7 f7 g7 h7 i7 j7 k7 l7 m7 a8 b8 c8 d8 e8 f8 g8 h8 i8 j8 k8 l8 m8 a9 b9 c9 d9 e9 f9 g9 h9 i9 j9 k9 l9 m9 a10 b10 c10 d10 e10 f10 g10 h10 i10 j10 k10 l10 m10 a11 b11 c11 d11 e11 f11 g11 h11 i11 j11 k11 l11 m11 a12 b12 c12 d12 e12 f12 g12 h12 i12 j12 k12 l12 m12 a13 b13 c13 d13 e13 f13 g13 h13 i13 j13 k13 l13 m13
76eab warning: curMostHits == 0!!

[cgao3]

I think you might get rid of these if you use "wolve" instead of "MoHex". When board size is very small, only ICE is of interest. In these cases, wolve might be better as an entrance for calling ICEs. The "player" part of MoHex might not work well on small board sizes.

[fvoichick]

I just did the same thing as before, replacing ./src/mohex/mohex with ./src/wolve/wolve. I get a segmentation fault again.

stdout:

= 

  e987fcd3b3ce7cac
  a  b  c  
 1\.  .  .\1
  2\.  .  .\2
   3\.  .  .\3
      a  b  c  

= 

= 

  733426b921ba3269
  a  b  c  
 1\.  .  .\1
  2\.  B  .\2
   3\.  .  .\3
      a  b  c  

default.log:

9909b config: Wolve v2.0.CMake Jan  1 1980.
9909b config: ============ InitializeSystem ============
9909b config: BenzeneProgram::InitRandom()
9909b config: Seed = 0
9909b fine: --InitializeOppMiai
9909b fine: --- ConstBoard (3 x 3)
9909b fine: Game::NewGame()
9909b fine: Game::NewGame()
9909b config: IcePatternSet: reading from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/ice-patterns.txt'.
9909b config: IcePatternSet: parsed 1136 patterns.
9909b fine: Data does not exist. Creating...
9909b fine: PatternMatcherData::Initialize (3 x 3)
9909b config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
9909b config: VCS:: parsed 1 patterns.
9909b config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
9909b config: VCS:: parsed 1 patterns.
9909b config: IcePatternSet: reading from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/ice-patterns.txt'.
9909b config: IcePatternSet: parsed 1136 patterns.
9909b config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
9909b config: VCS:: parsed 1 patterns.
9909b config: VCS: reading captured set patterns from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-captured-set.txt'.
9909b config: VCS:: parsed 1 patterns.
9909b config: CacheBook: reading from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/wolve-cache-book.txt'.
9909b fine: --- ConstBoard (11 x 11)
9909b config: CacheBook: contains 2280 entries.
9909b fine:   2.4e-05s to find inferior cells.
9909b fine: VCPattern::CreatePatterns(3, 3)
9909b config: VCPattern: loading pattern templates from '/home/finn/Desktop/hex/benzene-vanilla-cmake/share/vc-patterns.txt'.
9909b fine: Combining start(4) and end(16)...
9909b fine: Constructed 15.
9909b fine: Parsed 0 complete.
9909b fine: Translating, rotating, mirroring...
9909b fine: 66 total patterns
9909b fine: Done.
9909b fine:   0.000359s to build vcs.
9909b fine:   6.3e-05s to build vcs.
9909b fine: 0.000526s to compute all.
9909b info: Fillin caused win! Removing...
9909b fine:   1.5e-05s to find inferior cells.
9909b fine:   4.4e-05s to build vcs.
9909b fine:   3.7e-05s to build vcs.
9909b fine: 0.000134s to compute all.
9909b info: Opponent has won; playing most blocking move.
9909b fine: Intersection of smallest set is:
9909b fine:  invalid resign swap-pieces north east south west a1 b1 c1 d1 e1 f1 g1 h1 i1 j1 k1 l1 m1 a2 b2 c2 d2 e2 f2 g2 h2 i2 j2 k2 l2 m2 a3 b3 c3 d3 e3 f3 g3 h3 i3 j3 k3 l3 m3 a4 b4 c4 d4 e4 f4 g4 h4 i4 j4 k4 l4 m4 a5 b5 c5 d5 e5 f5 g5 h5 i5 j5 k5 l5 m5 a6 b6 c6 d6 e6 f6 g6 h6 i6 j6 k6 l6 m6 a7 b7 c7 d7 e7 f7 g7 h7 i7 j7 k7 l7 m7 a8 b8 c8 d8 e8 f8 g8 h8 i8 j8 k8 l8 m8 a9 b9 c9 d9 e9 f9 g9 h9 i9 j9 k9 l9 m9 a10 b10 c10 d10 e10 f10 g10 h10 i10 j10 k10 l10 m10 a11 b11 c11 d11 e11 f11 g11 h11 i11 j11 k11 l11 m11 a12 b12 c12 d12 e12 f12 g12 h12 i12 j12 k12 l12 m12 a13 b13 c13 d13 e13 f13 g13 h13 i13 j13 k13 l13 m13
9909b fine: After elimination of inferior cells:
9909b fine:  invalid resign swap-pieces north east south west d1 e1 f1 g1 h1 i1 j1 k1 l1 m1 b2 d2 e2 f2 g2 h2 i2 j2 k2 l2 m2 d3 e3 f3 g3 h3 i3 j3 k3 l3 m3 a4 b4 c4 d4 e4 f4 g4 h4 i4 j4 k4 l4 m4 a5 b5 c5 d5 e5 f5 g5 h5 i5 j5 k5 l5 m5 a6 b6 c6 d6 e6 f6 g6 h6 i6 j6 k6 l6 m6 a7 b7 c7 d7 e7 f7 g7 h7 i7 j7 k7 l7 m7 a8 b8 c8 d8 e8 f8 g8 h8 i8 j8 k8 l8 m8 a9 b9 c9 d9 e9 f9 g9 h9 i9 j9 k9 l9 m9 a10 b10 c10 d10 e10 f10 g10 h10 i10 j10 k10 l10 m10 a11 b11 c11 d11 e11 f11 g11 h11 i11 j11 k11 l11 m11 a12 b12 c12 d12 e12 f12 g12 h12 i12 j12 k12 l12 m12 a13 b13 c13 d13 e13 f13 g13 h13 i13 j13 k13 l13 m13
9909b warning: curMostHits == 0!!

echo $? gives 139.

[cgao3]

I just tried on my machine, worked fine for me..

/benzene-vanilla-cmake/build# ./src/wolve/wolve
Wolve 2.0.CMake Aug 23 2019
Copyright (C) 2007-2012 by the authors of the Benzene project.
This program comes with ABSOLUTELY NO WARRANTY. This is
free software and you are welcome to redistribute it under
certain conditions. Type `benzene-license' for details.

SgRandom::SetSeed: 1643515824
boardsize 3
=

showboard
=

  e987fcd3b3ce7cac
  a  b  c
 1\.  .  .\1
  2\.  .  .\2
   3\.  .  .\3
      a  b  c

play b b2
=

genmove w
26907 info: Fillin caused win! Removing...
26907 info: Opponent has won; playing most blocking move.
= b1

showboard
=

  689e69317521c4f9
  a  b  c
 1\.  W  .\1
  2\.  B  .\2
   3\.  .  .\3
      a  b  c

[cgao3]

I now suspect last commit from Nicolas introduced a bug (guess he should have been pushing to his nf branch)... You can try rollback to a commit before that and see if it works.

[fvoichick]

Confirmed. It seems the issue is several commits back. The segfault occurs when I do git checkout eef3347194432e537e15a0fa083bc780465f8cfc, but not when I do git checkout 492a2e3d37711369f1d3d59682d6b6011f48cf9b. It seems that @NicolasFabiano introduced the issue in commit eef3347194432e537e15a0fa083bc780465f8cfc.

[NicolasFabiano]

Yes, I'm sorry, I was new to git at this time and when time came to push I realized I did it totally wrong... I'll have a look to see if I can find when the bug comes from.

[NicolasFabiano]

I found where the bug comes from. When it finds that the game is lost, it considers all the possible moves. First, it iterates through the carriers of the virtual connections to take a small intersection of them. Then, among those that remain, it removes the inferior ones, provided that the rest is not empty.

The problem is that, when fillin causes the game to be won without a virtual connection, we take no intersection in the first step, so that in the second step all the gardage moves (like "resign" or the moves outside of the actual board) remain. Then, if all the moves inside the board are inferior, they are all removed (it thinks that it is ok because the rest is not empty). But you end up with only garbage moves and it fails.

I'm not sure how the bug has been caused by my changes. Maybe the fillins were considered to have a carrier in the previous version. Or maybe improving the pruning now lets me detect the whole board as inferior while it was not before. But anyway I guess that some edge cases could make the same problem occur for some well-chosen boards in the previous version.

@cgao3 The problematic function is MostOverlappingMove, in EndgameUtil.cpp . There are several possible straightforward fixes, can I let you choose your favorite?

[cgao3]

@NicolasFabiano Sure, feel free to do so..

[NicolasFabiano]

@cgao3 I can't contribute anymore to the git. Could you give me your new adress so I can send you the file? (the adress I have seems not to be up to date)

[cgao3]

Do want me to put it to Master branch or your nf branch?

[NicolasFabiano]

The fix is for the master branch, given the bug occurs in it.

Actually, the nf branch does not really have any reason to exist any more. I apparently have not applied all to master, this should be done too. The commits "tabs to space" and "Bug fix in precomputation" should be merged. I am a bit surprised by "Fix in misc-patterns.txt" : I remember doing it later than other commits, but is way clearly way before Feb 3, 2022. But I have had a look at it and this is indeed what I remember doing, it should be merged too. And there is a fourth commit, "standalone decomposition player, refined by David Pankratz", which I have no idea what it is.

[fvoichick]

@NicolasFabiano maybe you should fork this repo and create a pull request with all of the commits needed to fix the main branch, so it’s easier for @cgao3 to review and merge the fixes

[cgao3]

I've pushed the fixed version of "EndgameUtil.cpp" to the nf branch.

[lukaemon]

Confirmed. It seems the issue is several commits back. The segfault occurs when I do git checkout eef3347194432e537e15a0fa083bc780465f8cfc, but not when I do git checkout 492a2e3d37711369f1d3d59682d6b6011f48cf9b. It seems that @NicolasFabiano introduced the issue in commit eef3347.

Face the same problem. This one works for me.