[computer-go] Pure light playout + RAVE bot.

2009-12-18 Thread Łukasz Lew
Just FYI:
Bots: e.21a e.21b e.21c e.21d on CGOS
are identical and make 100k light playouts per move. And have MCTS+RAVE.

Regards,
Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Public Mogo binary is release 3 or 1?

2009-11-13 Thread Łukasz Lew
Why linux mogo downloaded here:
http://www.lri.fr/~gelly/mogo/MoGo_release3.tar.gz

when faced with version GTP command, returns
= MoGo release 1. Please read http://www.lri.fr/~gelly/MoGo.htm for
more information. That is NOT an official developpement MoGo version,
but it is a public release. Its strength highly depends on your
hardware and the time settings.

?

Is windows any different?

Regards,
Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] MoGo and Fuego question.

2009-11-13 Thread Łukasz Lew
Hi,

Is there a way to set up  MoGo so it has the same playing strength
independently of the CPU and other factors?
For instance fixing number of playouts per move?

The same question to Fuego developers.
Will I achieve this effect with this command?
uct_param_player max_games 10

Thanks,
Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Generalizing RAVE

2009-10-13 Thread Łukasz Lew
It's not available online, but I will send it if someone ask me to.
(in private e-mail)
Lukasz

2009/10/13 Petr Baudis pa...@ucw.cz:
 On Fri, Sep 25, 2009 at 11:51:21AM +0200, Łukasz Lew wrote:
 I tried CRAVE in my master thesis 4 years ago. The context was a
 growing decision tree.
 It didn't work as well.

 This sounds similar to one idea of mine; is your thesis available
 anywhere? (Or any other material published on CRAVE.)

 Thanks,

                                Petr Pasky Baudis
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Generalizing RAVE

2009-09-25 Thread Łukasz Lew
I tried CRAVE in my master thesis 4 years ago. The context was a
growing decision tree.
It didn't work as well.

Lukasz

On Fri, Sep 25, 2009 at 06:19, David Fotland fotl...@smart-games.com wrote:
  Tried CRAVE also, using 3x3 patterns as the context.  It didn't work.

 David

 -Original Message-
 From: computer-go-boun...@computer-go.org [mailto:computer-go-
 boun...@computer-go.org] On Behalf Of Peter Drake
 Sent: Thursday, September 24, 2009 12:00 PM
 To: Computer Go
 Subject: [computer-go] Generalizing RAVE

 RAVE is part of a larger family of algorithms. In general we can use
 direct Monte-Carlo results (i.e., the move played directly from a
 node) to determine the probability of winning after playing such a
 move. The generalized RAVE (GRAVE?) family does this by including
 (usually with some discount) moves played on similar boards.
 Different algorithms in this family count different boards as similar:

 Basic MCTS (i.e., UCT) without a transposition table counts no other
 boards.

 A transposition table counts identical boards, i.e., those with the
 same stones on the board, player to move, simple ko point, and number
 of passes.

 AMAF counts all boards.

 RAVE counts boards that follow the current board in a playout.

 CRAVE (Context-dependent RAVE) counts boards where the neighborhood of
 the move in question looks similar. Dave Hillis discussed one
 implementation for this. I tried another; it works better than plain
 MCTS, but not as well as RAVE.

 NAVE (Nearest-neighbor RAVE) counts some set of boards which have a
 small Hamming distance from the current board. Literally storing all
 board-move pairs is catastrophically expensive in both memory and time.

 DAVE (Distributed RAVE) stores this information holographically,
 storing win/run counts for each move combined with each point/color
 combination on the board. Thus, there are a set of runs for when a2 is
 black, another for when e3 is vacant, and so forth. To find the values
 for a particular board, sum across the points on that board. This is
 too expensive, but by probing based on only one random point, I was
 able to get something that beats MCTS (but not RAVE).

 The following are left as exercises:

 http://www.onelook.com/?loc=rz4w=*avescwo=1sswo=1

 It's conceivable that some statistical machine learning technique
 (e.g., neural networks) could be applied, with the playouts providing
 data for the regression.

 The more I study this and try different variants, the more impressed I
 am by RAVE. Boards after the current board is a very clever way of
 defining similarity. Also, recorded RAVE playouts, being stored in
 each node, expire in an elegant way. It still seems that RAVE fails to
 exploit some sibling information. For example, if I start a playout
 with black A, white B, and white wins, I should (weakly) consider B as
 a response to any black first move.

 Peter Drake
 http://www.lclark.edu/~drake/



 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Is RAVE weighting biased?

2009-09-03 Thread Łukasz Lew
On Wed, Sep 2, 2009 at 19:45, Matthew Woodcraftmatt...@woodcraft.me.uk wrote:
 Łukasz Lew wrote:
 If the weight in RAVE formula is near 1 in one child of tree and near
 0 in other then you basically compare RAVE value to regular average
 value, which might be comparing apples to oranges.

 Yes, and this can cause problems in practice. There's been some
 discussion of this before.

Can you give me a link or date?

Lukasz


 In positions where the RAVE values tend to be too high, the effect is
 that moves with few visits will be favoured, which will then equalise
 the RAVE weight again. The effect is rather like temporarily increasing
 the exploration coefficient, and nothing very bad happens.

 But in positions where the RAVE values are too low (which mostly means
 positions where the current player is winning), the effect is worse: the
 program will be reluctant to explore different moves, and this time
 there is positive feedback (the RAVE weights will diverge) and so the
 situation won't correct itself.

 -M-
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Is RAVE weighting biased?

2009-09-02 Thread Łukasz Lew
If the weight in RAVE formula is near 1 in one child of tree and near
0 in other then you basically compare RAVE value to regular average
value,
which might be comparing apples to oranges.

Have you ever tried to use the same weight for every move considered
(every child in the tree)?


Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Bitmap Go revisited and mockup implementation

2009-08-24 Thread Łukasz Lew
2009/8/24 René van de Veerdonk rene.vandeveerd...@gmail.com:
 David,
 Confession: I have not tested 19x19. As you have noted, and others before
 you over the years, a 19x19 board does not fit in one but three 128-bit
 registers and there would be a rather big penalty as a result, perhaps
 (likely?) wiping out all of the benefits of bitmaps. Antoine voiced his
 disappointment about the speed advantage even on 9x9 in the e-mail to the
 list that served as my basis. My hope, as Hideko Kato points out, is in
 longer registers or perhaps being able to port this to a GPU. A 64-bit OS
 with twice the number registers would also surely help out. Nevertheless, I
 was surprised that I was able to get to almost the same level of speed as
 Libego provides.

Libego provides 105-108 kpps on a single Core2 2.4 GHz on 9x9.
and 22-23 kpps on 19x19

Can you test your bitmap implementation on 19x19?

Lukasz

 The goals for this mockup were very humble: (1) to provide a basic
 implementation to see what it can do (and if I could do it), and (2) learn
 how to work with assembly and/or intrinsic functions (I had never done that
 before). It may not be too hard to try 19x19 and just see what happens. I
 may attempt this as a follow-up.
 René van de Veerdonk
 2009/8/23 David Fotland fotl...@smart-games.com

 How much would you lose for 19x19 board?  A board representation is not
 very interesting unless it scales to 19 line boards.



 David



 From: computer-go-boun...@computer-go.org
 [mailto:computer-go-boun...@computer-go.org] On Behalf Of René van de
 Veerdonk
 Sent: Sunday, August 23, 2009 1:11 PM
 To: computer-go@computer-go.org
 Subject: [computer-go] Bitmap Go revisited and mockup implementation



 Hi all,



 After years of reading this very interesting list, I decided to make my
 first contribution this week after reading once again about bitmap go. There
 is no freely available implementation of a bitmap based engine that I know
 of, so here is a start. Note that I am not a professional programmer,
 self-taught, and this is a part-time hobby, so do not expect perfect form.



 The attachment is an attempt to create an efficient implementation of a
 bitmap based light playout engine, following mostly the recommendations as
 spelled out by Antoine de Maricourt in his November 2006 message to this
 list. The application is single threaded and achieves around 75-80 kpps on
 my Centrino Duo 2.4 GHz Intel labtop. The mockup was developed in C/C++
 using the Microsoft Visual Studio 2008 IDE for Windows XP (32-bit) and
 undoubtedly suffers from portability issues as a result. The 128-bit SSE
 instructions are called through intrinsic functions, hopefully at least
 these interfaces are the same for other compilers. The single goal of this
 mockup was to do some benchmarking, so there is no gtp-interface, but that
 would be rather easy to add for those skilled in the art. The standard rules
 are used with one exception, the Brown eye-rule is used. Multi-stone suicide
 is explicitly forbidden. No superko checks are performed during playouts,
 and there is no mercy-rule either.



 I would be particularly interested to know if a 64-bit OS will improve the
 performance significantly, as it does have a lot less register pressure.
 Moving to a 64-bit OS will also make some instructions available that allow
 for further simplifications/efficiency improvements in the code. As will
 enabling SSE3 or SSE4.1 instructions.



 One note, the random number generator used is from Agner Fog's public
 library and was not included in the attachment. You will have to provide a
 random number generator yourself or download the appropriate version from
 his well-known website (www.agner.org/optimize)



 I hope this is the start of a discussion about further improvements that
 can be made, but you may use this code as you wish with no restrictions or
 guarantees. See the readme.txt file included in the attachment for more
 details (also partially included below).



 Comments and feedback welcome,



 René van de Veerdonk



 Excerpts from the readme.txt file:



 Introduction:

 =



 Mockup of a high performance implementation of the game of Go using
 bitmaps

 as the principle datastructures. This implementation is limited to
 measuring

 the performance of the principle components by playing random playouts
 from

 an empty 9x9 board, using Chinese scoring, not allowing pass moves until

 no other moves are available. Suicide is not allowed, neither for single

 or multi-stone groups. No checks are implemented for superko, but simple

 ko's are disallowed explicitly.



 Some implementation details:

 



 Benchmarking is done in test_board.cpp, where the number of playouts (n)
 and

 repeats (j) for each test is set. Benchmarking is done starting from an
 empty

 9x9 board until two (three with ko) passes are played in sequence. The

 benchmark playout follow the same scheme as method
 

Re: [computer-go] Re: Havannah - Go - LittleGolem

2009-06-22 Thread Łukasz Lew

 In Havannah, there are not many bots. And, in the meantime
 the programmers have marked their profiles accordingly.


Profiles don't help. On LG you just click register and you are paired.
Can you post a link to computer Havannah forum/thread? I was looking
for it on LG few weeks ago and couldn't find it.

 PS: Perhaps your negative view is a consequence of the doubtful honour
 that you were the first really strong player who lost to a bot on
 Havannah board of size 8. I think the funny final position of that
 game will become part of the history of Havannah
 http://www.littlegolem.net/jsp/game/game.jsp?gid=1056604

I'm not strong at all :) And in this game I confused the rules of
havannah. (it is not interesting)
I lost a much more interesting game here:
http://www.littlegolem.net/jsp/game/game.jsp?gid=1044847
Have fun with analyzing it :)



 --
 GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT!
 Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Havannah - Go - LittleGolem

2009-06-21 Thread Łukasz Lew
Try this link
http://www.littlegolem.net/jsp/games/gamedetail.jsp?gtid=havannah
(not sure if it works if you don't have an account).

Personally I'm really annoyed by many of these bots, because they do
not resign and play all possible forcing moves so
the games can be really long which is an issue on turn based servers.

Moreover they enter tournaments, so if you want to play in them you
have to play with these bots.

Lukasz Lew

On Sun, Jun 21, 2009 at 20:29, Michael
Williamsmichaelwilliam...@gmail.com wrote:
 Are the games archived?  Does the public have access to those archives?

 Ingo Althöfer wrote:

 Hello,

 some time ago I had asked if discussions on computer Havannah were
 welcome here in the list.
 The reactions were positive, but (by different
 reasons) actors preferred not to use the opportunity.

 In the meantime a computer Havannah scene has
 developed on the game server
 http://www.littlegolem.net

 There it is possible to play Havannah on many different
 board sizes (side lengths 4, 5, 6, 7, 8, 9, 10).
 Active programmers are Thomas Reinhardt (D, with TOBRT), Richard Lorentz
 (US, with Wanderer), Richard Pijl (NL, with
 gambler), ab (=anonymous, D, with havai). On small boards (4 and 5) the
 computers are doing really well in the meantime,
 but from size 6 on their games look strange.

 It is also possible to run  *** GO  bots *** there, for instance
 Gnugo is doing so.

 
 Some more information on LittleGolem:

 * Registration is required, but it is without cost, easy,
 and without complications.

 * Thinking time per move is 36 hours in the average (with
 a buffer of 240 hours; and 20 days of vacation per year).

 * It is good style to choose names of the type xxx_c for computer
 accounts. If you do not do this, you should write at least in the profile
 that a computer is playing.

 * Some participants on LittleGolem are not playing, but only
 participating in the interesting fora (one general forum; one
 special forum for each game). For new players it reqires to
 have some games completed, otherwise you can not write, but only
 read. (This is a measure against spam bots.)

 * At the moment there is, for each player, only one go rating (showing
 performance on 9, 13, 19) and only one Havannah performance,
 mixed over all board sizes. But I think there is some hope that this
 general rating will be split in size-dependent ratings again.

 Feel free to join LittleGolem.
 Ingo.

 PS: My account on Little Golem is Ingo Althofer.
 http://www.littlegolem.net/jsp/info/player.jsp?plid=11860

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Cgos server progress

2009-06-21 Thread Łukasz Lew
Hi Don,

Will a webpage change?
In particular, will we get access to archived games?

Lukasz

2009/6/22 Don Dailey dailey@gmail.com:
 The new cgos server is almost ready - but needs some more polishing up.

 I have an instance of it running while testing 50 programs using 3 different
 computers and it appears to be robust so far, after fixing some bugs of
 course.

 I am trying to crash it by killing the connections and killing the processes
 and anything malicious I can do.   So far so good.

 It's a single server, not separate servers.   For instance this one server
 could support many different board sizes and/or time controls, etc.  These I
 call venues and each is handled as if it's running on a separate server
 even though it isn't.  Even login names and passwords are separate as is the
 rating systems.

 It's coded in C and it really feels fast.   Low memory, low CPU overhead and
 very resource friendly.

 It's not quite ready yet,  but I will probably be calling for some testing
 soon.   I want to take the old CGOS off-line and run this one a few days to
 work out any glitches before going official with it.  The client (and
 any clients that any of you have built) will require a very simple
 modification.    I was able to change the regular CGOS client in just a
 minute or two.    The modification is required to support venues (to specify
 which board size you want to play on.)

 I will make it so the old client will still work but the venue will be a
 specified default (which will be 9x9, 5 minutes.)

 I plan to let the server itself play games too,  but only to fill out the
 case where there are no players available.  You will be able to play on any
 ODD board size from 9x9 to 19x19 although it probably won't be much fun
 unless there are a few others playing on those boards too, but you would
 always be able to get a game even if it was by the weak server player.

 I'm of course interested in an algorithms for playing relatively strong move
 instantly for the server.   Something along the lines of Lardo, which has no
 search and does not do simulations or anything iterative or recursive like
 this.   Just a set of trivial rules.   Lardo is about 700 ELO on 9x9,
 substantially stronger than random of course.    I may experiment with
 bulding such a bot.   The initial server fill in player may play mostly
 random however until I take the time to do this.    I don't remember the
 rules I used in Lardo, and I don't even know if I still have the source code
 for it,  but I think the rules are documented in this forum somewhere.

 Boardsize 9 will be 5 minutes and each additional odd board size higher will
 add 2 minutes.    As it turns out, this works out for 19x19 to be 15
 minutes.

 Currently,  I plan to use komi of 7.5 for everything.   It seems like this
 is a reasonable choice since both the 9x9 and 19x19 server are using 7.5.




 - Don



 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] cgos clients

2009-06-17 Thread Łukasz Lew
On Wed, Jun 17, 2009 at 08:11, Christian
Nentwichchrist...@modeltwozero.com wrote:
 Lukasz,

 your client doesn't seem to be displaying all the info for some reason:

  -c specified name of config file - this is MANDATORY
 -k sepcifies a file to create which will stop client after current game
 -p specifies which player plays first game
 -s display a sample configuration file to stdout and exit 


I just didn't paste it.

 If you add multiple engines, the priority fields will be added up,
 normalized to 1.0 and a player will be chosen probabilistically.

Thanks.
Somehow I assumed that all the programs are run in parallel.


 Christian
 p.s. remember also http://cgos-python.sourceforge.net/, which does not have
 this feature (yet!), but has others :)

nice. Thanks


 On 17/06/2009 00:29, Łukasz Lew wrote:

 Hi,

 I have a couple of question about cgos client programs.

 Why there are two links to clients 32bit linux?

 The first one is on page
 http://cgos.boardspace.net/9x9/
 http://cgos.boardspace.net/public/cgos3-x86_32.zip
 and is broken, but the page refers to it as version 1.1 compared to
 the one on the main page
 http://cgos.boardspace.net/
 http://cgos.boardspace.net/software/cgosGtp-linux-x86_32.tar.gz
 which works but the version is 0.98.

 Can I add some more engines to config file without restarting cgos client?

 What is the -p PLAYER_FIRST option ?

 cgosGtp 0.98 alpha - engine client for CGOS Linux-x86_64 by Don Dailey
 Usage: /home/lew/cgos/cgosGtp-linux-x86_64/main.tcl  -c CONFIG_FILE
 -k KILL_FILE  -p PLAYER_FIRST -s

 What is the priority in config file?

 Thanks
 Lukasz
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/



 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] New CGOS - need your thoughts.

2009-06-16 Thread Łukasz Lew
Maybe we could agree that 1 day out of 7 in a week would be played on
6 times faster time controls.
The same bots, connections, logins, the same number of games per week.
Different rating of course.
This would be a problem only for hardcoded bots with no time control.

The advantage would be that we would see how different algorithms (bots) scale.
If the ratings would be very similar for most bots, it would mean that
we can get faster testing of new ideas.
We would know which ideas can be tested of fast time control.

Lukasz

2009/6/16 Don Dailey dailey@gmail.com:
 From what I can see, there is resistance to this idea - so what I'm going
 to do is to provide venues which are standalone but makes it possible later
 to add a time control.    In other words for now there will be only 1 time
 control per board size but the server will be flexible enough that other
 venues can be added if the server ever gets popular enough that we have 40
 or 50 players always on line.   But they will be separate venues scheduled
 independently.


 - Don


 On Tue, Jun 16, 2009 at 8:08 AM, Isaac Deutsch i...@gmx.ch wrote:

 I'm voting for 2 time settings: One normal and one fast (so maybe 5 min
 and 1 min on 9x9).
 --
 GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT!
 Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Re: Core i7 performance in computer-go

2009-06-07 Thread Łukasz Lew
2009/6/6 Hideki Kato hideki_ka...@ybb.ne.jp:
 Hi Lukasz,

 I have five core2 and one i7 computers running at home.  I prefer i7,
 though don't have exact measure.

 The most important difference is the memory interface, ie, core2
 uses a obsolete common bus (FSB) while i7 uses p2p connection with
 an internal (on chip) memory controller.  Also, core2 uses DDR2
 (obsolete) and i7 uses DDR3 memory modules.

I know the technical differences. I just wonder do they matter in
practice of computer-go



 On overclocking, i7 performs better.  i7 920 (cheapest model) runs at
 3.6 GHz (C0 stepping; recent D0 is said at 4 GHz) while core2 Q9550
 (middle range model) runs at 3.2 GHz, with a rather silent air
 cooling.

thanks.


 If you have a benchmark program please send me.  Ubuntu Linux or
 WIndows XP is fine.


http://www.mimuw.edu.pl/~lew/engine.gz
please run with:
./engine --seed 123 -b

FYI it tests only the processor, not the memory and is optimized for core2.

 Ah, I don't prefer two sockets SMP computers since we will have hexa
 and octa core chips soon (next year? I don't remember).

I agree.


 Hideki

 Łukasz Lew: c55009e70906060527i424cd3d9h525e8f87ec165...@mail.gmail.com:
Hi

I have few days to buy a computer for Monte-carlo Go program.
There is not enough money for a multi processor, so I have to decide between
- core i7 2.66 GHz
- some core2 quad
both subjected to over-clocking.

Have you observed that Monte-Carlo Go program is faster on core i7
than on core2 ?

Lukasz
PS
Or have you found some cheap solutions for shared memory dual processor?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
 --
 g...@nue.ci.i.u-tokyo.ac.jp (Kato)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Re: Core i7 performance in computer-go

2009-06-07 Thread Łukasz Lew
2009/6/7 Hideki Kato hideki_ka...@ybb.ne.jp:
 Łukasz, is the program multi-threaded?

Is is single threaded and 32-bit.


 Corei7 920 runs about 7% slower than core2 at the same clock.
 Possibly due to the optimized code for core2?

That is my belief.

I will reconsider buying i7.
Thank you for your benchmarks.

Lukasz


 Experimental results follow.

 On a 3 GHz (333 x 9) core2 Q6600:
 20 playouts in 1.49209 seconds
 134.04 kpps
 44.6798 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins),

 Average of the middle 10 of 12 runs is 44.79506 kpps/GHz.
 Raw data: 44.6798, 44.7951, 44.8276, 44.8207, 44.8398, 44.6887,
 44.8317, 44.8491, 44.782, 44.7216, 44.7983, 44.8451

 On a 3.6 GHz (180 x 20) corei7 920:
 20 playouts in 1.34808 seconds
 148.359 kpps
 41.2643 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins),
 Average of the middle 10 of 12 runs is 41.57643 kpps/GHz.
 Raw data: 41.2643, 41.9025, 41.3732, 41.5582, 41.1666, 41.4887,
 41.7724, 41.9751, 41.6362, 41.787, 41.269, 41.7128

 On a 3 GHz (150 x 20) corei7 920:
 20 playouts in 1.6001 seconds
 124.992 kpps
 40.1661 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins),
 Average of the middle 10 of 12 runs is 41.79165 kpps/GHz.
 Raw data: 40.1661, 41.8626, 41.8366, 41.687, 41.7099, 41.9556,
 41.3053, 41.9335, 41.8255, 41.8838, 42.077, 41.9167

 With hyper threading on (3 GHz 920):
 20 playouts in 1.5881 seconds
 125.937 kpps
 41.9898 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins),
 Average of the middle 10 of 12 runs is 41.82533 kpps/GHz.
 Raw data: 41.9898, 42.0318, 42.0503, 41.947, 40.6079, 41.7033,
 42.0283, 41.8386, 41.5187, 41.8013, 41.9114, 41.4831

 Hideki

 Łukasz Lew: c55009e70906070309q4d6224e1s509c2d858ff7e...@mail.gmail.com:
2009/6/6 Hideki Kato hideki_ka...@ybb.ne.jp:
 Hi Lukasz,

 I have five core2 and one i7 computers running at home.  I prefer i7,
 though don't have exact measure.

 The most important difference is the memory interface, ie, core2
 uses a obsolete common bus (FSB) while i7 uses p2p connection with
 an internal (on chip) memory controller.  Also, core2 uses DDR2
 (obsolete) and i7 uses DDR3 memory modules.

I know the technical differences. I just wonder do they matter in
practice of computer-go



 On overclocking, i7 performs better.  i7 920 (cheapest model) runs at
 3.6 GHz (C0 stepping; recent D0 is said at 4 GHz) while core2 Q9550
 (middle range model) runs at 3.2 GHz, with a rather silent air
 cooling.

thanks.


 If you have a benchmark program please send me.  Ubuntu Linux or
 WIndows XP is fine.


http://www.mimuw.edu.pl/~lew/engine.gz
please run with:
./engine --seed 123 -b

FYI it tests only the processor, not the memory and is optimized for core2.

 Ah, I don't prefer two sockets SMP computers since we will have hexa
 and octa core chips soon (next year? I don't remember).

I agree.


 Hideki

 Łukasz Lew: c55009e70906060527i424cd3d9h525e8f87ec165...@mail.gmail.com:
Hi

I have few days to buy a computer for Monte-carlo Go program.
There is not enough money for a multi processor, so I have to decide between
- core i7 2.66 GHz
- some core2 quad
both subjected to over-clocking.

Have you observed that Monte-Carlo Go program is faster on core i7
than on core2 ?

Lukasz
PS
Or have you found some cheap solutions for shared memory dual processor?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
 --
 g...@nue.ci.i.u-tokyo.ac.jp (Kato)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
 --
 g...@nue.ci.i.u-tokyo.ac.jp (Kato)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] UCT tree pruning

2009-06-06 Thread Łukasz Lew
Nice to hear that :)

2009/6/5 Michael Williams michaelwilliam...@gmail.com:
 Łukasz Lew wrote:

 On Wed, Jun 3, 2009 at 00:56, Michael Williams
 michaelwilliam...@gmail.com wrote:

 Two things:  Firstly, I'm storing (only in RAM) the precalculated Winrate
 and InvSqrtVisits and keeping them updated.
 So my UCT formula went from

       Wins / Visits + sqrt(lnParentVisits / Visits)

 to

       WinRate + sqrtLnParentVisits * InvSqrtVisits;

 This has a memory cost, but I don't care so much about RAM since I can
 send
 the nodes to disk.

 And the second thing is to store in the parent node a reference to what
 is
 likely the UCT-best child node.  If the parent has been visited
 100*boardspaces times, I will go directly to the likely-best child with
 probability 2047/2048.  Anytime a proper UCT loop occurs, the likely-best
 reference is updated (about 90% of the time there is no change, so I
 think
 it's safe).

 This is quite similar to epsilon trick described here:
 http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf

 in short when you calculate best UCT child you visit it
 max(best.visit_count * epsilon, 1) times
 with epsilon = 0.05 for instance
 It works well both for new and old nodes, but you have to keep the
 counter of visits.
 The soft way would be to recalculate best child with probability
 min(1, 1/(best.visit_count*epsilon)).

 Both variants of ET can give you some guarantees about the way the
 tree is explored.

 Łukasz


 I switched to this method.  Thanks, Lukasz.

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Core i7 performance in computer-go

2009-06-06 Thread Łukasz Lew
Hi

I have few days to buy a computer for Monte-carlo Go program.
There is not enough money for a multi processor, so I have to decide between
- core i7 2.66 GHz
- some core2 quad
both subjected to over-clocking.

Have you observed that Monte-Carlo Go program is faster on core i7
than on core2 ?

Lukasz
PS
Or have you found some cheap solutions for shared memory dual processor?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] UCT tree pruning

2009-06-02 Thread Łukasz Lew
On Wed, Jun 3, 2009 at 00:56, Michael Williams
michaelwilliam...@gmail.com wrote:
 Two things:  Firstly, I'm storing (only in RAM) the precalculated Winrate
 and InvSqrtVisits and keeping them updated.
 So my UCT formula went from

        Wins / Visits + sqrt(lnParentVisits / Visits)

 to

        WinRate + sqrtLnParentVisits * InvSqrtVisits;

 This has a memory cost, but I don't care so much about RAM since I can send
 the nodes to disk.

 And the second thing is to store in the parent node a reference to what is
 likely the UCT-best child node.  If the parent has been visited
 100*boardspaces times, I will go directly to the likely-best child with
 probability 2047/2048.  Anytime a proper UCT loop occurs, the likely-best
 reference is updated (about 90% of the time there is no change, so I think
 it's safe).

This is quite similar to epsilon trick described here:
http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf

in short when you calculate best UCT child you visit it
max(best.visit_count * epsilon, 1) times
with epsilon = 0.05 for instance
It works well both for new and old nodes, but you have to keep the
counter of visits.
The soft way would be to recalculate best child with probability
min(1, 1/(best.visit_count*epsilon)).

Both variants of ET can give you some guarantees about the way the
tree is explored.

Łukasz



 Jason House wrote:

 That sounds like a good optimization. What did you do?

 Sent from my iPhone

 On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com
 wrote:

 Update:  After concentrating on tightening the UCT loop, I've optimized
 myself back into needing the SDD  :/

 But now I should be able to get to 20B nodes in just one day.

 (still only doing 7x7 Go)


 Michael Williams wrote:

 Yes, when memory is full, I save and free all leaf nodes (which is the
 vast majority).  Nodes are loaded as needed.
 Don Dailey wrote:


 On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams
 michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote:

   I've optimized my disk access to the point where I'm mostly CPU
   limited now, even when using a standard hard disk instead of an SSD.
    I can now create trees of up to about 30 billion nodes, which would
   take about a week.  The simulation rate is continuously going down
   because so much time is spent in UCT loops in the huge tree.


 That's impressive.   Are you doing things which move parts of the tree
 onto the disk and back when needed?     I'm curious about the details!

 - Don






   Don Dailey wrote:



       On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch
       mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch
 wrote:


            Well, I'll take that over crashing with an out-of-memory
       error. :)

          Still, pruning seems better to me and has the same effect. ;p


       But is it better?   I think it's not so obvious without thorough
       testing.

       Pruning throw away information that is lost forever and may need
       to be recalculated.   Requiring more simulations does not throw
       out results, but results in some inefficiencies.   So it's not
       clear to me which is better - it may even be that it depends on
       how much you push it.   I am just guessing but I would guess
       that pruning is better in the short term, worse in the longer
       term.   Imagine a search at a corespondence level, where the
       computer thinks for 24 hours.   Which method is best there?
    Could you use hard disk or SSD?   Using some kind of caching
       system,  where you relegate the oldest unvisited nodes to the
       hard dirve.   It may be that nodes you might normally prune are
       unlikely to get used again but if they do you still have the
       data.    This is no good unless you can guarantee that the disk
       is used very infrequently - but with SSD it may be more
 practical.


       - Don




                  --
          Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000
       Flatrate und
          Telefonanschluss nur 17,95 Euro/mtl.!*
       http://portal.gmx.net/de/go/dsl02
          ___
          computer-go mailing list
          computer...@computer-go.org
       mailto:computer-go@computer-go.org
       mailto:computer-go@computer-go.org
       mailto:computer-go@computer-go.org

          http://www.computer-go.org/mailman/listinfo/computer-go/




 


       ___
       computer-go mailing list
       computer-go@computer-go.org mailto:computer-go@computer-go.org
       http://www.computer-go.org/mailman/listinfo/computer-go/


   ___
   computer-go mailing list
   computer-go@computer-go.org mailto:computer-go@computer-go.org
   http://www.computer-go.org/mailman/listinfo/computer-go/




 

[computer-go] Re: Report on Fuego in Pamplona

2009-05-26 Thread Łukasz Lew
Thanks.

Lukasz

On Tue, May 26, 2009 at 22:15, Martin Mueller mmuel...@cs.ualberta.ca wrote:
 Hello all,

 I have uploaded a technical report, mainly with commented Fuego games from
 Pamplona. Lukasz, it has the config settings in an appendix.

 Fuego at the Computer Olympiad in Pamplona 2009: a Tournament Report
 http://www.cs.ualberta.ca/research/techreports/2009/TR09-09.php

 As always, all feedback is welcome, and there can be a revised version if
 needed.

        Martin

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Merging libego and fuego

2009-05-14 Thread Łukasz Lew
Libego has similar goal as fuego - to become universal platform for
experimenting with MC GO.
For a few days there has been talk about merging libego (mostly fast
board implementation) with fuego.
But I can't do it on my own.

Is there anybody interested in helping?
Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Congratulations to Fuego, the new champion!

2009-05-13 Thread Łukasz Lew
It beat mogo in playoff.
Gratulations!

As fuego is opensource, you might be interested in it's playout policy:
http://www.cs.ualberta.ca/~games/go/fuego/fuego-doc/gouct-doc/GoUctPlayoutPolicy_8h-source.html#l00489

Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Implications of a CPU vs Memory trend on MCTS

2009-05-12 Thread Łukasz Lew
Just a reminder that epsilon trick (invented by Jakub Pawlewicz) can
be used to avoid excessive memory usage (reuse memory) without
significant performance loss. It has been tested for proof number
search, but there is no reason for it to behave differently in MCTS.

Lukasz Lew

On Tue, May 12, 2009 at 19:35, Michael Williams
michaelwilliam...@gmail.com wrote:
 Those numbers are the average after the tree has grown to 1B nodes.  I'm
 sure the cache hates me.  Each tree traversal will likely make several reads
 from random locations in a 50 GB file.


 Don Dailey wrote:

 So you are saying that use disk memory for this?
 This could be pretty deceiving if most of your reads and writes are
 cached.    What happens when your tree gets much bigger than available
 memory?

 - Don



 On Tue, May 12, 2009 at 1:18 PM, Michael Williams
 michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote:

    In my system, I can retrieve the children of any node at a rate of
    about 100k nodes/sec.

    And I can save nodes at a rate of over 1M nodes/sec (this is much
    faster because in my implementation, the operation is sequential on
    disk).

    Those numbers are from 6x6 testing.


    Don Dailey wrote:

        This is probably a good solution.   I don't believe the memory
        has to be very fast at all because even with light playouts you
        are doing a LOT of computation between memory accesses.
  All of this must be tested of course.     In fact I was
        considering if disk memory could not be utilized as a kind of
        cache.   The secret would be to store complete trees in disk
        memory, trees that are not likely to be utilized but can be
        utilized in a pinch.   The tree store and retrieved must
        outweigh by a large factor the amount of time spent creating the
        tree in the first place in order for this to pay off.
        My guess is that this is impractical, but it's fun to think
        about how it might be done.   I'm not sure how to do it without
        having a caching nightmare.


        - Don



        On Tue, May 12, 2009 at 12:41 PM, Michael Williams
        michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com wrote:

           Don Dailey wrote:

               On Tue, May 12, 2009 at 12:16 PM, Michael Williams
               michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com
               mailto:michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com
               mailto:michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com

               mailto:michaelwilliam...@gmail.com
        mailto:michaelwilliam...@gmail.com wrote:

                  I have a trick  ;)

                  I am currently creating MCTS trees of over a billion
        nodes on
               my 4GB
                  machine.


               Ok,  I'll bite.    What is your solution?


           I use an SSD.  There are many details, of course.  But it's
        still in
           the works and I'm still making lots of changes and
        adjustments.  I
           seem to be able to solve (there are lots of definitions)
        6x6 Go in
           that when I use a komi of 3.5, it is unable to find a winning
        line
           for white and when I use 4.5, it is unable to find a winning
 line
           for black.


           ___
           computer-go mailing list
           computer-go@computer-go.org
        mailto:computer-go@computer-go.org
        mailto:computer-go@computer-go.org
        mailto:computer-go@computer-go.org

           http://www.computer-go.org/mailman/listinfo/computer-go/




  


        ___
        computer-go mailing list
        computer...@computer-go.org mailto:computer-go@computer-go.org
        http://www.computer-go.org/mailman/listinfo/computer-go/


    ___
    computer-go mailing list
    computer...@computer-go.org mailto:computer-go@computer-go.org
    http://www.computer-go.org/mailman/listinfo/computer-go/



 

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] CGOS: How to access old sgf games?

2009-05-05 Thread Łukasz Lew
2009/5/5 elife elife2...@gmail.com:
 For particular game, you can access it from url like
 http://cgos.boardspace.net/9x9/SGF/2009/05/05/752908.sgf

But how can I know what is the id of the game of a particular pair of engines?



 On Tue, May 5, 2009 at 8:42 PM, Łukasz Lew lukasz@gmail.com wrote:
 But not as old as January archive, but for example from yesterday.
 Can I get games of a cgos login?

 Lukasz
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] CGOS: How to access old sgf games?

2009-05-05 Thread Łukasz Lew
On Tue, May 5, 2009 at 14:56, Jason House jason.james.ho...@gmail.com wrote:
 There's no great way to do this. I guess one could sequentially download
 files and examine them for the player to play.

 I've always wanted to be able to click on a crosstable entry and get a more
 detailed summary of performance along with links to the last 10(?)  games
 between the pair. I've been too lazy to add the functionality myself.

Indeed.
The easiest thing for Don (that would be already useful) would be to
give access to links like this one:

http://cgos.boardspace.net/9x9/SGF/2009/05/05/




 Sent from my iPhone

 On May 5, 2009, at 8:42 AM, Łukasz Lew lukasz@gmail.com wrote:

 But not as old as January archive, but for example from yesterday.
 Can I get games of a cgos login?

 Lukasz
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] CGOS: How to access old sgf games?

2009-05-05 Thread Łukasz Lew
IT does not have to be complicated/perfect.
Static links might be enough.
Just automate compressing games of each pair of engines separately and
provide links to that.
(or better: link to a readable directory where the archives reside)

If you want to work on anything more complicated, I would vote for
better support of program versioning. :)

Lukasz

2009/5/5 Don Dailey dailey@gmail.com:
 I'm seriously considering to overhaul the archive system with CGI scripts to
 make it easy to grab anything by date range and player name.

 But it's not there now.

 - Don


 On Tue, May 5, 2009 at 8:42 AM, Łukasz Lew lukasz@gmail.com wrote:

 But not as old as January archive, but for example from yesterday.
 Can I get games of a cgos login?

 Lukasz
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Value of capture (atari?) heuristic.

2009-04-27 Thread Łukasz Lew
Hi,

Have any one of you tried uct + capture heuristic?
Is it stronger? How much?

Any one tried a variant (let's say local capture heuristic) where only
chains put into atari by last move are considered?

Any one tried pseudo-atari capture heuristic? I.e. only chains with
exactly one pseudoliberty are considered?

Regards,
Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Value of capture (atari?) heuristic.

2009-04-27 Thread Łukasz Lew
2009/4/28 Mark Boon tesujisoftw...@gmail.com:
 On Sun, Apr 26, 2009 at 11:54 PM, Łukasz Lew lukasz@gmail.com wrote:
 Hi,

 Have any one of you tried uct + capture heuristic?
 Is it stronger? How much?


 From memory I'd say it was winning about 80% against plain UCT. But
 only capture if it can escape (which means it can make three
 liberties.)

Thanks. Any additional rules in your experiment? For instance no
capturing stones that can't escape by this definition.
Do you know what happens if there's no such rule (always capture) ?

Lukasz


    Mark
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-24 Thread Łukasz Lew
On Fri, Apr 24, 2009 at 01:52, Łukasz Lew lukasz@gmail.com wrote:
 I get
 g++-4.1  35 kpps/GHz
 g++-4.2  45 kpps/GHz
 g++-4.3  40 kpps/GHz
 I'm happy it's quite consistent on core2

 I'm curious about 4.4 as well.

g++-4.4 45 kpps/GHz
package gcc-snapshot on ubuntu

$ /usr/lib/gcc-snapshot/bin/g++ --version
g++ (Ubuntu 20081024-0ubuntu1) 4.4.0 20081024 (experimental) [trunk
revision 141342]

so quite old.

Lukasz


 Lukasz

 PS

 On Fri, Apr 24, 2009 at 01:29, Adrian Grajdeanu adria...@cox.net wrote:
 I have two benchmarks:

 On an: Intel(R) Core(TM)2 CPU         T7200  @ 2.00GHz stepping 06
 g++ --version
 g++ (GCC) 4.1.2 20070925 (Red Hat 4.1.2-33)
 I had to modify SConstruct to refer to the default g++, not g++.4.2 and
 had to remove -march=native

 = Benchmarking, please wait ...

 = 20 playouts in 2.72759 seconds
 73.3249 kpps
 36.5657 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)

 = 20 playouts in 2.73858 seconds
 73.0304 kpps
 36.4108 kpps/GHz (clock independent)
 104924/94746 (black wins / white wins)

 = 20 playouts in 2.72858 seconds
 73.2981 kpps
 36.5291 kpps/GHz (clock independent)
 105097/94582 (black wins / white wins)

 = 20 playouts in 2.76258 seconds
 72.3961 kpps
 36.1141 kpps/GHz (clock independent)
 105139/94547 (black wins / white wins)

 = 20 playouts in 2.74358 seconds
 72.8974 kpps
 36.3124 kpps/GHz (clock independent)
 104896/94794 (black wins / white wins)

 = Try 'help'



 on an: Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz stepping 0a
 g++ --version
 g++ (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8)
 (with -march=native flag)
 = Benchmarking, please wait ...

 = 20 playouts in 1.65575 seconds
 120.791 kpps
 40.2566 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)

 = 20 playouts in 1.65275 seconds
 121.011 kpps
 40.3069 kpps/GHz (clock independent)
 104924/94746 (black wins / white wins)

 = 20 playouts in 1.65375 seconds
 120.937 kpps
 40.2789 kpps/GHz (clock independent)
 105097/94582 (black wins / white wins)

 = 20 playouts in 1.65475 seconds
 120.864 kpps
 40.2917 kpps/GHz (clock independent)
 105139/94547 (black wins / white wins)

 = 20 playouts in 1.65175 seconds
 121.084 kpps
 40.3084 kpps/GHz (clock independent)
 104896/94794 (black wins / white wins)

 = Try 'help'


 I'd be curious g++ 4.4 what gives?

 Cheers,
 Adrian

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-24 Thread Łukasz Lew
You have to take into account that there is time needed to load base
position and score the game after playout.
I remember that in my old tests it was around 180 cc per move.
(libego got a little bit faster since then)

Lukasz

On Fri, Apr 24, 2009 at 18:56, Jason House jason.james.ho...@gmail.com wrote:

 Of course, I now realize what I missed after sending it. Playout vs.
 Playout move... At a little over 100 moves per playout, our numbers
 agree

 Sent from my iPhone

 On Apr 24, 2009, at 12:54 PM, Jason House
 jason.james.ho...@gmail.com wrote:

 My math seems to be way different
 1e9 / 45000= 22,222 cycles per playout

 On Apr 24, 2009, at 12:22 PM, Michael Williams michaelwilliam...@gmail.com
  wrote:

 According to my math, that comes out to around 205 cycles per
 playout move.  Pretty damn good, I'd say.


 Łukasz Lew wrote:
 On Fri, Apr 24, 2009 at 01:52, Łukasz Lew lukasz@gmail.com
  wrote:
 I get
 g++-4.1  35 kpps/GHz
 g++-4.2  45 kpps/GHz
 g++-4.3  40 kpps/GHz
 I'm happy it's quite consistent on core2

 I'm curious about 4.4 as well.
 g++-4.4 45 kpps/GHz
 package gcc-snapshot on ubuntu
 $ /usr/lib/gcc-snapshot/bin/g++ --version
 g++ (Ubuntu 20081024-0ubuntu1) 4.4.0 20081024 (experimental) [trunk
 revision 141342]
 so quite old.
 Lukasz
 Lukasz

 PS

 On Fri, Apr 24, 2009 at 01:29, Adrian Grajdeanu
 adria...@cox.net wrote:
 I have two benchmarks:

 On an: Intel(R) Core(TM)2 CPU         T7200  @ 2.00GHz stepping 06
 g++ --version
 g++ (GCC) 4.1.2 20070925 (Red Hat 4.1.2-33)
 I had to modify SConstruct to refer to the default g++, not g++.
 4.2 and
 had to remove -march=native

 = Benchmarking, please wait ...

 = 20 playouts in 2.72759 seconds
 73.3249 kpps
 36.5657 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)

 = 20 playouts in 2.73858 seconds
 73.0304 kpps
 36.4108 kpps/GHz (clock independent)
 104924/94746 (black wins / white wins)

 = 20 playouts in 2.72858 seconds
 73.2981 kpps
 36.5291 kpps/GHz (clock independent)
 105097/94582 (black wins / white wins)

 = 20 playouts in 2.76258 seconds
 72.3961 kpps
 36.1141 kpps/GHz (clock independent)
 105139/94547 (black wins / white wins)

 = 20 playouts in 2.74358 seconds
 72.8974 kpps
 36.3124 kpps/GHz (clock independent)
 104896/94794 (black wins / white wins)

 = Try 'help'



 on an: Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz stepping 0a
 g++ --version
 g++ (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8)
 (with -march=native flag)
 = Benchmarking, please wait ...

 = 20 playouts in 1.65575 seconds
 120.791 kpps
 40.2566 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)

 = 20 playouts in 1.65275 seconds
 121.011 kpps
 40.3069 kpps/GHz (clock independent)
 104924/94746 (black wins / white wins)

 = 20 playouts in 1.65375 seconds
 120.937 kpps
 40.2789 kpps/GHz (clock independent)
 105097/94582 (black wins / white wins)

 = 20 playouts in 1.65475 seconds
 120.864 kpps
 40.2917 kpps/GHz (clock independent)
 105139/94547 (black wins / white wins)

 = 20 playouts in 1.65175 seconds
 121.084 kpps
 40.3084 kpps/GHz (clock independent)
 104896/94794 (black wins / white wins)

 = Try 'help'


 I'd be curious g++ 4.4 what gives?

 Cheers,
 Adrian

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 --~--~-~--~~~---~--~~
 You received this message because you are subscribed to the Google Groups 
 libego-devel group.
 To post to this group, send email to libego-de...@googlegroups.com
 To unsubscribe from this group, send email to 
 libego-devel+unsubscr...@googlegroups.com
 For more options, visit this group at 
 http://groups.google.com/group/libego-devel?hl=en
 -~--~~~~--~~--~--~---


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-23 Thread Łukasz Lew
On Thu, Apr 23, 2009 at 01:25, elife elife2...@gmail.com wrote:
 On my Intel(R) Core(TM)2 Duo CPU     T7200  @ 2.00GHz, using linux and
 the exact compiler libego was tuned for, I get 70 kpps/GHz.

 = 20 playouts in 2.85618 seconds
 70.0236 kpps
 -154.124 kpps/GHz (clock independent)


I found this kind of garbage associated with 64 bit systems.
It's probably because of my poor assembly, but I thought I fixed it recently.
Can you check newest version?

http://github.com/lukaszlew/libego/zipball/master

Lukasz

 104896/94794 (black wins / white wins)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Libego benchmarking

2009-04-23 Thread Łukasz Lew
This is because there is no getrusage function on windows, so I just
return (and divide) by 0.
I will try to fix it in next week.

Lukasz

On Thu, Apr 23, 2009 at 07:28, Petri Pitkanen
petri.t.pitka...@gmail.com wrote:
 Because your time measurement has gone wrong. You get 0 seconds in
 time hence kpssa in infinity.

 Petri

 2009/4/23 Michael Williams michaelwilliam...@gmail.com:
 Here is my full set of numbers.  I wonder why the known kpps/GHz but unknown
 kpps.



 = Benchmarking, please wait ...

 = 20 playouts in 0 seconds
 1.#INF kpps
 40.0245 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)
 --
 Petri Pitkänen
 e-mail: petri.t.pitka...@gmail.com
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-23 Thread Łukasz Lew
I get
g++-4.1  35 kpps/GHz
g++-4.2  45 kpps/GHz
g++-4.3  40 kpps/GHz
I'm happy it's quite consistent on core2

I'm curious about 4.4 as well.

Lukasz

PS

On Fri, Apr 24, 2009 at 01:29, Adrian Grajdeanu adria...@cox.net wrote:
 I have two benchmarks:

 On an: Intel(R) Core(TM)2 CPU         T7200  @ 2.00GHz stepping 06
 g++ --version
 g++ (GCC) 4.1.2 20070925 (Red Hat 4.1.2-33)
 I had to modify SConstruct to refer to the default g++, not g++.4.2 and
 had to remove -march=native

 = Benchmarking, please wait ...

 = 20 playouts in 2.72759 seconds
 73.3249 kpps
 36.5657 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)

 = 20 playouts in 2.73858 seconds
 73.0304 kpps
 36.4108 kpps/GHz (clock independent)
 104924/94746 (black wins / white wins)

 = 20 playouts in 2.72858 seconds
 73.2981 kpps
 36.5291 kpps/GHz (clock independent)
 105097/94582 (black wins / white wins)

 = 20 playouts in 2.76258 seconds
 72.3961 kpps
 36.1141 kpps/GHz (clock independent)
 105139/94547 (black wins / white wins)

 = 20 playouts in 2.74358 seconds
 72.8974 kpps
 36.3124 kpps/GHz (clock independent)
 104896/94794 (black wins / white wins)

 = Try 'help'



 on an: Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz stepping 0a
 g++ --version
 g++ (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8)
 (with -march=native flag)
 = Benchmarking, please wait ...

 = 20 playouts in 1.65575 seconds
 120.791 kpps
 40.2566 kpps/GHz (clock independent)
 105316/94359 (black wins / white wins)

 = 20 playouts in 1.65275 seconds
 121.011 kpps
 40.3069 kpps/GHz (clock independent)
 104924/94746 (black wins / white wins)

 = 20 playouts in 1.65375 seconds
 120.937 kpps
 40.2789 kpps/GHz (clock independent)
 105097/94582 (black wins / white wins)

 = 20 playouts in 1.65475 seconds
 120.864 kpps
 40.2917 kpps/GHz (clock independent)
 105139/94547 (black wins / white wins)

 = 20 playouts in 1.65175 seconds
 121.084 kpps
 40.3084 kpps/GHz (clock independent)
 104896/94794 (black wins / white wins)

 = Try 'help'


 I'd be curious g++ 4.4 what gives?

 Cheers,
 Adrian

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-22 Thread Łukasz Lew
Please download newest version, I made some ifdefWIN 32 ... to aid
mingw porting.
http://github.com/lukaszlew/libego/zipball/master

Under linux I can cross compile to windows binary with a following command
$ i586-mingw32msvc-g++ -o engine.exe ego/ego.cpp example/main.cpp -O3
-march=native -Iego -fomit-frame-pointer -ffast-math
-frename-registers

It might just work :)

FYI
$ i586-mingw32msvc-g++ --version
i586-mingw32msvc-g++ (GCC) 4.2.1-sjlj (mingw32-2)

And the performance I get is around 32 kpps/GHz

Lukasz

2009/4/22 Michael Williams michaelwilliam...@gmail.com:
 Ok, I have Mingw installed now.  That sounds like the way to go.  But I
 still don't know how to compile it  :/

 According to the SConstruct file, I should be doing something like this to
 build, but it complains:

 C:\Libego g++ /Fobuild\ego\dbg\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3 -Wall
 -Wextra -Wswitch-enum -fno-inline /nologo /Iego

 g++: /Fobuild\ego\dbg\ego.obj: No such file or directory
 g++: /c: No such file or directory
 g++: /nologo: No such file or directory
 g++: /Iego: No such file or directory
 In file included from ego\ego.h:27,
                 from ego\ego.cpp:47:
 ego\gtp.h:73: warning: `class Gtp' has virtual functions but non-virtual
 destructor
 In file included from ego\ego.cpp:54:
 ego\player.cpp: In constructor `Player::Player()':
 ego\player.cpp:27: warning: converting of negative value `-0x1' to
 `uint'
 In file included from ego\ego.cpp:55:
 ego\color.cpp: In constructor `Color::Color()':
 ego\color.cpp:27: warning: converting of negative value `-0x1' to
 `uint'


 I also tried the build command for the optimized version:


 C:\Libego g++ /Fobuild\ego\opt\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3 -Wall
 -Wextra -Wswitch-enum -O3 -march=native -fomit-frame-pointer -ffast-math
 -frename-registers /nologo /Iego

 g++: /Fobuild\ego\opt\ego.obj: No such file or directory
 g++: /c: No such file or directory
 g++: /nologo: No such file or directory
 g++: /Iego: No such file or directory
 ego\ego.cpp:1: error: bad value (native) for -march= switch
 ego\ego.cpp:1: error: bad value (native) for -mtune= switch


 Sorry for my ignorance.



 Łukasz Lew wrote:

 2009/4/21 Łukasz Lew lukasz@gmail.com:

 mingw rules!
 I compiled libego with it and got a decent 32kpps / GHz ( native g++
 was 44kpps / GHz)

 I used wine to run resulting exe on linux:)

 Lukasz

 2009/4/21 Don Dailey dailey@gmail.com:

 I use mingw to produce cros platform executables.   I can build
 executables
 for linux, win32 and win64, which for my chess program is a must since
 it's
 64 bit.

 - Don


 On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com
 wrote:

 On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:

 I forgot about cygwin indeed. It is a good idea.
 But can you ran the binary on a system without cygwin?

 We can run the binary on a system without cygwin if we provide
 cygwin1.dll.

 That is great.
 Another good idea is mingw.

 BTW
 I would like to recommend stackoverflow.com for programming questions.
 I asked this question there


 http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
 and got few good answers within a minute.

 Lukasz

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-21 Thread Łukasz Lew
On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:
 I forgot about cygwin indeed. It is a good idea.
 But can you ran the binary on a system without cygwin?

 We can run the binary on a system without cygwin if we provide cygwin1.dll.

That is great.
Another good idea is mingw.

BTW
I would like to recommend stackoverflow.com for programming questions.
I asked this question there
http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
and got few good answers within a minute.

Lukasz

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] (no subject)

2009-04-21 Thread Łukasz Lew
I like the idea very much.
But the coding effort is mostly in the GUI so it depends whether
gogui's (or other GUIS's) author will like the idea.

It has great commercial/popularity potential.
But it is not so important for research.

Lukasz

On Tue, Apr 21, 2009 at 07:35, Ingo Althöfer 3-hirn-ver...@gmx.de wrote:
 Hello,

 during the last weekend I have tried (for the
 first time) to use commercial go programs
 to analyse some games played between human
 players (on KGS).
 The idea was to use the bots for blunderchecks.
 So, I was looking for positions where the
 evaluation (in win  percentages) jumped or
 dropped between consecutive moves.


 *** Concrete Example ***

 Amongst others I looked at a game between
 bwilcox[3d] and harleqin [2d], played on April 20,
 2009, starting time 5:31 [CEST]. You can download
 the sgf for instance from the KGS archive at
 http://www.gokgs.com/gameArchives.jsp?user=Harleqin

 (By the way, bwilcox might be Bruce Wilcox, one of
 the veterans in computer go.)


 Both programs in my analysis claimed that
 77.f13 was a big error:
 * In Leela the score dropped from 50.5 to 41.4 .
 * In ManyFaces the score dropped from 50.0 to 45.8 .

 Instead of 77.f13, both programs proposed 77.d14,
 with the possible continuation 78.e14 79.d13 .

 I discussed these findings with Harleqin, and
 he agreed that 77.f13 was a move that brought him
 into problems.


 *** General Wish ***

 Unfortunately current, (commercial) go programs
 (including Leela and ManyFaces) do not have a user
 interface that allows for COMFORTABLE analysis of
 games. The user has to click lots of buttons when
 jumping back and forth in some sgf.

 My wish is to have something similar to that, what has become
 standard in computer chess programs in the mid 1990's:
 * on the left half of the screen the diagram of the board
 * on the right half a list (not only sgf, but also with
  move numbers included)
 * the program is computing in analysis (infinite) mode
 * when the user clicks (by mouse) on any move in the move list
  then the program jumps immediately to this position and
  starts analysing (of course this position is shown in the diagram)
 * of course the screen should all the time show (in fat font)
  what the value of komi in the game under investigation is.

 * Another big wish: the programs should allow for some k-best mode
 where not only the best but the k best moves are computed (k being
 some integer specified by the user).

 Ingo.
 --
 Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss 
 für nur 17,95 Euro/mtl.!* 
 http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-21 Thread Łukasz Lew
On Tue, Apr 21, 2009 at 04:59, Jason House jason.james.ho...@gmail.com wrote:
 I always recommend cygwin. I'm a linux guy and can't live without all my
 little tools and simple package installation. You should be able to get the
 exact gcc libego was optimized for that way.

I forgot about cygwin indeed. It is a good idea.
But can you ran the binary on a system without cygwin?


 I use the digital mars d compiler and it's blazingly fast. All my d files
 can compile and link faster than gcc compiles one of libego's c++ files. I'm
 not knocking libego, just giving a relevent reference point. I'm using
 libego under the hood for playouts.

the reason of slow  libego compilation is conntected to speed of playouts.
It has everything in one file optimized with O3.
After compilation there are almost no functions calls.

Lukasz


 Sent from my iPhone

 On Apr 20, 2009, at 9:18 PM, Michael Williams michaelwilliam...@gmail.com
 wrote:

 I got Libego compiled to a Windows DLL using Visual Studio and was able to
 call it, but I was only getting around 5k pps on my Core2.  So I wanted to
 try another compiler.  Has anyone used the Digital Mars C++ compiler?  Or is
 there another compiler I should try?
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-21 Thread Łukasz Lew
mingw rules!
I compiled libego with it and got a decent 32kpps / GHz ( native g++
was 44kpps / GHz)

Lukasz

2009/4/21 Don Dailey dailey@gmail.com:
 I use mingw to produce cros platform executables.   I can build executables
 for linux, win32 and win64, which for my chess program is a must since it's
 64 bit.

 - Don


 On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com wrote:

 On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:
  I forgot about cygwin indeed. It is a good idea.
  But can you ran the binary on a system without cygwin?
 
  We can run the binary on a system without cygwin if we provide
  cygwin1.dll.

 That is great.
 Another good idea is mingw.

 BTW
 I would like to recommend stackoverflow.com for programming questions.
 I asked this question there

 http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
 and got few good answers within a minute.

 Lukasz

  ___
  computer-go mailing list
  computer-go@computer-go.org
  http://www.computer-go.org/mailman/listinfo/computer-go/
 
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-21 Thread Łukasz Lew
2009/4/21 Łukasz Lew lukasz@gmail.com:
 mingw rules!
 I compiled libego with it and got a decent 32kpps / GHz ( native g++
 was 44kpps / GHz)

I used wine to run resulting exe on linux:)


 Lukasz

 2009/4/21 Don Dailey dailey@gmail.com:
 I use mingw to produce cros platform executables.   I can build executables
 for linux, win32 and win64, which for my chess program is a must since it's
 64 bit.

 - Don


 On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com wrote:

 On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:
  I forgot about cygwin indeed. It is a good idea.
  But can you ran the binary on a system without cygwin?
 
  We can run the binary on a system without cygwin if we provide
  cygwin1.dll.

 That is great.
 Another good idea is mingw.

 BTW
 I would like to recommend stackoverflow.com for programming questions.
 I asked this question there

 http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
 and got few good answers within a minute.

 Lukasz

  ___
  computer-go mailing list
  computer-go@computer-go.org
  http://www.computer-go.org/mailman/listinfo/computer-go/
 
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-21 Thread Łukasz Lew
Funny story:
I have worse performance with g++-4.3 (20% as well)
I probably overoptimized for g++-4.2 or something :)

FYI g++4.4 is about to be released. it is already in experimental
debian repository

Lukasz

2009/4/21 Adrian Grajdeanu adria...@cox.net:
 Just to add my 2c for the performance freaks. I've noticed that code
 generated by g++ 4.3.x was about 40-45% faster non-optimized when compared
 to previous versions of g++ (native linux platform). When optimizing code
 (-O3), 4.3 generated code that was 20% faster. This is probably the more
 relevant number for those that optimize their code anyway. Don't know about
 you, but I was impressed by 20% gain.

 If you already use g++ 4.3, pardon my interruption. But if you don't, you
 will be pleasantly surprised once you upgrade to it.

 Adrian


 Łukasz Lew wrote:

 mingw rules!
 I compiled libego with it and got a decent 32kpps / GHz ( native g++
 was 44kpps / GHz)

 Lukasz

 2009/4/21 Don Dailey dailey@gmail.com:

 I use mingw to produce cros platform executables.   I can build
 executables
 for linux, win32 and win64, which for my chess program is a must since
 it's
 64 bit.

 - Don


 On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com wrote:

 On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:

 I forgot about cygwin indeed. It is a good idea.
 But can you ran the binary on a system without cygwin?

 We can run the binary on a system without cygwin if we provide
 cygwin1.dll.

 That is great.
 Another good idea is mingw.

 BTW
 I would like to recommend stackoverflow.com for programming questions.
 I asked this question there


 http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
 and got few good answers within a minute.

 Lukasz

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Could be that nobody is playing?

2009-04-20 Thread Łukasz Lew
Rated: 1713 as of 2007-12-29 09:28:46
http://cgos.boardspace.net/9x9/cross/libEGO-v0.115-100k.html

I am running exactly the same binary file to check it recent rating.
ego-v0.115-100k

Lukasz

On Mon, Apr 20, 2009 at 20:16, Christoph Birk b...@ociw.edu wrote:
 On Mon, 20 Apr 2009, ?ukasz Lew wrote:

 Is there a rating drift? I remember that pure UCT no RAVE with 100k
 playouts got over 1700 elo.

 That seems a little high. My 50k-pure-UCT searcher is around
 1580 for a long time.

 Christoph

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Could be that nobody is playing?

2009-04-20 Thread Łukasz Lew
that is correct.

2009/4/20 Don Dailey dailey@gmail.com:
 That should be interesting.

 So we have

   1. ego-v0.115-100k

   2. libEGO-v0.115-100k

 Is that correct?   We can watch it's bayelo rating as well as it's
 incremental rating.

 - Don





 On Mon, Apr 20, 2009 at 3:13 PM, Łukasz Lew lukasz@gmail.com wrote:

 Rated: 1713 as of 2007-12-29 09:28:46
 http://cgos.boardspace.net/9x9/cross/libEGO-v0.115-100k.html

 I am running exactly the same binary file to check it recent rating.
 ego-v0.115-100k

 Lukasz

 On Mon, Apr 20, 2009 at 20:16, Christoph Birk b...@ociw.edu wrote:
  On Mon, 20 Apr 2009, ?ukasz Lew wrote:
 
  Is there a rating drift? I remember that pure UCT no RAVE with 100k
  playouts got over 1700 elo.
 
  That seems a little high. My 50k-pure-UCT searcher is around
  1580 for a long time.
 
  Christoph
 
  ___
  computer-go mailing list
  computer-go@computer-go.org
  http://www.computer-go.org/mailman/listinfo/computer-go/
 
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Could be that nobody is playing?

2009-04-20 Thread Łukasz Lew
Hardware might be not important for fixed number of playouts.
Can you give us logins?

2009/4/20 Don Dailey dailey@gmail.com:
 Jason,

 This means nothing - can you give us more details?   What did the error bars
 look like?   Which hardware were each run on?  etc.

 - Don


 2009/4/20 Jason House jason.james.ho...@gmail.com

 Earlier today, I looked up my identical 50k RAVE bots and found ratings of
 1827 (old) and 1468 (new).

 Sent from my iPhone
 On Apr 20, 2009, at 4:08 PM, Don Dailey dailey@gmail.com wrote:

 That should be interesting.

 So we have

   1. ego-v0.115-100k

   2. libEGO-v0.115-100k

 Is that correct?   We can watch it's bayelo rating as well as it's
 incremental rating.

 - Don





 On Mon, Apr 20, 2009 at 3:13 PM, Łukasz Lew lukasz@gmail.com wrote:

 Rated: 1713 as of 2007-12-29 09:28:46
 http://cgos.boardspace.net/9x9/cross/libEGO-v0.115-100k.html

 I am running exactly the same binary file to check it recent rating.
 ego-v0.115-100k

 Lukasz

 On Mon, Apr 20, 2009 at 20:16, Christoph Birk b...@ociw.edu wrote:
  On Mon, 20 Apr 2009, ?ukasz Lew wrote:
 
  Is there a rating drift? I remember that pure UCT no RAVE with 100k
  playouts got over 1700 elo.
 
  That seems a little high. My 50k-pure-UCT searcher is around
  1580 for a long time.
 
  Christoph
 
  ___
  computer-go mailing list
  computer-go@computer-go.org
  http://www.computer-go.org/mailman/listinfo/computer-go/
 
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Digital Mars

2009-04-20 Thread Łukasz Lew
From my expirience on windows, the best results I had with Intel C++ compiler
http://software.intel.com/en-us/articles/intel-c-compiler-professional-edition-for-windows-evaluation/
It had around 70%-90% of g++.

Lukasz

On Tue, Apr 21, 2009 at 03:18, Michael Williams
michaelwilliam...@gmail.com wrote:
 I got Libego compiled to a Windows DLL using Visual Studio and was able to
 call it, but I was only getting around 5k pps on my Core2.  So I wanted to
 try another compiler.  Has anyone used the Digital Mars C++ compiler?  Or is
 there another compiler I should try?
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] List of improvements for Monte-Carlo Go.

2009-04-18 Thread Łukasz Lew
I think it would be useful to have a list of existing important
heuristics / algorithms / ideas that improve Monte-Carlo Go.
If you are aware of any that are not on this list please add them.

Lukasz Lew

- MCTS / UCT
- capture/atari heuristics in heavy playouts / mogo patterns
http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf
- harvested patterns with elo ratings http://remi.coulom.free.fr/Amsterdam2007/
- criticality heuristic http://remi.coulom.free.fr/Criticality/
- progressive bias / progrssive unprunning
http://www.math-info.univ-paris5.fr/~bouzy/publications/CWHUB-pMCTS-2007.pdf
- first play urgency + locality
http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] Re: List of improvements for Monte-Carlo Go.

2009-04-18 Thread Łukasz Lew
On Sun, Apr 19, 2009 at 01:49, Łukasz Lew lukasz@gmail.com wrote:
 I think it would be useful to have a list of existing important
 heuristics / algorithms / ideas that improve Monte-Carlo Go.
 If you are aware of any that are not on this list please add them.

 Lukasz Lew

 - MCTS / UCT
 - capture/atari heuristics in heavy playouts / mogo patterns
 http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf
 - harvested patterns with elo ratings 
 http://remi.coulom.free.fr/Amsterdam2007/
 - criticality heuristic http://remi.coulom.free.fr/Criticality/
 - progressive bias / progrssive unprunning
 http://www.math-info.univ-paris5.fr/~bouzy/publications/CWHUB-pMCTS-2007.pdf
 - first play urgency + locality
 http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf


- RAVE. RLGO, http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Libego for Windoze

2009-04-10 Thread Łukasz Lew
I might have back to revert to make/cmake (from scons) after all.
There is some hope in google software construction toolkit and in
scons on google summer of code.

In libego a lot have changed. Now ego is truely a library and is
compiled separately.
ego/ego.cpp is enough to compile library. Then example/main.cpp is an
gtp engine.

Lukasz

On Fri, Apr 10, 2009 at 04:34, Darren Cook dar...@dcook.org wrote:
 Has anyone created VC++ project files for Libego?  Or any Libego Windows
 build?

 Have you tried starting a new project and dragging in main.cpp and
 gtp.cpp, then seeing if it compiles?

 (I've only compiled on linux; the libego I have on my development
 machine is from June 2007, presumably before scons support as I wrote my
 own makefile, but main.cpp and gtp.cpp seem to be the only top-level files.)

 Darren

 P.S. I used scons for a couple of years, but got frustrated by how hard
 it made trying to do something they'd not allowed for (e.g. having my
 unit tests compile and run in a specific order). I've also used jam and
 ant, but the past 3 or 4 years my make replacement of choice is... drum
 roll please... make. It turns out despite its poor design decisions
 (such as treating tab and space differently), at least I can always get
 the job done with it.

 --
 Darren Cook, Software Researcher/Developer
 http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
                        open source dictionary/semantic network)
 http://dcook.org/work/ (About me and my work)
 http://dcook.org/blogs.html (My blogs and articles)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Libego for Windoze

2009-04-10 Thread Łukasz Lew
Let's not spam list until we get the conclusion.
I will answer in private.

On Fri, Apr 10, 2009 at 20:03, Michael Williams
michaelwilliam...@gmail.com wrote:
 If I have only that file in the project, and fix some header includes, I am
 left with many errors still.  The first few are complaining about this
 block:

 uint64 FastTimer::get_cc_time () volatile {
  uint64 ret;
  __asm__ __volatile__(rdtsc : =A (ret) : :);
  return ret;
 }


 Łukasz Lew wrote:

 I might have back to revert to make/cmake (from scons) after all.
 There is some hope in google software construction toolkit and in
 scons on google summer of code.

 In libego a lot have changed. Now ego is truely a library and is
 compiled separately.
 ego/ego.cpp is enough to compile library. Then example/main.cpp is an
 gtp engine.

 Lukasz

 On Fri, Apr 10, 2009 at 04:34, Darren Cook dar...@dcook.org wrote:

 Has anyone created VC++ project files for Libego?  Or any Libego Windows
 build?

 Have you tried starting a new project and dragging in main.cpp and
 gtp.cpp, then seeing if it compiles?

 (I've only compiled on linux; the libego I have on my development
 machine is from June 2007, presumably before scons support as I wrote my
 own makefile, but main.cpp and gtp.cpp seem to be the only top-level
 files.)

 Darren

 P.S. I used scons for a couple of years, but got frustrated by how hard
 it made trying to do something they'd not allowed for (e.g. having my
 unit tests compile and run in a specific order). I've also used jam and
 ant, but the past 3 or 4 years my make replacement of choice is... drum
 roll please... make. It turns out despite its poor design decisions
 (such as treating tab and space differently), at least I can always get
 the job done with it.

 --
 Darren Cook, Software Researcher/Developer
 http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
                       open source dictionary/semantic network)
 http://dcook.org/work/ (About me and my work)
 http://dcook.org/blogs.html (My blogs and articles)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-09 Thread Łukasz Lew
Can you give some more info about experimental setup and the
algorithms you used?

On Thu, Apr 9, 2009 at 01:42,  w...@swcp.com wrote:
 Lukasz,

 My performance test suite did 7 ways of tracking liberties:
 * dense linked lists, (where 4 * number of positions are allocated)
I guess this is what gnugo-montecarlo implemented?
 * sparse linked lists, (where 256 * number of positions are allocated)
?
 * arrays of liberties, (256 * number of positions are allocated)
Is it like regular gnugo board implementation.
 * trivial pseudo-liberties
like libego I guess.
 * boesch computation for pseudo-liberties
an link?
 * bitsets
one bit per board location per string?
 * bitsets, with each bit in a separate word.
?

 I tested all of them using 2 techniques:
 * simple mc, (which never asked for the list of liberties for a group)
  Note that it also tests reseting the board in 3 ways.
one playout over and over again, or many randomized playouts? (you
mention 324 moves)
 * ladder reading exercises, which asked for the liberties of a group
  and used undo.


 Results are were pretty striking. Below is raw data.
 Tests were on a 3 year old Core2.
 * for pure mc: simple pseudo liberties was by far the fastest.
 * for ladder reading: arrays of liberties was by far the fastest.
 * as noted in other emails, linked lists have horrible cache behavior.
can you elaborate on that?
Does it apply to dense lists?

In general I'm about to implement dense lists.
What is slow about them in your implementation?
(in playouts)

 * 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, .33 games/sec
 undo 324 moves: total 3860 ms, each game 0.386000 ms, 2590.673575 games/sec
 reset 324 moves: total 3062 ms, each game 0.306200 ms, 3265.839321 games/sec
 ladder: total 3469 ms, each ladder 0.346900 ms, 2882.675123 ladders/sec

 SPARSE LINKS
 normal 324 moves: total 7109 ms, each game 0.710900 ms, 1406.667604 games/sec
 undo 324 moves: total 7703 ms, each game 0.770300 ms, 1298.195508 games/sec
 reset 324 moves: total 10890 ms, each game 1.089000 ms, 918.273646 games/sec
 ladder: total 8062 ms, each ladder 0.806200 ms, 1240.387001 ladders/sec

 BOESCH PSEUDO LIBERTIES
 normal 324 moves: total 2281 ms, each game 0.228100 ms, 4384.042087 games/sec
 undo 324 moves: total 3422 ms, each game 0.342200 ms, 2922.267680 games/sec
 reset 324 moves: total 2532 ms, each game 0.253200 ms, 3949.447077 games/sec
 ladder: total 5797 ms, each ladder 0.579700 ms, 1725.030188 ladders/sec

 SIMPLE PSEUDO LIBERTIES
 normal 324 moves: total 1985 ms, each game 0.198500 ms, 5037.783375 games/sec
 undo 324 moves: total 2328 ms, each game 0.232800 ms, 4295.532646 games/sec
 reset 324 moves: total 1922 ms, each game 0.192200 ms, 5202.913632 games/sec
 ladder: total 4890 ms, each ladder 0.489000 ms, 2044.989775 ladders/sec

 ARRAYS
 normal 324 moves: total 2578 ms, each game 0.257800 ms, 3878.975950 games/sec
 undo 324 moves: total 3313 ms, each game 0.331300 ms, 3018.412315 games/sec
 reset 324 moves: total 2703 ms, each game 0.270300 ms, 3699.593045 games/sec
 ladder: total 2703 ms, each ladder 0.270300 ms, 3699.593045 ladders/sec

 BITSET
 normal 324 moves: total 3453 ms, each game 0.345300 ms, 2896.032436 games/sec
 undo 324 moves: total 4203 ms, each game 0.420300 ms, 2379.252915 games/sec
 reset 324 moves: total 3828 ms, each game 0.382800 ms, 2612.330199 games/sec
 ladder: total 6735 ms, each ladder 0.673500 ms, 1484.780995 ladders/sec

 BITSET IN WORDS
 normal 324 moves: total 6172 ms, each game 0.617200 ms, 1620.220350 games/sec
 undo 324 moves: total 7203 ms, each game 0.720300 ms, 1388.310426 games/sec
 reset 324 moves: total 10157 ms, each game 1.015700 ms, 984.542680 games/sec
 ladder: total 7172 ms, each ladder 0.717200 ms, 1394.311210 ladders/sec

 What other methods have you tried?

 Lukasz

 On Thu, Apr 2, 2009 at 17:14,  w...@swcp.com wrote:
  Isaac,
 
  I implemented about 6 way to track liberties,
  a couple years ago, and measured the running
  performance, and by far the best is also the
  simplest: keep an array of liberties for each
  chain, and do a simple linear search.
 
  This may seem slow, but it has a couple real
  advantages. First, 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
really no benefit that I can see from using pseudo liberties.
   
Mark
   
 
 When John Tromp and I were thinking about these things in 2007 we
 decided to switch to counting real liberties instead of
 pseudo-liberties. Someone (Rémi?) told us that in the end the
 performance 

Re: [computer-go] Libego for Windoze

2009-04-09 Thread Łukasz Lew
There is plenty of info in documentation
http://www.scons.org/doc/production/HTML/scons-user.html
just search for Visual. I don't have VC++ so i can't help you :(
A wild guess would be to remove CXX and CXXFLAGS from SConstruct ...
maybe defaults will be good enough :)

Let me know if you get somwhere, I would update my version.

Lukasz

On Fri, Apr 10, 2009 at 00:24, Michael Williams
michaelwilliam...@gmail.com wrote:
 Cool, but I have no idea how to use SCons.  I downloaded and installed the
 Windows version.  Finally I found where it put itself in my system:  under
 my python/scripts folder (of course!).  I executed the scons batch file
 while in the libego folder and it found the SConstruct file.  But then it
 complained of not finding g++.  How do I use it with MS VC++?  I skimmed the
 FAQ and other docs on the website, but there does not appear to be much
 geared toward using it with Windows/MS VC++.  Any ideas?



 ?ukasz Lew wrote:

 libego is using SCons for building and
 SCons supports Visual Studio so
 SCons can be used to build libego.

 Lukasz

 On Thu, Apr 9, 2009 at 19:20, Michael Williams
 michaelwilliam...@gmail.com wrote:

 Has anyone created VC++ project files for Libego?  Or any Libego Windows
 build?
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-08 Thread Łukasz Lew
On Wed, Apr 8, 2009 at 01:13, Darren Cook dar...@dcook.org wrote:
 Linked lists have a terrible cache behaviour: every pointer (or index)
 dereference has a nearly 100% chance of causing a cache miss.
...

 It's quite easy and efficient to put all lists (cyclic, linked in one
 direction) of liberties (on one 19x19 board)
 into 4*19*19*sizeof (vertex) array. If vertex is int32 then it is about 1.5 
 kB.

 Hi Lukasz,  (private reply, but reply to the list is fine by me)
 Do you have some code demonstrating the above idea? It sounds
 interesting, but I cannot grasp what the data and algorithm look like.

4*19*19*4 is around 5.5 kB
On 9x9 it will be less than 1.5 kB

My mistake.

Are you still interested?


 Darren


 --
 Darren Cook, Software Researcher/Developer
 http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
                        open source dictionary/semantic network)
 http://dcook.org/work/ (About me and my work)
 http://dcook.org/blogs.html (My blogs and articles)

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Dependency inversions in Monte-Carlo Go

2009-04-08 Thread Łukasz Lew
On Tue, Apr 7, 2009 at 23:52, Claus Reinke claus.rei...@talk21.com wrote:
 Last time I looked more closely at what my MC bot (simple, no tree)
 was doing, I noticed that it has a tendency to try the impossible moves
 (suicides) first, discarding them as impossible for every genmove.

 Looking at more statistics, and thinking about it, it finally dawned on
 me that this is a consequence of the standard move evaluation approach
 based on win rate:

 - what one hopes for is the move with the best chance of winning
    (move enables win)
 - what one might get is a move that can only be played when winning
    (win enables move)

 For suicide moves, this is particularly obvious: they become possible
 only in the small number of games in which the opponent group
 surrounding the pseudo-eye has died (or is killed by playing in the
 pseudo-eye after removing all other liberties). The larger the group,
 the more likely that the game is going to be won if that group dies
 (roughly), so the larger the opponent group, the more tempting its
 pseudo-eyes seem for win-rate-based evaluation, however unlikely
 it is that the group actually dies in non-random play (certainly not
 by starting with the pseudo-eye).

 Something similar might be happening at a less obvious scale,
 such as playing a move into self-atari: there is one opponent
 move that renders this useless, but it is only one move - any
 game in which the stone is not captured might look rather
 good in terms of winning.

Good insight, well known too.


 Is there a known method of reducing the impact of these outliers
 (other than building a real tree and seeing by trial-and-error
 that many good-looking moves aren't really useful)?

Heavy playouts introduce lot's of knowledge to avoid moves that can be
easily and with high probability detected that are bad.

If you are asking about domain-independent techniques, then only MCTS
and AMAF/RAVE are well known.
Nothing else is in popular. But more and more people are thinking how
to make adaptive playouts.


 It seems
 that one cannot just devalue moves with low hit counts - after
 all, if there is only one sequence of moves that will rescue the
 game, one doesn't want to discount it just because it is rare.

 One thing that might help are move-number statistics: those
 moves that tend to be played late in the playouts in which
 they occur might depend on other moves to be played first,
 so perhaps one should have lower bounds on when each
 move can be considered for actual play?

In light playout moves are played at random, so the moment of playing
a move doesn't carry too much information.

Lukasz


 Claus




 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-08 Thread Łukasz Lew
On Wed, Apr 8, 2009 at 09:12, Darren Cook dar...@dcook.org wrote:
 Do you have some code demonstrating the above idea? It sounds
 interesting, but I cannot grasp what the data and algorithm look like.

 4*19*19*4 is around 5.5 kB
 On 9x9 it will be less than 1.5 kB

 Are you still interested?

 My own method is a large pre-allocated pool of Chain objects, which use
 std::vector, or fixed-size arrays, to store liberties. So I'm using a
 lot more memory. If your idea actually works and is just as quick then
 of course I'm interested.

The problem is similar to the problem of storing lists of stones in one group.
For a reference you can take a look for a libego implementation:
The file is in the spirit one class for all including unit tests, so
it's big. But just ignore it and track
chain_next_v

http://github.com/lukaszlew/libego/blob/00264d126ef6aa909dd7f52a668e8fe33e62aeb4/ego/board.cpp

chain_next_v is essentially a map vertex - next_vertex (vertex is
board location).
chain_next_v implements cyclic linked lists.
The trick is that it is implemented as an array of size 19*19*sizeof(vertex).
This is possible because one vertex can be always only in one group.

Now merging groups is as simple as crossing the lists (line 500).

If you have any questions so far, go ahead and ask :)

Now the liberties. One liberty can be in many groups. But in only as many as 4.
Let's call links between neighboring vertices pseudoliberties.
Now we can create a structure similar to chain_next_v that track all
pseudo-liberties of a group.
It would be again map implemented as an array indexed by vertex and
direction (N,W,S,E).

Now when you merge you just go over this list and throw away
duplicates. This can be done in linear time
using another map-array vertex - bool. That will have info whether
particular liberty (vertex without direction) was already in visited.

Hope this helps :)
Lukasz


 Darren

 --
 Darren Cook, Software Researcher/Developer
 http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
                        open source dictionary/semantic network)
 http://dcook.org/work/ (About me and my work)
 http://dcook.org/blogs.html (My blogs and articles)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] stone-age and patterns

2009-04-08 Thread Łukasz Lew
I'm just digging through tons of posts I didn't have time to read.
This one is particularly interesting for me.
Thanks for sharing this idea.
I don't have slow tactical reader, but it helps me to understand why
heavy playouts work while
direct optimization of strength of the playout doesn't help.

I wonder what would happen if we limit capture and atari heuristics to
only prehistoric stones.

Lukasz

On Mon, Feb 2, 2009 at 13:36, Mark Boon tesujisoftw...@gmail.com wrote:
 I haven't gotten very far yet in incorporating many of the suggestions
 published on this mailing-list into the MCTS ref-bot. As such I feel I still
 have a lot of catching up to do when it comes to MC programs, mostly due to
 lack of time.

 But I had an idea I wanted to share as I haven't seen anything like it
 described here. It comes forth from an observation I had when looking at
 playouts and what effects some of the patterns had on it. So far it's my
 opinion that guiding playouts is mostly useful in order to maintain certain
 features of the original position and prevent the random walk from stumbling
 into an unreasonable result.  As an example I'm going to use the simple case
 of a stone in atari that cannot escape. When random play tries an escaping
 move, I make the program automatically play the capturing move to maintain
 the status of the stone(s) (now more than one) in atari. When implementing
 something like that in the playouts however, more often than not this
 'pattern' arises not based on the original position but purely from the
 random play. I figured it doesn't help the program at all trying to maintain
 the captured status of a stone or stones that weren't even on the board at
 the start of the playout.

 So I tried a simple experiment: whenever a single stone is placed on the
 board I record the time (move-number really) it was created in an array I
 call stoneAge. When more stones are connected to the original they get the
 same age. When two chains merge I pick an arbitrary age of the two (I could
 have picked the smallest number, but it doesn't really matter). So for each
 chain of stones the array marks the earliest time of creation. Next, when a
 playout starts, I mark the starting time in a variable I call 'playoutStart'
 and there's a simple function:

 boolean isPrehistoric(int chain)
 {
        return stoneAge[chain]=playoutStart;
 }

 During playout, I only apply the tactical reader to chains for which the
 isPrehistoric() function returns true. Tests show that using this method
 doesn't affect the strength of the program at all. But the amount of time
 spent in the tactical reader is cut in less than half.

 I'm suspecting the same holds true to a large degree for other patterns, but
 I haven't had the time yet to test that. Other cases may not provide as much
 gain because they are cheaper to compute. But I think in general it's better
 to let the random play run its course as much as possible and restrict moves
 guided by patterns as much as possible to situations relevant to the
 original position. The stone-age information is very cheap to maintain so
 it's hardly a burden to use.

 Hope this helps anyone, especially those with slow tactical readers :) If
 anyone manages to use this successfully in other situations than tactical
 readers I'd be interested to hear it, as so far it's only a hunch that this
 has wider applicability than just tactics. I was going to wait until posting
 this until I had time to try it out for myself but lately I didn't have the
 time.

 Mark

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-08 Thread Łukasz Lew
 ...
 For a reference you can take a look for a libego implementation:

 Ah, so you already use this idea in libego?

libego uses this idea only for list of stones in chain.
list of liberties are not implemented.
but I guess I will implement it sometime soon.

 That is all I need to know,
 because, unless something has changed, libego does light playouts faster
 than any other program. (?)

I don't know about the speed of other programs.

libego currently does 40-45 kpps / GHz.
So if you have 3 GHz processor you will get around 130k playouts per second.

Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Fast ways to evaluate program strength.

2009-04-08 Thread Łukasz Lew
On Wed, Apr 8, 2009 at 10:46, Darren Cook dar...@dcook.org wrote:
 End game is another issue. MC programs only aim on winning, so they
 endgame is nor perfect in sense human would define it, but perfect
 enough to win if the game is winnable.

 You can modify komi to get the human expert and MC program in agreement.

 This suggests how you could automate a set of endgame problems: run Mogo
 (or similar) with lots of time and keep increasing/reducing the komi
 until you get a sudden swing in winning probability (e.g. from 60% to
 20% for side to play). That should tell you the komi to use, and at
 least one of the winning moves.

There might be no sudden swing if the program is not strong enough /
position not endgameish enough.


 To find alternative winning moves you'd need to have some way to tell
 Mogo, or whatever, it cannot choose the existing winning move you have,
 and must choose a different move. Once winning probability suddenly
 drops again it tells you there are no more winning moves left.

 If a program can generate the test set, why bother? I think it is useful
 because you can tune against it. E.g. if you give Mogo 120s per move to
 generate the test suite moves, then you tune until it can find the
 correct moves for the whole test suite on 1s per move.

 Tuning the endgame play is very important for MCTS search, because every
 playout always goes to the endgame. Strong endgame play in the playouts
 should make a program stronger at all stages of a game.

 What do you think? Is such a endgame problem suite useful?

I like the idea of a program generating a suite.
It seems usefull :)
Actually we might generalize it with storing much more information
than best move.
We can store value of each move, predicted territory etc.
Then we can see which tests correlate with strength and keep only these.

Lukasz


 Darren

 --
 Darren Cook, Software Researcher/Developer
 http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
                        open source dictionary/semantic network)
 http://dcook.org/work/ (About me and my work)
 http://dcook.org/blogs.html (My blogs and articles)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-08 Thread Łukasz Lew
On Wed, Apr 8, 2009 at 13:10, Isaac Deutsch i...@gmx.ch wrote:
 Hi Lukasz,

 I think I understand the way it is done for storing the stones; I do it
 exactly the same way.

 For the liberties: Does the index of the direction (NWSE) state where the
 chain is in respect to the liberty? So if you place a single stone on the
 board at position, you add 4 liberties and link them:
 - left of position, E
 - right of position, W
 - below of position, N
 - above of position, S
 Is that correct?

Yep.
I'm thinking about implementing it in libego with heavy playouts for
demonstration.
Maybe It will get libego some attention. :)


 I have another question. How do you efficiently track visited positions to
 avoid superko?
 I use zobrist hashing, but the memory it uses is quite big, and I think
 copying it from board to board takes a lot of time. Of course I don't do
 superko checks in the playouts, but in the UCT tree I have to check for it.

I use zobrist hashing as well. But the random base is separated from
board and shared so I don't copy it.
I copy just a xor hash which is no more than 8 bytes per board.



 Isaac

 Now the liberties. One liberty can be in many groups. But in only as many
 as 4.
 Let's call links between neighboring vertices pseudoliberties.
 Now we can create a structure similar to chain_next_v that track all
 pseudo-liberties of a group.
 It would be again map implemented as an array indexed by vertex and
 direction (N,W,S,E).

 Now when you merge you just go over this list and throw away
 duplicates. This can be done in linear time
 using another map-array vertex - bool. That will have info whether
 particular liberty (vertex without direction) was already in visited.

 Hope this helps :)
 Lukasz

 --
 Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss 
 für nur 17,95 Euro/mtl.!* 
 http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Dependency inversions in Monte-Carlo Go

2009-04-08 Thread Łukasz Lew
On Wed, Apr 8, 2009 at 14:41, Jason House jason.james.ho...@gmail.com wrote:
 On Apr 8, 2009, at 3:15 AM, Łukasz Lew lukasz@gmail.com wrote:

 On Tue, Apr 7, 2009 at 23:52, Claus Reinke claus.rei...@talk21.com
 wrote:

 Last time I looked more closely at what my MC bot (simple, no tree)
 was doing, I noticed that it has a tendency to try the impossible moves
 (suicides) first, discarding them as impossible for every genmove.

 Looking at more statistics, and thinking about it, it finally dawned on
 me that this is a consequence of the standard move evaluation approach
 based on win rate:

 - what one hopes for is the move with the best chance of winning
   (move enables win)
 - what one might get is a move that can only be played when winning
   (win enables move)

 For suicide moves, this is particularly obvious: they become possible
 only in the small number of games in which the opponent group
 surrounding the pseudo-eye has died (or is killed by playing in the
 pseudo-eye after removing all other liberties). The larger the group,
 the more likely that the game is going to be won if that group dies
 (roughly), so the larger the opponent group, the more tempting its
 pseudo-eyes seem for win-rate-based evaluation, however unlikely
 it is that the group actually dies in non-random play (certainly not
 by starting with the pseudo-eye).

 Something similar might be happening at a less obvious scale,
 such as playing a move into self-atari: there is one opponent
 move that renders this useless, but it is only one move - any
 game in which the stone is not captured might look rather
 good in terms of winning.

 Good insight, well known too.


 Is there a known method of reducing the impact of these outliers
 (other than building a real tree and seeing by trial-and-error
 that many good-looking moves aren't really useful)?

 Heavy playouts introduce lot's of knowledge to avoid moves that can be
 easily and with high probability detected that are bad.

 If you are asking about domain-independent techniques, then only MCTS
 and AMAF/RAVE are well known.
 Nothing else is in popular. But more and more people are thinking how
 to make adaptive playouts.

 Heavy playouts aren't the only way. Initialization heuristics and
 progressive widening also work.

Indeed :)




 It seems
 that one cannot just devalue moves with low hit counts - after
 all, if there is only one sequence of moves that will rescue the
 game, one doesn't want to discount it just because it is rare.

 One thing that might help are move-number statistics: those
 moves that tend to be played late in the playouts in which
 they occur might depend on other moves to be played first,
 so perhaps one should have lower bounds on when each
 move can be considered for actual play?

 In light playout moves are played at random, so the moment of playing
 a move doesn't carry too much information.

 Lukasz


 Claus




 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Zobrist hashing

2009-04-08 Thread Łukasz Lew
Ah, that's what you mean. :)
Actually I don't care too much about superko. I just care about the
move the genmove returns.
It would be better If I check at least some part of MCTS tree.
I just replay the game to check whether there is a hash collision. (I
use 64 bits)

If I would wan't fast checking I would probably use bloom filter.
http://en.wikipedia.org/wiki/Bloom_filter

Lukasz

On Wed, Apr 8, 2009 at 20:59, Isaac Deutsch i...@gmx.ch wrote:

 Like any hash function, multiple board positions can hash to the same
 value.  The idea is that the probability of encountering two board
 positions in the same game that have the same hash value is so low,
 that if you get a duplicate hash value you are practically guaranteed
 that it's a superko.

 Colin


 Yes, that is clear, but Lukasz didn't mention how he stores the past hash
 values. Sorry if my statement was not clear.

 Isaac
 --
 Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: 
 http://www.gmx.net/de/go/multimessenger01
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-08 Thread Łukasz Lew
2009/4/8 Gunnar Farnebäck gun...@lysator.liu.se:
 Łukasz Lew wrote:
 ...
 For a reference you can take a look for a libego implementation:
 Ah, so you already use this idea in libego?

 libego uses this idea only for list of stones in chain.
 list of liberties are not implemented.
 but I guess I will implement it sometime soon.

 You can find this idea in the GNU Go montecarlo board implementation,
 although with doubly linked lists, see for example
 http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c
 starting at line 43. This code is doing quite a lot of book-keeping to
 support tunable pattern-based heavy playouts, however, so it may be
 easier to start with a previous iteration of the code at
 http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b

Indeed that's almost exactly what I meant.
I can see that you are using doubly linked list to have a constant
time liberty_edge removal. Is there any other reason?
Have you considered amortized constant time (we remove it when we have
an occasion) approach?

Lukasz
PS
This is nice code to read :)


 /Gunnar
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-07 Thread Łukasz Lew
On Tue, Apr 7, 2009 at 07:40, David Fotland fotl...@smart-games.com wrote:
 In Many Faces' playouts I don't keep arrays of liberties.  I just keep the
 counts.  In the older program I keep linked lists of liberties.

How do you count the number of liberties when you merge two groups?
Do you walk over both chains searching for duplicates in their empty
neighbourhoods (duplicated liberties)?

Lukasz


 David

 -Original Message-
 From: computer-go-boun...@computer-go.org [mailto:computer-go-
 boun...@computer-go.org] On Behalf Of w...@swcp.com
 Sent: Monday, April 06, 2009 10:36 AM
 To: computer-go
 Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

 Isaac,

 My numbers were extracted from the insert() function,
 so my numbers don't say how long the average search.
 would be. When you place a stone on the board, you
 immediately add up to 4 adjacent liberties, one at a
 time. Never-the-less, it does say something.

 I have intended to measure the distributions of all
 set operations in the board funcions, but I have not
 finished them.

 Space is also very significant when choosing a
 representation. Another issue is whether the board
 can undo or rewind to saved positions. The arrays
 that store liberties take 19*19*256 shorts or
 184832 bytes. (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 faster. For
 x=8
  inserts, linear arrays are about 3 times faster. From your data I
 calculated
  an average liberty count of 2.8 (which seems low to me). This means that
 for
  the used board sizes, the constant time merge does not pay off vs. the
  constant time count.
 
  So I can confirm that the linear arrays do seem to be faster, however I
  haven't tested how they compare to pseudo libs. For heavier playouts, I
  reckon that true liberties might be a bit faster and more useful.
 
  Isaac
 
   Original-Nachricht 
   Datum: Fri, 3 Apr 2009 10:22:37 MDT
   Von: w...@swcp.com
   An: computer-go computer-go@computer-go.org
   Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique
 liberties?
 
   Isaac,
  
   Most groups have only say 4 to 8 liberties. This is why simple arrays
 of
   liberty locations work so well. The new Intel CPUs have instructions
   that can search strings 16 bytes at a time, so it could run even
 faster.
  
   Bit vectors also work, but if you want a true liberty count, then you
 have
   to avoid counting (1 or 1) as 2, which is the pseudo liberty problem,
 and
   which takes more code to write and more time to compute.
  
   When I started, I wanted to find a better implementation than gnugo,
 and
   I was unable to do so. Of course one can refine or simplify the gnugo
 code
   in many different 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 that there are only 2% as many liberties/adjacencies
   of size 8 as there are of size 0. Chains with liberties/adjacency
 lists
   of size 16 are so few as to be irrelevant.
  
      data here.
  
  
On Thu, Apr 2, 2009 at 5:14 AM,  w...@swcp.com wrote:
Isaac,
   
I implemented about 6 way to track liberties,
a couple years ago, and measured the running
performance, and by far the best is also the
simplest: keep an array of liberties for each
chain, and do a simple linear search.
   
This may seem slow, but it has a couple real
advantages. First, it works with the cache
to maximize locality. Second it is very simple.
   
   
This *does* seem slow, even when caching the number of liberties.
 You
mentioned that you did this a couple years ago, do you think it
 still
   holds
true? Thank you for the information.
   
This is what I do too. I never bothered with bit-arrays but
 possibly
that's simply because I fail to see how you can merge two chains
 and
count liberties in O(1).
   
Merging would be a simple OR operation. Counting can be done, for
   example,
with some kind of binary search. Counting the bits set has been well
researched and many different algorithms exist.
  
  
  
   ___
   computer-go mailing list
   computer-go@computer-go.org
   http://www.computer-go.org/mailman/listinfo/computer-go/
 
  --
  Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
 http://www.gmx.net/de/go/multimessenger01
  ___
  computer-go mailing list
  computer-go@computer-go.org
  

Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-07 Thread Łukasz Lew
Thanks. What about linked lists?
They seem to be both compact and fast to merge and detect duplicates.
Why have you abandoned them?

Lukasz

On Tue, Apr 7, 2009 at 17:42, David Fotland fotl...@smart-games.com wrote:
 Yes, I walk both chains looking for duplicates.  This is quite fast if done
 efficiently, since group merging is rare enough.  I found keeping the
 liberty arrays to be slower since they are big, so there is more copy
 overhead in the UCT tree, and they are not cache friendly.

 David

 -Original Message-
 From: computer-go-boun...@computer-go.org [mailto:computer-go-
 boun...@computer-go.org] On Behalf Of Lukasz Lew
 Sent: Tuesday, April 07, 2009 2:32 AM
 To: computer-go
 Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

 On Tue, Apr 7, 2009 at 07:40, David Fotland fotl...@smart-games.com
 wrote:
  In Many Faces' playouts I don't keep arrays of liberties.  I just keep
 the
  counts.  In the older program I keep linked lists of liberties.

 How do you count the number of liberties when you merge two groups?
 Do you walk over both chains searching for duplicates in their empty
 neighbourhoods (duplicated liberties)?

 Lukasz

 
  David
 
  -Original Message-
  From: computer-go-boun...@computer-go.org [mailto:computer-go-
  boun...@computer-go.org] On Behalf Of w...@swcp.com
  Sent: Monday, April 06, 2009 10:36 AM
  To: computer-go
  Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
 
  Isaac,
 
  My numbers were extracted from the insert() function,
  so my numbers don't say how long the average search.
  would be. When you place a stone on the board, you
  immediately add up to 4 adjacent liberties, one at a
  time. Never-the-less, it does say something.
 
  I have intended to measure the distributions of all
  set operations in the board funcions, but I have not
  finished them.
 
  Space is also very significant when choosing a
  representation. Another issue is whether the board
  can undo or rewind to saved positions. The arrays
  that store liberties take 19*19*256 shorts or
  184832 bytes. (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 faster. For
  x=8
   inserts, linear arrays are about 3 times faster. From your data I
  calculated
   an average liberty count of 2.8 (which seems low to me). This means
 that
  for
   the used board sizes, the constant time merge does not pay off vs.
 the
   constant time count.
  
   So I can confirm that the linear arrays do seem to be faster, however
 I
   haven't tested how they compare to pseudo libs. For heavier playouts,
 I
   reckon that true liberties might be a bit faster and more useful.
  
   Isaac
  
    Original-Nachricht 
Datum: Fri, 3 Apr 2009 10:22:37 MDT
Von: w...@swcp.com
An: computer-go computer-go@computer-go.org
Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique
  liberties?
  
Isaac,
   
Most groups have only say 4 to 8 liberties. This is why simple
 arrays
  of
liberty locations work so well. The new Intel CPUs have
 instructions
that can search strings 16 bytes at a time, so it could run even
  faster.
   
Bit vectors also work, but if you want a true liberty count, then
 you
  have
to avoid counting (1 or 1) as 2, which is the pseudo liberty
 problem,
  and
which takes more code to write and more time to compute.
   
When I started, I wanted to find a better implementation than
 gnugo,
  and
I was unable to do so. Of course one can refine or simplify the
 gnugo
  code
in many different 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 that there are only 2% as many
 liberties/adjacencies
of size 8 as there are of size 0. Chains with liberties/adjacency
  lists
of size 16 are so few as to be irrelevant.
   
   data here.
   
   
 On Thu, Apr 2, 2009 at 5:14 AM,  w...@swcp.com wrote:
 Isaac,

 I implemented about 6 way to track liberties,
 a couple years ago, and measured the running
 performance, and by far the best is also the
 simplest: keep an array of liberties for each
 chain, and do a simple linear search.

 This may seem slow, but it has a couple real
 advantages. First, it works with the cache
 to maximize locality. Second it is very simple.


 This *does* seem slow, even when caching the number of liberties.
  You
 mentioned that you did this a couple years ago, do you 

[computer-go] Fast ways to evaluate program strength.

2009-04-07 Thread Łukasz Lew
Hi,

I was wondering what are the good (fast/accurate) ways of evaluating
program strength.
The most accurate one is to play many games against gnugo or on KGS.
But it is quite slow as many games are needed.

Another one is to have set of labeled positions (win/loss)  and make
your program predict the labels. (This is what MoGo guys did)
It is much faster. But how well it is correlated with the true strength?

I had an idea to further refine this measure to predict ownership of
each intersection. This is much faster and completed games don't need
labeling.
It also converges much faster. And its easy to find type of positions
where your program predicts completely wrong.
Have anyone tried it?

Another idea is to try to predict moves in a set of (pro) games.
Is the prediction rate well correlated with program strength?

Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-07 Thread Łukasz Lew
2009/4/7 Colin Kern colin.k...@gmail.com:
 On Tue, Apr 7, 2009 at 12:33 PM, Łukasz Lew lukasz@gmail.com wrote:
 Thanks. What about linked lists?
 They seem to be both compact and fast to merge and detect duplicates.
 Why have you abandoned them?

 Lukasz


 Or a Hash Set, which has constant time insert, delete, contains, and
 size operations and guarantees no duplicates.  Merging groups would be
 linear, I think.

Hash set is usually bigger than array of liberties.
The bigger problem is that you can't get the single element of singleton.
(btw you don't need hashing to store liberties as liberties usually
are integers from some not too big interval)


 Colin
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Fast ways to evaluate program strength.

2009-04-07 Thread Łukasz Lew
Another idea is to try to predict moves in a set of (pro) games.
Is the prediction rate well correlated with program strength?

 No, very poorly correlated. I think that's well known.

It is well known that systems created for pro move prediction using no
search like MoyoGo, similat Microsoft's pattern system and Erik van
der Werf's neural net work well on prediction but very badly as
playing engines.

I would like to rephrase my question:
Let's measure prediction of pro moves of a whole engine while
modifying heavy playouts / MCTS in the engine.
How well might it work?

I like the idea of selecting positions/moves that give good
correlation with strength as the positions might me chosen
automatically

Lukasz.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?

2009-04-06 Thread Łukasz Lew
What other methods have you tried?

Lukasz

On Thu, Apr 2, 2009 at 17:14,  w...@swcp.com wrote:
 Isaac,

 I implemented about 6 way to track liberties,
 a couple years ago, and measured the running
 performance, and by far the best is also the
 simplest: keep an array of liberties for each
 chain, and do a simple linear search.

 This may seem slow, but it has a couple real
 advantages. First, 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
   really no benefit that I can see from using pseudo liberties.
  
   Mark
  

When John Tromp and I were thinking about these things in 2007 we
decided to switch to counting real liberties instead of
pseudo-liberties. Someone (Rémi?) told us that in the end the
performance difference wasn't very large, and we verified this.
   
Álvaro.
   

 Thanks. What is a fast way to track liberties?

 I thought about bit arrays. Merging to groups would take O(1), counting
 takes O(1)-ish, and memory required would be small.

 Of course I could also use STL's set structure, but I found it to be
 quite slow - it implements a set using a RB-tree. This was actually the
 reason I switched to pseudo libs.

 -ibd.
 --
 Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
 http://www.gmx.net/de/go/multimessenger01
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/




 --



 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Published source for mercy rule?

2009-03-01 Thread Łukasz Lew
mercy rule in libego:
http://github.com/lukaszlew/libego/blob/77b4dd4e035e4b44c17204557c9930a52e10e0c0/ego/playout.h
line 55.

Regards,
Łukasz Lew

On Fri, Feb 27, 2009 at 01:00, Seth Pellegrino se...@lclark.edu wrote:
 Hello list,

 I've managed to track the idea of a mercy rule in monte-carlo playouts back
 to a mail sent to this list by David Hillis:

 http://computer-go.org/pipermail/computer-go/2006-December/007478.html

 I'm currently putting the finishing touches on a paper which includes this
 idea, and I was wondering if anyone knew of any published sources where I
 could cite the idea?

 Thanks,

 Seth Pellegrino

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Playout acceleration

2008-09-05 Thread Łukasz Lew
There might be no need for heavier playouts to be slower.
Sometimes they are even faster. (maybe it was in case of Crazy Stone?)


On Fri, Sep 5, 2008 at 18:43, Michael Williams
[EMAIL PROTECTED] wrote:
 Has anyone tried heavy, slow playouts near the tree and light, fast playouts
 near the end of the game?  I'm calling this playout acceleration because
 it starts slow and speeds up.  You could have many different playout
 weights/speeds in a single playout.  It seems like a reasonable idea to me
 since the moves near the tree should be the most important.  Thoughts?

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Ladders and UCT again

2008-08-02 Thread Łukasz Lew
On Sat, Aug 2, 2008 at 16:06, Álvaro Begué [EMAIL PROTECTED] wrote:
 On Sat, Aug 2, 2008 at 9:43 AM, Jason House [EMAIL PROTECTED] wrote:
 On Aug 2, 2008, at 4:31 AM, Gunnar Farnebäck [EMAIL PROTECTED] wrote:

 It's often a good idea to bias capturing moves in the playouts,
 regardless whether it's a ladder or not. This would result in those
 stones being captured in most simulations.

 What method do people use for finding capture moves in playouts? Pseudo
 liberties can miss simple stuff like open triangles and one-eyed groups.
 Additionally, some literature discusses captures to add group liberties.
 What's the preferred method to detect
 that?___

 When we wrote dimwit, John Tromp found a fast method that I described
 here: http://computer-go.org/pipermail/computer-go/2007-November/012342.html

 However, my current thinking is that it's probably best to just keep a
 real liberty count and a list of liberties for each chain. This way
 you can also find atari moves, which would be very hard to do if you
 only keep pseudo-liberties.

Do you have any proposal how to find true number of liberties?

Cheers,
Lukasz

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Ladders and UCT again

2008-08-02 Thread Łukasz Lew
Can you describe your algorithms?

Cheers,
Lukasz

On Sat, Aug 2, 2008 at 19:36, Hideki Kato [EMAIL PROTECTED] wrote:
 David Fotland: [EMAIL PROTECTED]:
I keep liberty counts.

 Me too.  Also is Hiroshi.

 -Hideki

David

 -Original Message-
 From: [EMAIL PROTECTED] [mailto:computer-go-
 [EMAIL PROTECTED] On Behalf Of Jason House
 Sent: Saturday, August 02, 2008 6:43 AM
 To: computer-go
 Subject: Re: [computer-go] Ladders and UCT again

 On Aug 2, 2008, at 4:31 AM, Gunnar Farneb ck [EMAIL PROTECTED]
 wrote:

  It's often a good idea to bias capturing moves in the playouts,
  regardless whether it's a ladder or not. This would result in those
  stones being captured in most simulations.

 What method do people use for finding capture moves in playouts?
 Pseudo liberties can miss simple stuff like open triangles and one-
 eyed groups. Additionally, some literature discusses captures to add
 group liberties. What's the preferred method to detect
 that?___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
 --
 [EMAIL PROTECTED] (Kato)
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] On question about Libego110

2008-01-10 Thread Łukasz Lew
The code of any version is easy to get:
http://www.mimuw.edu.pl/~lew/hg/libego/?tags

The file you are talking about is here:
http://www.mimuw.edu.pl/~lew/hg/libego/?file/dfcd0a6db96e/uct.cpp


If you take a look at line 151 you see: (bias should be renamed to
number_of_visits)

explore_coeff  = log (bias) * explore_rate;

where bias is equivalent to this-bias i.e. number of visits in current node.
2 lines lower is a loop over all children where we compute:

   float child_urgency = child-ucb pl (explore_coeff);

where the body of ucb is:

return
(pl == player::black ? value : -value) +
sqrt (explore_coeff / bias);

and bias variable refers to the child's bias.

If you have any more questions, just ask.
Łukasz

On Jan 9, 2008 7:49 PM,  [EMAIL PROTECTED] wrote:
 I'm looking at the code of Libgo110. I have a question. In the file uct.cpp
 and the definition of class note_t, the explore_coeff is calculated from
 log(node-bias). But in the paper 'Modification of UCT with Patterns in
 Monte-Carlo Go' table 1 line 10 -17, the explore_coeff is calculated from
 log(nb), where nb is the summation of node-bias for all the child nodes.
 Whyis the difference? Or did I read the code wrong?

  Thanks for any explanation.

  DL
  
  More new features than ever. Check out the new AOL Mail!

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] libEGO v0.115

2007-12-22 Thread Łukasz Lew
Hi

New version of libEGO is available at :
http://www.mimuw.edu.pl/~lew/hg/libego/
The main improvements are:
- experiment.cpp file introduced which can now display ALL-AS-FIRST
move values through GoGui
  (just connect libEGO to GoGui)

- new + option for benchmark GTP command (i.e. benchmark 10 +)
  for displaying probabilities that vertex will be black after the playout.

- Big readability improvement in playout.cpp: Playout policy is now
separated from
  playout loop. It's easy now to change the playout policy.

- mercy rule turned off by default (20% drop in performance) (config.cpp)

- new convinient board.play introduced

- many small improvements

Have fun.
Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] low-hanging fruit - yose

2007-12-13 Thread Łukasz Lew
This is an artifact of using mercy rule.
You can change it in config.cpp
use_mercy_rule = true

Should I make it default?

Thanks,
Lukasz

On Dec 10, 2007 11:41 PM, Heikki Levanto [EMAIL PROTECTED] wrote:
 On Mon, Dec 10, 2007 at 04:08:48PM -0500, Don Dailey wrote:
  Would you rather be 95% confident of a win or 90% confident?There is
  only 1 correct answer to that question.

 Yes, if you can offer me reliable confidence numbers. We all (should) know
 that MC evaluations suffer from systematic problems that can not just be
 averaged away statistically.

 Compare these two positions:

 playout_benchmark 1
 = Initial board:
 komi 7.5
A B C D E F G H J
  9 . . . . . O O O O 9
  8 O O O O O O O O O 8
  7 O O O O O O O O O 7
  6 O O O O O O O O O 6
  5 # # # # # # # # # 5
  4 O O O # # # # # # 4
  3 O O O O . # # # # 3
  2 . O O O . # # # . 2
  1 # . O O . # # . # 1
A B C D E F G H J
 Performance:
   1 playouts
   0.032002 seconds
   312.481 kpps
 Black wins = 1937
 White wins = 8063
 P(black win) = 0.1937


 playout_benchmark 1
 = Initial board:
 komi 7.5
A B C D E F G H J
  9 . # . . . O O O O 9
  8 O O O O O O O O O 8
  7 O O O O O O O O O 7
  6 O O O O O O # # # 6
  5 # # # # # # # # # 5
  4 O O O # # # # # # 4
  3 O O O O . # # # # 3
  2 . O O O . # # # . 2
  1 . . O O . # # . # 1
A B C D E F G H J
 Performance:
   1 playouts
   0.084006 seconds
   119.039 kpps
 Black wins = 7746
 White wins = 2254
 P(black win) = 0.7746


 Which one is better, 77% or 19%?


 I must admit I don't quite understand the results myself. But they are made
 with LibEGOs MC, so I trust they show what traditional MC simulation would
 see. The top group is obviously alive but can die in a MC simulation. The
 bottom group is obviously unsettled, so who ever plays there first should
 win the game. I suppose in some follow-ups, white may be able to live in the
 resulting space, and win the game that way too.

 This has nothing to do with the argument of attacking the larger group first,
 rather the contrary. But it shows that MC evaluations can give results so
 badly off that there is not always much point in distinguishing between your
 80% and 85% confidence.

 Regards

Heikki

 --
 Heikki Levanto   In Murphy We Turst heikki (at) lsd (dot) dk


 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Hint for good Bayes book wanted

2007-07-23 Thread Łukasz Lew

Absolutely the best book I've seen is:

Christopher M. Bishop
Pattern Recognition and Machine Learning

It's totally awesome!

Strong points:
- It have both Bayesian and non Bayesian ways explained
- the explanation is clear
- figures are so helpful (and aesthetic)
- it concentrates on prediction and classification and have
algorithmic perspective
  (contrary to MacKay's book)

There is a free chapter on graphical models:
http://research.microsoft.com/~cmbishop/PRML/Bishop-PRML-sample.pdf

Lukasz Lew

On 7/23/07, chrilly [EMAIL PROTECTED] wrote:

I have a Phd in statistics. But Bayesian methods were at that time a
non-topic. I know the general principles, but I want to learn a little bit
more about the latest developments in the field. Bayes is now chic, there
are many books about it. I assume also a lot of bad ones.
Can anyone recommend me a good state of the art book about Bayesian
inference. Should be somewhat in the applied direction, but also with a
sound mathematical background.

Chrilly

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Explanation to MoGo paper wanted. (BackGammon Code)

2007-07-03 Thread Łukasz Lew

On 7/3/07, chrilly [EMAIL PROTECTED] wrote:

 
  We just presented our paper describing MoGo's improvements at ICML,
  and we thought we would pass on some of the feedback and corrections
  we have received.
  (http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf)
 

 They are probably referring to this paper:
 http://www.cs.ualberta.ca/~mmueller/ps/silver-ijcai2007.pdf

No, I am referring to the icml2007 paper.


What I said is that ICML paper mentions RLGO evaluation function which
is described in this paper:
http://www.cs.ualberta.ca/~mmueller/ps/silver-ijcai2007.pdf



 It's because Go is not only game in the world and certainly not only
 reinforcement learning problem. They are using a widely accepted
 terminology.

But a very inappropriate one. I have read Suttons book and all the things I
know (e.g. TD-Gammon) are completly obfuscated. Its maybe suitable to
present generel concepts, but it is extremly complicated to formulate an
algorithm in this framework.
But the main point is: I think game programmers should be more proud of
their work and should present their results in the language of game
programming. We are the ones which make progress, not these paper tigers.


I agree that game programmers make most of the progress in game domain.



When I wrote the Null-Move article, some referees pointed out, that the
article is not scentific enough. The NullMove was already known and even
published before. But only after this non-scientific article it became a
must have in chess programming. The pseudo-code had a bug and I see till
today this bug in open-source chess programms.

 Can You share the source?

Yes. See attached Archive. The interface and the UCT part are rather
primitive. The move-generator is better/faster than the ones I have seen in
other public code (but can be certainly improved). The evaluation was
published by G.Tesauro, but the implementation is more efficient. It is -
according to G.Tesauro - a baseline for an evaluation. Every usefull
evaluation function should clearly beat this one.
The purpose of the code was to study the effect of Monte-Carlo sampling. I
was deeply impressed how much better the Rollout/Monte-Carlo version plays.


Thanks,
I asked for the source, mostly because I expect to learn something from you.

Best regards,
Lukasz



Chrilly

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] ICGA 2007 MoGo-Steenvreter

2007-06-15 Thread Łukasz Lew

This is my analysis. It may be flawed but I hope it has some value.

It would be very interesting to see what mogo thinks on those variations.

Best Regards,
Lukasz


On 6/14/07, Sylvain Gelly [EMAIL PROTECTED] wrote:

Hello Sanghyeon, thank you for your comments.

  After white (mogo) H2, MoGo was estimating 74%, and expecting:
  H2 G1 H3 B1 A1 B3 H1 F8 B5 H4
 This is far too optimistic. Why would black play H2? :-)
Sorry, white played H2. The sequence I gave starts with white move :).
Black was expecting to play G1 :).

  Black played H3, and estimation increased to 81%, white B3 and expecting:
  B3 B1 A1 B4 C5 C4 A3 C6 B6 B5
 After B3 B1 A1, black G1 and then B1 F1 D1 B4 and white is dead.
Ok thanks. So good white actually played G1 instead of A1 after black B1 then.


  Actually during pondering MoGo realized that it was lost then, because
  black played the expected move (B1), but the estimation was then 
  50%.
 MoGo realized too. Actually G1 is an interesting move. After white 48,
 all groups on the board is alive and white actually wins by my counting.
 So I think that white 50 is a losing move.

Oh, so contrary to what I believed, you say (if I understand you
correctly) that the mistake was done in the upper left group and not
in the bottom center group?


Thank you,
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/



tour_169-round_9-game_2-analysis.sgf
Description: Binary data
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] analysis of UCT and BAST

2007-05-31 Thread Łukasz Lew

Please notice that it is not my work.
All the experiments were performed by Filip Gruszczynski.

He corrected the webpage. (should be EGO_POWER)

Best Regards,
Lukasz

On 5/30/07, Rémi Coulom [EMAIL PROTECTED] wrote:

Łukasz Lew wrote:
 I'm not sure whether You have noticed, but my student made an
 empirical comparison
 between BAST, UCT and other formulas.

 It can  be found here:
 http://students.mimuw.edu.pl/~fg219435/Go/

 Best Regards,
 Lukasz Lew


Hi Łukasz,

You write that EGO_BAST seems to be a bit more effective against
GnuGo, but I cannot see any test result of EGO_BAST against GNU Go on
your page.

Rémi

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] analysis of UCT and BAST

2007-05-31 Thread Łukasz Lew

On 5/31/07, Remi Munos [EMAIL PROTECTED] wrote:

Thanks Lukasz for the link.
I'm not sure to understand precisely the formulas. For example, for
ego_bast_sqrt, you mention that the bast value of a node is the min of the


As I said previously this is not my experiment.
You can reach the author - Filip Gruszczynski - using
gruszczy (at) gmail (dot) com


max of the bast values of the children and the own value of the node plus the
confidence interval term sqrt(explore_rat * sqrt(p) / n) where p and n are
the number of visits of the parent and current nodes.
Do you add to the own value, an addition smoothness sequence (the delta term
in the bast paper)? Here I think a such smoothness term could be
k gamma^d /sqrt(n)
(for some well chosen k and gamma constants, with a large k and gamma1)
where d if the depth of the current node.
This would take into account the time needed for the bias (difference between
the true value of a node and the empirical average of the obtained rewards)
to decrease to 0 (since we know that from the sqrt sequence above, the bias
will decrease with rate O(1/sqrt(n)).
From your formula, it does not seem that you add such an additional smoothness
sequence, so I would say that this bound would be very close to a ego_sqrt
(because the argument in the min above will most always be the second
argument).
Tell me if I misunderstood the formulas of your student.


The simplest and most definite way is to look at the source code.

Best Regards,
Lukasz

PS
Filip noted that more complicated versions of BAST were worse.




On Wednesday 30 May 2007 21:05:15 Łukasz Lew wrote:
 I'm not sure whether You have noticed, but my student made an
 empirical comparison
 between BAST, UCT and other formulas.

 It can  be found here:
 http://students.mimuw.edu.pl/~fg219435/Go/

 Best Regards,
 Lukasz Lew

 On 5/30/07, Remi Munos [EMAIL PROTECTED] wrote:
  I have updated the BAST paper, providing additional comparison with UCT,
  as suggested by one person in the list. See:
  https://hal.inria.fr/inria-00150207
 
  Basically, in the considered examples, BAST with an appropriate
  smoothness sequence performs always better than both UCT and Flat-UCB.
  Now, the best smoothness coefficient is always smaller than the constant
  corresponding to the true smoothnes of the tree, and sometimes very close
  to 0 (which corresponds to UCT).
  Since go is way more complex than the problem of optimizing a simple 1-d
  function, I would say that no theoretical work could predict whether BAST
  would do better than UCT or not, in Monte-Carlo-go.
 
  Best, Remi
 
  ___
  computer-go mailing list
  computer-go@computer-go.org
  http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/



--
Rémi Munos
Directeur de recherche INRIA
Sequential Learning project
http://www.grappa.univ-lille3.fr/cgi-bin/twiki/view/Sequel/Munos
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] analysis of UCT and BAST

2007-05-30 Thread Łukasz Lew

I'm not sure whether You have noticed, but my student made an
empirical comparison
between BAST, UCT and other formulas.

It can  be found here:
http://students.mimuw.edu.pl/~fg219435/Go/

Best Regards,
Lukasz Lew

On 5/30/07, Remi Munos [EMAIL PROTECTED] wrote:

I have updated the BAST paper, providing additional comparison with UCT, as
suggested by one person in the list. See: https://hal.inria.fr/inria-00150207

Basically, in the considered examples, BAST with an appropriate smoothness
sequence performs always better than both UCT and Flat-UCB.
Now, the best smoothness coefficient is always smaller than the constant
corresponding to the true smoothnes of the tree, and sometimes very close to
0 (which corresponds to UCT).
Since go is way more complex than the problem of optimizing a simple 1-d
function, I would say that no theoretical work could predict whether BAST
would do better than UCT or not, in Monte-Carlo-go.

Best, Remi

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Efficiently selecting a point to play in a random playout

2007-05-27 Thread Łukasz Lew

Hi,

I've tested many approaches, and the one I implemented is clearly the best.
The bias that Peter Drake talks about is negligible and doesn't have a
noticeable impact
on playout results.
(and uniformity of playout isn't something to fight for in MC Go)

Jason, can You tell me why You don't want to use libego instead?
Actually this is open question to all comp-go readers.

Is libego too complicated? Do You have problems with compilation?
Or You are not comfortable with the GNU license? Any other reason?

Best Regards,
Lukasz Lew


On 5/27/07, Jason House [EMAIL PROTECTED] wrote:

  As I get into the home stretch of rewriting the core of my bot, I want
to add a monte carlo player.  I've realized that picking a random move
to play is non-trivial since it's such a key element in playout speed.

  An array of legal positions has easy lookup, but may not be easy to
maintain... I guess it'd require storing a mapping between board
position and index into the legal positions array so that a move that
becomes illegal can be quickly removed (by moving the item from the tail
of the array into the empty location).

  Looking at libego, I see it does a variant on this where it maintains
an array of empty points.  If the random index it picks is disallowed,
it'll scan through the array (with wrapping around the end) until it
either finds an allowed move or returns to its starting point.

  Which methods have people tried and what works best?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


[computer-go] UCT formula testing

2007-05-13 Thread Łukasz Lew

My student - Filip Gruszczynski, made extensive testing of alternative
formulas for UCT.
Over 30 000 games; ~10 different algorithms with various constants
(including BAST).

http://students.mimuw.edu.pl/~fg219435/Go/


From the article:

It seems, that the more simple approach we take, the better. EGO_SQRT
seems to be the best when compared with other ego programs, though
EGO_BAST seems to be a bit more effective against GnuGo - possibly
with better constants it could win even more.

--

Taking the opportunity, I also would like to announce that development
of libego will be stopped at least for 4 months (I'm on 3 month
internship + vacations :] ).

Best Regards,
Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] The physics of Go playing strength.

2007-04-14 Thread Łukasz Lew

Libego played at old CGOS with name sth like UCT-107-???k

100k was about 1550k
200k about 1650k

I don't remember and I can't find the rating list anymore.

Łukasz

On 4/14/07, Darren Cook [EMAIL PROTECTED] wrote:

 I've been trying the libego program out of the box, and am up to
 200,000 UCT playouts, but still gnugo 3.6 on level 6 is winning 10 out
 of 10. ...

 If 200,000 play-outs is being beat, something is broken.  Even
 a bad implementation should do better than that.

 Does libego provide a full UCT implementation out of the box?

Thanks for the reply Don.

I've just reviewed the code again and it seems to be the same algorithm
as described at http://senseis.xmp.net/?UCT

The way it is implemented differs from the pseudo-code in a few minor
ways, but notably: it (libego) maintains a float win-rate for the node,
which is updated, rather than storing wins and recalculating win-rate
each time. I suppose there could be a rounding error creeping in there.

I've tried changing it to use two ints, for total visits and black wins,
and then calculate the winning rate on the fly. But it still cannot win
a game against gnugo on level 6: it lost 9 out of 9 at 100K playouts,
and has lost 4 out of 4 at 500K playouts. Yet there is no major bug:
when I played it a game at each of 100K and 500K it played reasonable
go, and I could notice that 500K was stronger.

Has anyone else tried studying or using libego's UCT implementation? Is
there another open source implementation of UCT I can compare against?

 One thing that I think most people are doing is related to how you
 select a move once you have finished the search.   Do you pick the
 highest scoring move? ...

No, currently it chooses the most visited node, ignoring score.

Darren


___
computer-go mailing list
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] RNGs

2007-03-29 Thread Łukasz Lew

You can get it from ego library - file utils.cpp
Łukasz

On 3/29/07, Chris Fant [EMAIL PROTECTED] wrote:

Can someone please re-send that list of fast/small random number
generators?  I can't seem to find it.  Thanks.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] libego questions on playout

2007-03-18 Thread Łukasz Lew

Hi,

On 3/17/07, Peter Christopher [EMAIL PROTECTED] wrote:

Hi LL or any others who know,

I've been playing with libego.  Nice work, thanks for distributing it.
 I am working on understanding some of the details of uct.cpp, in
particular how it does playouts in life-death and ko situations.  I
will try to add some helpful comments to the code once I have it
figured out, so that others can more quickly understand it.


You can also ask question (to me) and I will answer in form of comments.
I found this a quite effective way of putting comments in proper places .
( to avoid: i++; // increases i :-] )



Perhaps you could help me out with a few basic questions.

Does the board code (board.cpp) currently treat ko, suicide, multiple
ko, etc, according to standard go rules or is there work remaining to
be done for it to be precisely correct?


simple ko is supported in board.cpp

board.cpp::play_no_pass returns play_ko
when illegal move (due to simple ko) was tried.



Does the playout code (playout.cpp run() ) follow the board code
exactly in examining the legality of all possible moves?


Unfortunately, I do not understand Your question.

simple_playout::run uses
simple_playout::play_one

which look for move that is not simple ko and not *single stone suicide*

Best Regards,



Thanks,
Peter
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] GTPv3

2007-03-02 Thread Łukasz Lew

On 3/2/07, Markus Enzenberger [EMAIL PROTECTED] wrote:

On Thu March 1 2007 05:22, Łukasz Lew wrote:
 The most important thing is controller - engine architecture.
 There are situations that engine would like to have the control. For

these requests come up once in a while, but IMO the clear separation between
who is the controller and the engine is a big advantage of GTP. It makes both
the implementation of engines and controllers much easier.


I agree



Can you do simple, single-threaded controller scripts with UCI? Is it used for
as many use cases as GTP is, ranging from regression testing to any kind of
automated experiments with Go engines?

The Go server protocols are designed for humans and asynchronous sending of
messages between them at any time, but does it make sense for a computer
engine to allow it to start chatting, whenever it feels like it?


I think it is sometimes important to allow the engine to sent some
information including chatting.



I think that GTP should not be extended in a way that makes the implementation
of engines or controllers more complicated.


I agree.

So is there any solution not using stderr?



 In gogui this is solved by using stderr to send those commands, but:
 - stderr is not network transparent

Remi Coulom convinced me that it is more convenient for the engine to write to
standard error and he was right. Typically the GTP interface is only one of
several interfaces to lower level Go engine code and you don't want to make
lower level code aware of this.


I would like to have GTP flexible enough to be the only interface needed.



One idea I had in mind to address this was to allow the engine to send comment
lines before the actual response. Then you could tunnel the standard error
output through a network connection in these comment lines, maybe starting
with a special keyword.


That is interesting.
But why before the actual response?
It should be allowed to sent it any time, and it's a matter of server
implementation when
It will parse it.



It would need only a minor modification to existing controllers to ignore all
text before the response. Alternatively, one could extend the tools GtpServer
and NetGtp in the GoGui package to internally transmit standard error text in
such a way, that would be transparent for the engine and controller on
different hosts.

 6. Position setup. I had conversation with Marcus about setup in GoGui.
 And we concluded that there should be a separate command for that.

The coming version 1.0 of GoGui will support a setup command. It is a
simplified version of a suggestion I made a while ago to the GTP list and
uses a syntax like:

gogui-setup b A1 b B2 w C3

Originally I had an undoable setup command in mind to incrementally follow
setup stones in SGF trees, but it is much easier for engine programmers to
handle only full position setup on empty boards, so GoGui will follow the SGF
properties incrementally and translate setup nodes into clear_board /
gogui-setup sequences.

- Markus
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] GTPv3

2007-03-01 Thread Łukasz Lew

Hi,

There are some issues that are not so well defined in GTP v2.
Maybe GTP v3 should be released to avoid too much legacy later?

1.
The most important thing is controller - engine architecture.
There are situations that engine would like to have the control. For instance
When he want to send commands to GUI to draw something while he is working.

In gogui this is solved by using stderr to send those commands, but:
- stderr is not network transparent
- syntax is not standardized
- there is no confirmation about success / failure for those commands.

2.
The second thing is that there are many variables in the engine (komi,
board size, time, etc).
Developers tend to have more of them to control various parameters of
the engine.
End users could like to have some control over strength of the algorithm, etc.

3. If GTP would supports chats, KGS would probably implement it.

4. Opponent identification.

5. Interrupt. Users do not always want to wait until the program finish work.
 GoGui uses comment #interrupt to do it, but this is a hack.
(this is somewhat related to 1.)

6. Position setup. I had conversation with Marcus about setup in GoGui.
And we concluded that there should be a separate command for that.

Would You like to have those issues solved?
I hope we can get somewhere. :)

Best Regards,
Łukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Big board. Torus ?

2007-02-23 Thread Łukasz Lew

The number of liberties is not the same measure as dimensionality.
You need to look at a area/boundary ratio.

At some point I adapted libEGO to hexagonal topology, and the game -
Hex Go ( Ho? :-) )
was actually very interesting. Major features are:

- almost no capture tactics
- no ko
- a lot of cut/connect tactics
- a high ration strategy/tactics
- interesting nakade :)

Best,
Łukasz

On 2/23/07, Jacques Basaldúa [EMAIL PROTECTED] wrote:

Magnus Persson wrote:

  ... it is impossible to make eyes when attacks on the eyes
  has so many directions to escape. Every reasonable well
  played game will end in seki.

I totally agree. In 2D a free stone has 4 liberties. In 3D, 6. In nD, 2n.

The higher n, the less interesting. You could give 8 liberties to a stone
by including the diagonal neighbors, but that would just produce that
everything reasonable survives in seki. All games are a draw.

4 liberties is the magic number, but playing without edges mat be fun.

Jacques.


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Library of Effective GO routines v 0.106

2007-02-22 Thread Łukasz Lew

I do not understand it. Maybe someone does?
I've made some tests on 2 core processors, and I have strange results.
Some of 2 core processors got results exactly 2x times worse than they should.
Why?
I have no idea.
But 2.8 Ghz 2 core works exactly like my 1.4 laptop.


Also version of g++ does matter.
Łukasz

On 2/21/07, Brian Slesinsky [EMAIL PROTECTED] wrote:

The only real change is to link against the Boost libraries I
installed using DarwinPorts.  Here are the diffs:

-CFLAGS += -Wall #-static #-Wno-long-long -Wextra -Wno-variadic-macros
+CFLAGS += -Wall -I/opt/local/include -L/opt/local/lib

It's a desktop and I don't see any options for power management.
Maybe it's just a difference in processors?  It's a two core chip but
perhaps not as fast at single-threaded apps.  Adding multithreading
might help.

- Brian

On 2/21/07, Łukasz Lew [EMAIL PROTECTED] wrote:
 On 2/21/07, Brian Slesinsky [EMAIL PROTECTED] wrote:
  [resending; apologies if you get this twice.]
 
  Hi,

 Hi Brian,

 
  This is my first post to the list, so I'll introduce myself:   I'm a
  software developer and just getting started with playing Go.  I read
  the article in the Economist and thought that the work on Monte-Carlo
  based Go programs sounds promising.  I'm not interested in writing my
  own Go program but would like to experiment with improving existing
  programs.

 Have fun ;)

 
  I built and started libego on an iMac with a 2GHz Intel Core Duo.  The
  initial benchmark reports these results:
 
  Performance:
10 playouts
1.84255 seconds
54.2727 kpps
  Black wins = 43983
  White wins = 56017
  P(black win) = 0.43983
 
  Are these numbers to be expected?

 They are correct, except rather low performance.
 It should be rather about 80 kpps (kilo playouts per second)

 There are few possible reasons for this:
  - You are using a laptop with power management
   - You changed Makefile or some source files to make it compile on Mac?

 Best Regards,
 Łukasz Lew

 
  - Brian
  ___
  computer-go mailing list
  computer-go@computer-go.org
  http://www.computer-go.org/mailman/listinfo/computer-go/
 

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Library of Effective GO routines v 0.106

2007-02-22 Thread Łukasz Lew

On 2/22/07, Sylvain Gelly [EMAIL PROTECTED] wrote:

Hello,

 I do not understand it. Maybe someone does?
 I've made some tests on 2 core processors, and I have strange results.
 Some of 2 core processors got results exactly 2x times worse than they should.
 Why?
 I have no idea.
 But 2.8 Ghz 2 core works exactly like my 1.4 laptop.
 Also version of g++ does matter.

Here, from my experience, the following can matter a lot:
- version of g++ (g++ 4.1 gave me +50% against g++ 4.0 on an opteron!)


True.


- version of the libc: even compiled with a modern compiler, a program
running on a machine with an old version of the libc can be very
significantly slower (-30% observed!).


True.


- exact version of the processor: today the frequency means nothing,
nor the name of the processor. You have to check the exact numbers.
And I also observed that even the small numbers as the stepping
number, matters. MoGo runs faster on my P4 3.4 Ghz  than on a 3 years
newer P4 3.8 Ghz, which has also more cache. I ran test on other P4,
and the slower had a different stepping, that's all (all are dell
computers using same hardware).
- Measure of time: if you take the CPU time, on multiprocessor
machine, while using multithreading, sometimes the reported time is
not what you expect (generaly reported for all the threads), so when
you calculate the speed of playouts, you can have a 2x/4x factor.

Hope that can help,


Thanks for information.


I used a static binary compiled in one place with good compiler.
I do not use threads, nor external libraries (in benchmark).
I checked exact stepping in /proc/cpuinfo

So I still have no idea :)

Łukasz


Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Library of Effective GO routines v 0.106

2007-02-21 Thread Łukasz Lew

On 2/21/07, Brian Slesinsky [EMAIL PROTECTED] wrote:

[resending; apologies if you get this twice.]

Hi,


Hi Brian,



This is my first post to the list, so I'll introduce myself:   I'm a
software developer and just getting started with playing Go.  I read
the article in the Economist and thought that the work on Monte-Carlo
based Go programs sounds promising.  I'm not interested in writing my
own Go program but would like to experiment with improving existing
programs.


Have fun ;)



I built and started libego on an iMac with a 2GHz Intel Core Duo.  The
initial benchmark reports these results:

Performance:
  10 playouts
  1.84255 seconds
  54.2727 kpps
Black wins = 43983
White wins = 56017
P(black win) = 0.43983

Are these numbers to be expected?


They are correct, except rather low performance.
It should be rather about 80 kpps (kilo playouts per second)

There are few possible reasons for this:
- You are using a laptop with power management
 - You changed Makefile or some source files to make it compile on Mac?

Best Regards,
Łukasz Lew



- Brian
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Effective Go Library v0.101

2007-02-17 Thread Łukasz Lew

On 2/17/07, Luke Gustafson [EMAIL PROTECTED] wrote:

Lukasz, any chance you can access the assembly to see how the compiler
optimized it differently?  That is a strange result.  All that I could think
of is, if you have several places where the function is called, and the
compiler used to be inlining it, it may be faster (for cache reasons) to
make it a function call instead of inlining.  Inlining is not always
fastest!


There was only one place and no inlineing :)
So it was pure difference static/dynamic call.
And I did immediately look at the asm, the difference was very small.
exactly static / dynamic call :) So I don't get it.
But I don't won't to get it. Is to much for me. I.e. too absorbing :)




Regarding function pointers--from Agner Fog's guide:
3.7 Indirect jumps (all processors except PM and Core2)
Indirect jumps, indirect calls, and returns may go to a different address
each time. The
prediction method for an indirect jump or indirect call is, in all
processors except PM and
Core2, simply to predict that it will go to the same target as last time it
was executed. The
first time an indirect jump or indirect call is seen, it is predicted to go
to the immediately
following instruction.  (The Pentium M  Core2 have more sophisticated
indirect jump prediction)


I tested on PM, so this may be an explanation.

But anyway this is so small *detail* that I prefer to concentrate in
different places.
For instance I just implemented UCT and I want to publish it asap.:)

Lukasz



So, if a function pointer always points to the same function, all processors
will predict the branch correctly!  I am doubtful function objects would be
much faster, except that they may be more likely to be inline-able.

Also I disagree that well-designed code should cause function objects to be
predicted at compile time--it seems to me that their purpose is for run-time
polymorphism!


I will just tell You about my experiences:

 - allmost all code of benchmark in Ego library is inlined (remove_stone is
 not)
 - function pointer are usually inefficient, because jump prediction works
 poorly
 - when I introduced a parameter to simple_playout::run: function
 pointer that replaced play_one and always put address of play_one
 there, then the code was slightly faster.
 I have *no idea* why it was so.

 - and most important: KISS

 Lukasz


 On 2/16/07, Darren Cook [EMAIL PROTECTED] wrote:
  trouble.  Also, the alternative is usually function pointers which
  have
  atleast 50 times the overhead of a function object.  Correct me if I'm
  wrong.
 
  function objects really cannot be 50 times more efficient as function
  pointer are rather efficient with very little overhead.

 With well-designed code, function objects (functors) should be
 compiled inline, and have zero overhead. Function pointers are never
 inlined (unless modern compilers are getting *really* clever), so they
 always have some overhead. Functors are therefore divide-by-zero-times
 more efficient (I don't know where Nick got the 50 times figure from :-).

 (If the functor is large enough to not be inlined then it is execution
 time that dominates and function call overhead is not important.)

 Using functors might cause more code, so less code fits in cache. I
 don't know how that affects overall performance.

 Darren

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Effective Go Library v0.101

2007-02-15 Thread Łukasz Lew

The library is just a bunch of code and You can do whatever You want with it.
I'm realistic, what matters is: what You have learned, does Your program works.
So just get the code and hack it as fast as You can to get some effect
asap, to feed Your motivation, to get more effect fast, etc...

Concerning new versions ... it should be no big deal i guess.
You can just copy some files and hack the copies.

Another option is getting whole repository, so You can commit and
branch locally:

hg clone http://www.mimuw.edu.pl/~lew/hg/
cd libego
here is Your hacking

hg commit  (this is local commit)

hg pull (then whenever You want to check for new version)

But repository-solution may be too much for a less than few weeks of
work, it will be just a burden.

So just grab the source, do something and be happy :)
Lukasz

On 2/14/07, Heikki Levanto [EMAIL PROTECTED] wrote:

On Wed, Feb 14, 2007 at 10:57:38PM +0100, ?ukasz Lew wrote:
 Basically I wanted to implement a board in a hope that more people get
 attracted to Computer Go. But now this is more or less accomplished.
 So I decided to implement some kind of set canonical algorithms.
 But only those most common, I do not intend to make another GnuGo :)

 I just started UCT, as majority voted for it. Maybe patterns will come next.
 If You have something to propose, just go ahead :)

I have a question about your philosophy. Do you mean us - the users of
your library - to take the current version of the code, and start
modifying it to our needs? Or do you want us to link with the library,
so that we can upgrade to a later version without branching?

I am asking because I would need a bit different playout routine. I
could easily hack the library to do what I want, but that would in
effect be a branch, and lead to maintenance problems later if/when you
release a better version.

I could also inherit from your classes, and override what I need. That
would probably require a new header file, or something.

Or I could abstract my needs into a more general interface, submit that
as a patch, hope you accept it, and then use that.

To get down to earth, I would like to look at the board at the end of
each playout, calculate something more than just win/loss, and pass that
info back to who ever called playout. One way to do that would be to
pass a function pointer and a (void?) pointer to playout, and have it
call back the function with the board, winner, and the void pointer. If
that sounds more like C than C++, it is because I am a C programmer. If
some other C++ idiom could do the same thing, all the better.

Also, you have implemented the mercy rule in the playout code. If the
library should be used without duplicating the code, this might be
better left as a settable parameter.

Like I said, I could easily write my own playout. But then I'd have to
modify the gtp code to call that, and probably change a bit more here
and there. In the end I would have forked your code, and when you
release the next version, I would have to merge the changes in, and/or
decide to go our separate ways.

Perhaps I am worrying too much at such early state. I am just about
considering to start my own project. But I'd like to do the right thing
from the beginning.

What do you think?

   Heikki



--
Heikki Levanto   In Murphy We Turst heikki (at) lsd (dot) dk

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Effective Go Library v0.101

2007-02-13 Thread Łukasz Lew

On 2/13/07, Heikki Levanto [EMAIL PROTECTED] wrote:

On Sun, Feb 04, 2007 at 02:13:33PM +0100, ?ukasz Lew wrote:
 Optimizing and refactoring became my hobby, but it's too absorbing :)
 It's time to add some features now.

Just one question: Is the gtp support sufficient to play against other
machines (if we ignore the rather trivial genmove code :-)? If not,
adding the missing commands, even as dummies, would be a help for
beginning programmers.

Yes it is.



Also, I notice that I can not use quarry (graphical interface for Go and

Try GoGui.


other games) to play against 'engine_opt'. Presumably it needs a few
more gtp commands implemented. I will look into this, because if I am to
write any sort of engine, I will want to be able to play agaist it. Will
make a good warming-up exercise.

Thanks again for a good, useful library. I have started to look into it,
and once I got aroundthe namespaces and short names within, it looks
reasonably clear. I will experiment with some ideas, and if anything
useful comes out of them, I let you know. If I run into obvious
improvements, I may even send a patch.


Thanks :)

Łukasz



Regards

   Heikki

--
Heikki Levanto   In Murphy We Turst heikki (at) lsd (dot) dk


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-09 Thread Łukasz Lew

On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote:

Hi,

did you read Anti Huima's paper? The idea looks similar, but
unfortunately it does not work. I provided a proof of the defect on this
list (end of 2002 if I remember well). It's not that easy to get a
working scheme. In fact there is only one combination with 8 chunks of
data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we
found the right scheme. We wanted to write a paper, but we did not (it
takes time, and I had not that much time - mathematic and computer go is
just a hobby for me).

After having the right scheme, the tricky part is to perform a
statistical analysis: unfortunately introducing constraints to deal with
symetries weakens the hash key. The probability of collision becomes non
uniform and depends on the board configuration. In short: if you take
two different random board configurations, then the probability that
they have the same key becomes higher if one of the configuration has
self symetries.

If there is strong interest, I can post the scheme.

Please do.


But I'm not sure I
will post the statistical analysis (it was almost ten hand writen pages,
and I'm not sure I still have them).

Have You performed an empirical test for collisions?

Best,
Łukasz Lew



Antoine.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Effective Go Library v0.101

2007-02-05 Thread Łukasz Lew

There is nothing inherently cplusplusic, You can change class to
struct (provided that Your compiler supports functions in structs).
Add prefix player_ to every function in player:: namespace.

And of course don't forget about this no_variable_in_for thing...
Of course no printing on streams,
etc etc etc.

A lot of pain.
A LOT.

Maybe You prefer D?

Łukasz


On 2/5/07, steve uurtamo [EMAIL PROTECTED] wrote:

has anyone tried writing a C interface to these functions?
any suggestions about how to start?  i love the idea of the
library, but do not love the idea of writing C++.

thanks,

s.

- Original Message 
From: Łukasz Lew [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
Sent: Monday, February 5, 2007 2:41:23 AM
Subject: Re: [computer-go] Effective Go Library v0.101

Effective Go Library:
http://www.mimuw.edu.pl/~lew/









Don't pick lemons.
See all the new 2007 cars at Yahoo! Autos.
http://autos.yahoo.com/new_cars.html
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Effective Go Library v0.101

2007-02-04 Thread Łukasz Lew

Hi,

EGB 0.101 is the last performance release:
50 kpps on 1.4 GHz and
80 kpps on 2.2 GHz.

Optimizing and refactoring became my hobby, but it's too absorbing :)
It's time to add some features now.

I consider 3 things:
 - liberties tracing
 - UCT tree search
 - pattern tracing

Which feature You would like to see implemented?

Do You have any idea how to implement liberties efficiently?


Best Regards,
Łukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Effective Go Library v0.101

2007-02-04 Thread Łukasz Lew

On 2/4/07, Hideki Kato [EMAIL PROTECTED] wrote:

Łukasz Lew: [EMAIL PROTECTED]:
50 kpps on 1.4 GHz and
80 kpps on 2.2 GHz.


I'd like to add a sample in hand (10^6 playouts):
115 kpps on 3.0 GHz Intel Core2Duo (E6700/Conroe).


A pleasant number to look at ;)



And I have a question. Why Komi is not float but int?


For efficiency reasons ( :D )
Draw means win for white, so 7,5 is the same as 7.

You should use board-set_komi (float) it works OK.
I will add get_komi function and fix benchmark output..

Łukasz



- gg
--
Hideki Kato mailto:[EMAIL PROTECTED]
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Effective Go Library v0.101

2007-02-04 Thread Łukasz Lew

On 2/5/07, Hideki Kato [EMAIL PROTECTED] wrote:

Łukasz Lew: [EMAIL PROTECTED]:
On 2/4/07, Hideki Kato [EMAIL PROTECTED] wrote:

 Łukasz Lew: [EMAIL PROTECTED]:

 50 kpps on 1.4 GHz and

 80 kpps on 2.2 GHz.





 I'd like to add a sample in hand (10^6 playouts):

 115 kpps on 3.0 GHz Intel Core2Duo (E6700/Conroe).



A pleasant number to look at ;)


:)


 And I have a question. Why Komi is not float but int
For efficiency reasons ( :D )

Sure, I've modified your source code to use float for komi and get 75
(!) kpps on the same box above.


This is a way to much, please send me Your modification.



Draw means win
for white, so 7,5 is the same as 7.

It's ok for almost all games but you can also use a classical technique
of doubling komi that concludes having all internal scores be doubled.

I've tried this and get 104 kpps but I'm not sure it's correct (very
slower than expected).


There is no need to double all scores, because the convention that
white wins draws have the same effect.



You should use board-set_komi (float) it works OK.
I will add get_komi function and fix benchmark output..


Łukasz
add get_komi function and fix benchmark output..



Łukasz






- gg

 --

 Hideki
Kato mailto:[EMAIL PROTECTED]


___


computer-go mailing list


computer-go@computer-go.org


http://www.computer-go.org/mailman/listinfo/computer-go/




 inline file
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Effective Go Library v0.101

2007-02-04 Thread Łukasz Lew

Effective Go Library:
http://www.mimuw.edu.pl/~lew/

On 2/4/07, David Doshay [EMAIL PROTECTED] wrote:

UCT.

Cheers,
David



On 4, Feb 2007, at 5:13 AM, Łukasz Lew wrote:

 It's time to add some features now.

 I consider 3 things:
  - liberties tracing
  - UCT tree search
  - pattern tracing

 Which feature You would like to see implemented?


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] scalability study

2007-01-29 Thread Łukasz Lew

On 1/29/07, Don Dailey [EMAIL PROTECTED] wrote:

I don't understand what you are saying here.

Here is what I THINK you are saying ...

simple MC with all as first beats standard UCT at
19x19 go.

Is that what you mean?


Yes, That is what I meant.
I.e. Noise is so high on 19x19, that You need much more playouts
to have the same confidence about move.

I.e. just look at the numbers - how many playouts each move received
(ni UCT algorithm).

Best Regards
Łukasz



My experience with simple MC is that it does beat
UCT at really fast time controls in 9x9 and I believe,
although I haven't tested it, that simple MC
(with all-as-first)  will be superior at 19x19 until
you reach some fairly high number of play-outs.

In the 24 hour tournament I didn't use my MC program
for a couple of reasons,  one of them was my concern
about the memory requirements and the other was that
it wasn't clear to me that it would play stronger.
I felt that simple MC might be in it's sweet spot
even though it's not scalable beyond a certain point.

However, I have no hard evidence - it was just a
hunch and I did no studies as it was a last minute
decision to enter the tournament.

- Don






On Sun, 2007-01-28 at 23:49 +0100, Łukasz Lew wrote:
 Try simple MC with all as first :)
 I guess it beat any UCT totally.
 ( one playout here will be as 200-300 in UCT)


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] scalability study

2007-01-28 Thread Łukasz Lew

Try simple MC with all as first :)
I guess it beat any UCT totally.
( one playout here will be as 200-300 in UCT)

On 1/27/07, Don Dailey [EMAIL PROTECTED] wrote:

Below is the current results (in progress) of my
UCT 19x19 GO scalability study.

This is going to take a lot of time, but the
results should be useful and I want to make
them a matter of public record.   Each person
will interpret the data however he/she chooses.

The data below contains the following levels:

  0001  - 1024 play-outs
  0002  - 2048 play-outs
  0004  - 4096 play-outs
  0008  - 8192 play-outs

With help from other I will extend this as
much as possible to much higher levels.  Someone
is helping me run games even now as I write
this at higher levels - but the rate of play is
quite slow, so it will be some time until we get
significant results.

Also please note this is not a round robin,  only
matches between neighbor levels will be played.
2 vs 1,  4 vs 2,  8 vs 4,  16 vs 8   etc.

   komi 7.5
   200 games per match - 100 with each color


- Don



 gameswin%   Match
--  --   -
24   95.8%   0008 0004
   151   94.7%   0004 0002
   152   90.1%   0002 0001


 RatingTot GmsPlayer
--------
 1045.3 240008
  678.71750004
  321.13030002
0.01520001

Black wins:  159  48.6 %
White wins:  168  51.4 %



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


  1   2   >