IBM's computer only stores 5 qubits.
The biggest quantum computers only store 1000 qubits.
No. For now.
MW
Is it time to start developing the next generation of game playing
algorithms?
http://www.research.ibm.com/quantum/
___
Computer-go mailing
One question is whether Lee Sedol knows about these weaknesses.
Another question is whether he will exploit those weaknesses.
Lee has a very simple style of play that seems less ko-oriented
than other players, and this may play into the hands of Alpha.
Michael Wing
I was surprised the Lee
In my opinion, the thing that programs do worst is ko.
Lee did not play any kos, except one minor irrelevant
one in the lower left. This game was so simple that
the program could accurately model the whole board.
If Lee wants to win, he needs to start 2 or 3
simultaneous kos.
Michael Wing
: 67% 67% 67% 67% 67% 67% 67% 67%
Hyper-threading works pretty well on the i7.
So, with little cache conflict, you should expect about
5.33 times as much work, as a single processor,
which is useful to know.
Michael Wing
___
computer-go mailing list
architecture. because
of the larger, faster L2 cache doubly linked lists may work well.
I have a code generator that makes it (somewhat) easy to try this out:
http://pages.swcp.com/~wing/cgbg/
Of course, writing out the different implementations yourself is a good
exercise to help understand
Wing
I've seen bit-maps mentioned many times, but is there any evidence
it's faster than a 'traditional' implementation?
You can also use board-sized bitmaps. Merging is a trivial OR
operation.
___
computer-go mailing list
computer-go
In the cgbg framework, arrays and lists are unsorted.
But, there are many reasonable variations.
You will just have to jump in and read some code or write
your own to fully understand. I recommend reading the
gnugo source, which is pretty darn good.
Michael Wing
How do these link list
£ukasz,
My code is online in the directory:
http://pages.swcp.com/~wing/cgbg/
The file cgbg is a ruby program, which
generates a C program, as well as a performance
test. So the only difference is the
desired distinction.
My implementation of dense links is similar
to, but not identical
, linked lists have horrible cache behavior.
* So, as far as I can see the only question is whether you will
do any classic reading or not, which will determine the
best implementation.
Michael Wing
---
DENSE LINKS
normal 324 moves: total 3000 ms, each game 0.30 ms
. (A chain can only have about 2/3 of
the locations on the board as liberties, if you
follow the usual rules.) This overwhelms all
other data in the board.
Michael Wing
I made some artificial tests where I do x inserts, 1 delete, 10 counts and
1 merge. For x=4 inserts, linear arrays are about 4 times
ways, but gnugo has all of the good ideas.
Michael Wing
PS: Here is the data for how many times the program tried to insert
a stone into a chain that has x liberties or x adjacencies. It was taken
from a run that combined monte carlo simulations and ladder reading
exercises. Note
, it works with the cache
to maximize locality. Second it is very simple.
Michael Wing
Many Faces also counts real liberties, and is quite fast enough.
I can confirm, with a bit of optimization, counting real liberties is
only marginally slower than counting pseudo-liberties. So there's
more than
1 rank. Further improvement will require new ideas.
Michael Wing
By the way, does anybody know of any nifty tools or heuristics for
efficient probabilistic multi-parameter optimization? In other words,
like multi-dimensional optimization, except instead of your function
returning
])
{ triple ko }
Michael Wing
Michael Williams:
You might be speaking in general terms, I'm talking about a
specific test for full-board repetition due to triple ko.
In this case the sequences that you are comparing would be
the same length. So the test would look something like this
(forgive me
Jacques,
(Offline)
Are you saying that you copy the whole board for each move,
when you have a stack of boards?
Thanks,
Michael Wing
Well, every implementation is different. In its slowest
mode, my board stores information about neighbor stones
in each cell. It has a stack of boards
am not sure exactly what undo costs, but lets say
5% to 10%.
I do local analysis, so I pay for undo anyways.
But, if you were doing MC only, then you could go 5%
to 15% faster if you remove superko checking and undo.
Michael Wing
Michael Wing wrote:
In my program (which implements undo
is also small, but might be
worth a tiny amount of effort.
* Some kind of study to measuring the ELO cost of bad
suicide and ko decisions would be useful.
* I plan to detect both suicide and superko on principle,
confident that it doesn't make much difference.
Michael Wing
Don Dailey [EMAIL
Mark,
Don did say that doubling the speed of a machine is
100 ELO. See the thread at
http://www.mail-archive.com/computer-go@computer-go.org/msg05358.html
I believe that beating someone 2:1 is 100 ELO.
So, if ignoring suicide is at most 1 ELO, then it doesn't matter.
Michael Wing
P.S. I should
is just a wild guess. Yet, I
stand by my analysis.
Michael Wing
I think you are off on the relative importance of superko and suicide
and it seems that your values are rather arbitrary - just made up.
First of all, we are only talking about detection in the play-outs, not
in the tree search
reasonably well, too. See below.
Michael Wing
www.swcp.com/~wing/cgbg
---
The Critters Go Board Generator
Michael Wing
January 15, 2008
Ive wanted to develop a fast go board for many years, and have spent
the last few months helping write a go board generator to figure out what
fast
terry mcintyre [EMAIL PROTECTED] said:
www.swcp.com/~wing/cgbg
I visited the www page, and the combination of pre with
very long lines does not work well at all. Tried both firefox
and IE. pre prevents the browser from wrapping the text to
fit the display page.
Thanks. Reformatted
/zobrist.pdf.
Michael Wing
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
that
the sum of say 20 liberties takes more than 32 bits.
One solution is to use 64 bits for pseudo liberties.
Another solution is keep a count of PLs, and also
a 32 bit unsigned PL value, igoring overflow, and
only check the PL value when the PL count is less
than 5.
-- Michael Wing
// --- code
the solution by Eric Boesch that used bit masking and no
random numbers?
I saw it, but I didn't understand it. However, since it does array
references inside a for loop, it probably does at least as many
memory accesses as this solution.
-- Michael Wing
* These numbers are small enough
Jason,
I realize that I was looking at the IsOneSum() constructor,
which had the array lookups. My bad. I just didn't
understand how it worked.
-- M
On Sat, 2007-11-24 at 10:36 -0700, [EMAIL PROTECTED] wrote:
Since 160,000 2*(19*19)^2, a value well below the various possible
sums of
and compiler
intelligence. Neither can replace the other.
Please use both.
Michael Wing
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
algorithms
and data structures.
Michael Wing
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Because many optimizations take exponential or worse
time to figure out if they apply. This means that
the sun would explode before your compile would finish.
Yes, compilers will get more sophisticated over time.
No, they will not replace any algorithms or data structures.
Michael Wing
Why
28 matches
Mail list logo