Re: Benson Rules!

[mueller@xxxxxxxxx (Martin Mueller)]

> I studied your thesis and even started to implement some code
>when I was implementing the scoring for pubgo (many thanks for
>making your work public).
>
>I found that to implement the scheme for a general case
>(many strings and false eyes etc) would have required a considerable
>effort (in terms of program structure). The problem is deciding which
>strings are the focus of the algolrithm. It looked like you would
>need to try all combinations or have some heuristics for flaging
>a stable core. I am missing something ?
>

Yes, you're missing something, but you're not the first :)
It is the main difference between Benson's first and second paper, an
improvement in the algorithm. The same idea also works for my definitions
of 1-vital and 2-vital. Instead of computing small sets and making them
bigger, you go the other way.
You initially make a set as big as possible, and then throw out those
blocks that don't have 2 healthy regions.

I guess code says it better than words, so I have attached the core
routines below. These are used by all solvers, such as BensonSolver and my
own VitalSolver. VitalSolver computes 2-vital regions (regions that already
provide 2 sure libs for a neighboring block) before calling this.

>
> I also came to the conclusion that us humans do not think like this.
>In the end I just used a brute force search to detect life / death.
>

I agree that humans don't initially work like this. However, as a player I
have also found it useful to think about these fundamentals.

        Martin

The following is actual code from Smart Go Board/Explorer, with some
debugging  #if's removed. This code is not in the public domain and is
given for illustration purposes only.

void BasicSolver::FindSafePoints (BWSET& safe)
{
        GenBlocksRegions (); // find all blocks and regions on whole board

        for (BlackWhite col = fBlack; col <= fWhite; col++)
        {
                ListOf<ListOf<BBlock> > sets;
                FindTestSets (sets, col); // find maximal sets for
aliveness testing

                for (ListIteratorOf<ListOf<BBlock> > it (sets); it; ++it)
                {       TestAlive (**it, safe, col); // find safe subset
within each maximal set
                        delete *it; // new 96-02-05
                }
        }
} // FindSafePoints

void BasicSolver::FindTestSets (ListOf<ListOf<BBlock> > & sets, BlackWhite col)
{
        ASSERT(sets.IsEmpty());

        ListOf<BBlock> doneSoFar;
        for (ListIteratorOf<BBlock> it (AllBlocks (col)); it; ++it)
        {       BBlock* block = *it;
                if (!doneSoFar.Contains (block))
                {
                        ListOf<BBlock>* blocks = new ListOf<BBlock>;
                        blocks->Append(block);

                        FindClosure(*blocks);
                        doneSoFar.Concat(&ListOf<BBlock>(*blocks)); // copy
constructor,

// to avoid deleting blocks list
                        sets.Append (blocks);
                }
        }
} // FindTestSets

void BasicSolver::FindClosure (ListOf<BBlock>& blocks)
// compute closure of blocks set: expand set of blocks until
// all blocks adjacent to all adjacent regions are in set.
// see [Benson] for explanation.
{
        ListOf<BBlock> toTest = blocks;

        while (toTest.NonEmpty())
        {
                const BBlock* b = toTest.Pop();
                for (ListIteratorOf<Region> it (b->m_healthy); it; ++it)
                {       Region* r = *it;
                        for (ListIteratorOf<BBlock> it (r->m_blocks); it; ++it)
                        {       BBlock* b2 = *it;
                                if(!blocks.Contains(b2) &&
b2->m_healthy.Contains(r))
                                {
                                        blocks.Append(b2);
                                        toTest.Append(b2);
                                }
                        }
                }
        }
} // FindClosure

void BasicSolver::TestAlive (ListOf<BBlock>& blocks, BWSET& safe,
BlackWhite color)
// Test if list of Benson blocks forms a living group.
//      Each block must have a sure liberty count of at least 2.
//      A region provides one sure liberty if it is healthy and its
boundary consists
//      only of blocks in the list.
{
        ListOf<Region> regions = AllRegions(color);

        bool changed;
        ListOf<BBlock> toDelete;
        do
        {
                TestAdjacent (regions, blocks);
                toDelete.Clear();
                for (ListIteratorOf<BBlock> it (blocks); it; ++it)
                {
                        ListOf<Region>& br = (*it)->m_healthy;

                        bool has2 = br.MinLength(2);
                        if (has2)
                        {
                                int nuRegions = 0;
                                for (ListIteratorOf<Region> it(br); it; ++it)
                                {
                                        if (regions.Contains(*it))
                                        {
                                                nuRegions++;
                                                if (nuRegions >= 2)
                                                        break;
                                        }
                                }
                                has2 = (nuRegions >= 2);
                        }
                        if (!has2)
                                toDelete.Append(*it);
                }

                changed = toDelete.NonEmpty();
                if (changed)
                {
                        for (ListIteratorOf<BBlock> it (toDelete); it; ++it)
                                blocks.Exclude(*it);
                }
        } while(changed);

        if (blocks.NonEmpty())
        {
                PointSet blockPoints;
                for (ListIteratorOf<BBlock> it (blocks); it; ++it)
                {
                        blockPoints |= (*it)->Stones();
                }

                color = blocks.Top()->Color(); // **** setting it once
would be enough..
                safe [color] |= blockPoints;

                {       for (ListIteratorOf<Region> it (regions); it; ++it)
                        {       if      ((*it)->HealthyForSomeBlock (blocks))
                                {       safe [color] |= (*it)->Points();
                                }
                }       }
        }
} // TestAlive