Main Page
From Londerings
Welcome to WikiBlog. We are working on 24 articles. Learn how to edit pages (at Wikipedia site) (http://en.wikipedia.org/wiki/Wikipedia:How_to_edit_a_page), experiment in the sandbox and edit articles here.
For more frequent items see Minor items page.
| Table of contents |
CrazyStone beats pro player on 7x7 board: 2006-08-05
CrazyStone beats pro player on 7x7 Go board as white 8 times and plays 1 jigo. As black CrazyStone beats pro 1 time and loses 2 times. On all games except one komi 9 is used.
For games see KGS game archives (http://kgs.kiseido.com/en_US/gameArchives.jsp?user=CrazyStone).
Senseis 7x7 best play page (http://senseis.xmp.net/?7x7BestPlay).
SimpleGo v0.4.0: 2006-08-05
Tomorrow is Seventeenth KGS Computer Go Tournament (http://kgs.kiseido.com/en_US/tournEntrants.jsp?sort=s&id=212). SimpleBot participates in Open section.
More info about SimpleGo v0.4.0
SimpleGo v0.3.1: 2006-01-16
- tactical cut/connection reading for heuristical death reading
- cutting of small passageways between surrounding groups and between surrounding group and edge for killed group (only miai cutting currently)
Now it realises dead groups much earlier and sometimes kills and saves groups.
v0.3.X versions are available at SourceForge (http://londerings.sourceforge.net/go/simple_go/0_3/).
SimpleGo v0.2.2: 2005-10-27
Tactical search using partially implemented lambda search (http://www.t-t.dk/go/cg2000/). Depth 1 global search replaced with quick scoring based on shapes and local tactical results.
Go Teaching Program: 2005-10-22
Strength scales from "I have not read rules" to what GNU Go can offer.
When user starts program first time it presents user with empty 5x5 board. When user clicks on board stone is placed there. Near random level computer player responds. It would recognize atari and avoid playing into its own eyes. Each time stone is placed on board it would first do join animation with friendly stones if there are any. Then it would flash its liberties and change liberties count. If it touches enemy stones it would also flash their liberties and update counts. If it captures any of opponent stones flash differently all removed liberties and animate capture of stones. Initially it would also flash and mark all intersections where user can play. Gradually it would fade these helps away. This would be configurable too.
If illegal move is tried, have suitable explanation with animations. For example (Super-)Ko might have animation where situation repeats first slowly and then faster and faster and some animated characters comment on how ridiculous this is and then forbidding it is said to be the solution.
This would allow user to start playing instantly without reading rules.
As user strength increases animations and markings get less noticeable and eventually disappear.
The playing engine would change as the user becomes stronger. The program also would randomly select an opponent some levels above or below the user, and determine appropriate handicap. Maybe occasionally the handicap should be little off as well, to provide the user with a surprise element.
Program would keep track rank and current performance rating. Rank would only increase when program is sure strength has permanently increased. At certain rank points board size would change from 5x5 to 7x7 to 9x9 to 13x13 to 19x19.
- 5x5 maybe while < 100k
- 7x7 maybe while < 50k
- 9x9 maybe while < 30k-40k
Rank increase is like level increases in computer role playing games (CRPGs). Initial rank is near 200k and would usually initially quickly increase to 50k or maybe even 30k during first play session. Hope is that user gets hooked on "One more level" -effect that CRPGs often have. Final boss level is GNU Go, which is not that easy to achieve in a week ;-)
Also there should be variety of opponents at each level. Various versions of GNU Go provide one scale of opponents from very weak to current GNU Go.
Could also have other engines to play against. For example SimpleGo engine. Earlier versions are made to play against really new players.
Other authors might contribute additional engines to have more variety in opponents.
Also can use tuning to make various versions weaker to add variety of opponents at weaker levels. At stronger levels it might propose that user plays at online server against humans. Suggestion for playing against humans could start when user has achieved roughly 20k-30k level. Depends on online server what is lowest supported rating. This is to avoid frustration of thinking having fair game and then getting thoroughly trounced.
There could also be sturdy hardware to allow small children
to play. It would be like table PC with touch screen.
When user presses on screen stone would appear there.
This would allow even =<2 year old children to 'play'.
Computer also would have endless patience with many initial
random games before child starts to see patterns.
There could be fingerprint identification beside screen that would serve 2 purposes:
- Identify user and select right level.
- Start new game or continue old game.
New game would also be started when old has been finished and user tries to place a stone.
Maybe this tablet Go game would allow even monkeys to learn to play Go. If some of them can learn sign language, then why not also to play Go?
This program also could be used to monitor progress by beginning Go program as it gets stronger.
Just add GTP support and then program can gain levels when programmer makes it stronger, just like human would.
Also there could be menu item that would be something like "About your current computer opponent". From there you could even start programming IDE and start modifying source to computer opponent after having forked it with different name so not to confuse with stock program.
Permanent page/Edit link for this entry found here
SimpleGo engine: Tuesday, October 4th, 2005
SimpleGo (http://senseis.xmp.net/?SimpleGo) engine is now at version 0.2.1. Added 1-2 liberty tactical search. Maybe 20 stones stronger.
Great problems list: Thursday, September 22nd, 2005
I think these are most interesting problems.
- AI: sufficiently advanced AI would cover rest of this list
- Go program that plays well and/or human can use it for team play effectively at dan strength.
- Solve DNA coding (and also automatically decode text by humans, etc...)
- Busy Beaver Turing Machine (http://grail.cba.csuohio.edu/~somos/bb.html)
- Game of Life + random 'sun'
Permanent page/Edit link for this entry found here
Copyrights and patents: Thursday, September 15th, 2005
How to make Shakespeare again possible?
What if copyrights and patents were applied to garden?
Simulation of patent effectiveness?
Huge personal library possible.
For details see copyrights and patents
Go projects: Thursday, September 15th, 2005
At londerings/go (http://cvs.sourceforge.net/viewcvs.py/londerings/go/) there are some new projects:
gtpBalancer: Play 2 Go programs against each other and change handicap during tournament to find right handicap between these 2 programs.
gtpTuner: Change GNU Go 3.6 strength from full strength to full randomness smoothly. Favor top moves more than other moves when using partial randomness.
goTK: wxPython based Go ToolKit, unfinished
hgoban: Go goban program for HP 49G+ calculator: allows playing games between humans and replaying pro games.
kombilo: Path for kombilo05m that adds GNU Go interface to show top moves and dead/critical status of blocks and territory/moyo/area. Also has local_search interface. Screen shot (http://londerings.sourceforge.net/go/kombilo_gg.png)
local_search: Chess style tactical capture search for user defined area and blocks (hopefully life detection added soon, other features mentioned in page some time later).
old: Patch for Liberty 1.0 and GNU Go 2.0 so that they support simple version of GTP.
simple_go (http://senseis.xmp.net/?SimpleGo): Simple Go playing program written completely in Python, very weak. Initially meant for beginner programmers also.
Mathematical Go/GodBot source code (http://cvs.sourceforge.net/viewcvs.py/londerings/go/src/). If compiled with Chinese rule set support and other suitable settings, produces GodBot engine. GodBot is playing at KGS 2x2 and 3x3 sizes presently. Current CVS corresponds to this. By changing settings, one can compile older mathematical Go solver.
Permanent page/Edit link for this entry found here
Running ball: Thursday, March 3rd, 2005
Last night I dreamed about new sport. In dream there were about 10 teams each with 2 members. At start everybody was given ball. In dream ball was about squash ball sized. Goal was to run about 10km route as fast as possible while scoring as many goals as possible in 10 goal posts spaced 1km apart each other. There are no goal keepers. Whoever kicks ball over goal gets score. You can score only once with each ball in each goal line. Total score for team is calculated from number of goals and finish time. In dream each dream member was running alone against however happened to compete from same ball.
Once I awakened I started to ponder about this more and started typing it.
- First change immediately was to upgrade ball to football.
- Then I started to think about cheating. What if somebody doesn't care about ball during route and just runs to goal and then tries to catch one or more balls and score with them.
- There should be penalty from touching ball with hands or carrying it.
- Would this be effective strategy?
- With teams would this even be valid strategy?
- One way to fix this would be to have cameras all along route and players and balls to be brightly colored. Program then calculates how many meters each player had control of ball.
While typing I thought that maybe every team initially has one ball or maybe 1/2 of number of players.
One variation would be to play this at field and instead of fixed length it would be fixed time. Also team size could be 1 for individual competition.
Have you ever heard about game like this? If you try it, I would like to hear about experiences with it.
Permanent page/Edit link for this entry found here
Started few stories: Wednesday, January 26th, 2005
NanoMagic is fantasy story.
Signal is SciFi story.
Local Go search: Thursday, December 2nd, 2004
Chess style local searches. Local situation in Go often covers only about 5-40 intersections. Positions that cover 10 or less intersections should be solvable about instantly: at most 3^10 = 59049 positions. In chess beginning and middle game positions usually have about 20-40 moves. Still chess engines manage easily 10-15 ply (white+black moves) deep searches. In endgame searches might go 30 or more plies deep.
How to map techniques used in chess to local searches.
- Alpha-beta: if we already have better move elsewhere don't search further: standard stuff.
- Done
- Null move pruning: this is natural in Go: if opponent tenukis or passes and we still win: effectively reduces search depth by one.
- Search extensions: if move is forced (for example its only move that avoids capture): extend search depth by one. This handles cases like ladders.
- Hash tables: ko situations will be somewhat problematic.
- Done
- Ko is problematic for local searches in general. Need to enumerate ko threats and their values globally before we know winner of ko fight.
- History/killer moves: as usual.
- Scoring: 'end positions' like when given goal (for example group lives) has been achieved: handle these like checkmate in chess. Subtract depth from score so fastest route is favored.
- Only capture detected
- Positional scoring: how near we are of goal.
Examples:
| Goal | positional scores |
|---|---|
| 2 eyes | one of two eyes formed |
| partially formed eye | |
| space for eyes | |
| connect | approximate distance remaining |
| likelihood of connecting to succeed | |
| break in | depth of break in |
| area that has captured | |
| how connected break in is from secure base | |
| how surrounded it is | |
| general | area covered by live stones |
| weakly surrounded area | |
| weakly surrounded opponent stones give some score to owner | |
| unconditionally dead stones give none or minimal score for removal purposes | |
| 1., 2., etc.. order liberties: smaller order liberties give more score |
Permanent page/Edit link for this entry found here
Human-computer team Go: Saturday, November 27th, 2004
I'm currently experimenting with human-computer team play. I'm hoping that I can combine strengths of human and computer. Human is better at strategy and computer is better at local reading.
Areas where computer might be useful:
- Avoiding trivial blunders
- Various local reads:
- Life and death
- Connection searches
- Forming eyes
- Invasions and protecting against them
- Fuseki (global opening) and joseki (local opening)
- Score estimates
- Doing local/global pattern matching against pro games and then look at how game continued. Matching can also be fuzzy.
Areas where human might be useful:
- Avoiding trivial blunders
- Supply strategy:
- Keep these groups connected
- This group needs more eyespace or connection to group A or group B.
- Keep this dragon from connecting and/or forming eyes.
- Attack both and at same time get area/influence
- etc..
Current status
Rating according KGS 2005-07-11:
- Computer rating (GNU Go): 13k-12k, v3.6 probably 12k
- Computer rating (Games under Kombilo): 6d-9p
- Computer rating (local_search): if problem defined well, enough small and correct result is dead (capture): maybe perfect
- Human rating (Aloriless): 13k
- Team rating (Aloril): 7k? (8k-6k): KGS info of Aloril explicitly tells that I use computer help.
Computer help is used in following way.
- GNU Go: In screen (http://londerings.sourceforge.net/go/kombilo_gg.png) is shown all moves GnuGo is considering with scores. Score estimate with upper and lower limits is shown. Dead and critical dragons according GnuGo is shown. Territory/moyo/area is also shown though I plan to replace or augment them with eye display. Usually I also check reply and sometimes I read local position more deeply with GNU Go.
- Kombilo: At start of game I first try to find same whole board game and later I try to find same situation locally and see if its applicable to current whole board situation.
- Local_search: If there is small and closed situation then I can try to search to see if there is capture or clear way to avoid capture.
After analysis moves are decided by me. It takes about 10s to 10min to decide about move. I'm using 15min main time and 1min*50 byo-yomi as time setting.
About 50% of moves I decide to play are different than what GnuGo thinks is best. When team strength was about 13k-10k in strength, 40% of moves mere different.
In general global reading is done by me+Kombilo and local reading is done by GnuGo+local_search.
Currently this way of playing looks promising and is fun for me. Each game takes some hours to play though.
Chess
In chess it seems that Hydra (http://www.chessbase.com/newsdetail.asp?newsid=2476) is stronger than humans.
However in team play (Freestyle tournament) Hydra didn't even manage to get to top 8 players (http://www.chessbase.com/newsdetail.asp?newsid=2446).
Then couple of amateurs equipped with computers finished ahead of Grand Masters equipped with computers (http://www.chessbase.com/newsdetail.asp?newsid=2467).
Imagine if something like 5k player using pro level computer beat top amateur/pros using pro level computer in Go! Of course currently there are no pro level computers in Go ;-)
Permanent page/Edit link for this entry found here
To run list: Saturday, November 6th, 2004
This is manual distributed computing ;-)
This lists things to run:
If you start to run something:
Add name, start time and what you are running (range for example)
After you have ran it, edit to add result (or if no result, mention that also).
Currently E start factorization has things to run.
Permanent page/Edit link for this entry found here
Kirill Kryukov has also solved 3x3 chess: Tuesday, October 12th, 2004
Aloril: First I did 2-9 men tablebases. Date on last logfile is 1999-06-03. However there were errors and I lost interest for a while. At 2001 I got interested again and solved all positions at once instead of doing each piece combination separately. Tablebases have 2001-05-02 as date. Then I think I used a day or few to verify solution. I talked about solution at irc.worldforge.org #lounge at 2001-05-04 10:31:24. However I didn't talk about it at web until 2004-09-03. My solution includes only positions where there are no pawns or they are only at 2. row.
Kirill Kryukov has also solved 3x3 Chess in 2003. Since February 2004 his results are available (http://kd.lab.nig.ac.jp/3x3-chess/) online.
This includes longest checkmate lines, statistics, mate in N problems and some interesting positions. Also you can query the database for any position.
His solution is more complete because it also includes positions where white has pawn(s) on 1. row and/or black has pawn(s) on 3. row and it includes distance to stalemate.
Kir: I looked up the database, it seems the longest stalemate is 14 moves, you can see them here (http://kd.lab.nig.ac.jp/3x3-chess/positions.html#Longest_stalemate). If pawns are only allowed on 2-nd row, the longest stalemate is in 13 moves. There are 956 of them, like this one (http://kd.lab.nig.ac.jp/3x3-chess/3x3can.cgi?wNKnpppkBN). :-)
Here is longest optimal game that ends in mate when pawns are only allowed on 2. row, starting positions:
Mate in 16: KbN/qPP/Bbk w
Mate in 16: KbN/rPP/Bbk w
Moves: c3-a2 c1-c2 a2-c3 c2-c1 a3-b3 b1-c2 b3-a3 c2-b3 c3-a2 c1-c2 a2-c1 c2-c1 a3-b3 c1-b1 b3-c3 b1-c1 b2-b3N c1-b1 a1-b2 b1-a2 b3-c1 a2-b1 b2-a3 b1-a1 c3-b3 a1-b1 c1-a2 b1-a1 a3-b2 a1-b1 a2-c3
first position as a diagram:
3|KbN 2|qPP 1|Bbk +--- abc white to move
You can browse above position at Kirill Kryukovs site (http://kd.lab.nig.ac.jp/3x3-chess/3x3can.cgi?wKbNqPPBbk).
Here is longest line (http://kd.lab.nig.ac.jp/3x3-chess/3x3can.cgi?wK.ppnnqkr) if you allow pawns on first and last row.
Statistics (these are for positions where pawn(s) are allowed only on 2. row):
Time to solve: about 2h (calculating from 2001 logfile, takes 17 iterations)
Time to check solution: about 10h: this needs to go trough all positions (no mirror or legality reductions!) and for all nonterminal legal positions will do 1 ply search and compare result to stored value.
Table statistics (many mirror and king capture possible positions not included):
Unknown: these are positions that are draw by repetition
Draw: these are stalemate positions
Positions that can be forced into stalemate probably belong to later one of above, but I'm not sure
| Position | count | % in table |
|---|---|---|
| All | 48756582 | 100.000% |
| All lost | 27206172 | 55.800% |
| All draw | 7615818 | 15.620% |
| All won | 11484416 | 23.555% |
| Illegal | 2450176 | 5.025% |
| Unknown | 5766648 | 11.827% |
| Lost in 0 | 16825939 | 34.510% |
| Lost in 1 | 5314422 | 10.900% |
| Lost in 2 | 2267461 | 4.651% |
| Lost in 3 | 1102487 | 2.261% |
| Lost in 4 | 701304 | 1.438% |
| Lost in 5 | 470686 | 0.965% |
| Lost in 6 | 274836 | 0.564% |
| Lost in 7 | 133398 | 0.274% |
| Lost in 8 | 67108 | 0.138% |
| Lost in 9 | 29842 | 0.061% |
| Lost in 10 | 10734 | 0.022% |
| Lost in 11 | 4263 | 0.009% |
| Lost in 12 | 1967 | 0.004% |
| Lost in 13 | 1536 | 0.003% |
| Lost in 14 | 155 | 0.000% |
| Lost in 15 | 34 | 0.000% |
| Draw | 1849170 | 3.793% |
| Won in 16 | 2 | 0.000% |
| Won in 15 | 201 | 0.000% |
| Won in 14 | 310 | 0.001% |
| Won in 13 | 1072 | 0.002% |
| Won in 12 | 3169 | 0.006% |
| Won in 11 | 5407 | 0.011% |
| Won in 10 | 15660 | 0.032% |
| Won in 9 | 39601 | 0.081% |
| Won in 8 | 82430 | 0.169% |
| Won in 7 | 165466 | 0.339% |
| Won in 6 | 318632 | 0.654% |
| Won in 5 | 492748 | 1.011% |
| Won in 4 | 737437 | 1.512% |
| Won in 3 | 1383606 | 2.838% |
| Won in 2 | 2799725 | 5.742% |
| Won in 1 | 5438950 | 11.155% |
Complete 3x3 statistics (133×3 positions):
| Position | count | % in all positions | % in legal positions |
|---|---|---|---|
| All legal | 88520332 | 0.835% | 100.000% |
| All illegal | 10515979041 | 99.165% | 11879.733% |
| All lost | 51655161 | 0.487% | 58.354% |
| All draw | 14614570 | 0.138% | 16.510% |
| All won | 22250601 | 0.210% | 25.136% |
| extraIllegal | 10511078689 | 99.119% | 11874.197% |
| Unknown | 11035058 | 0.104% | 12.466% |
| Lost in 0 | 31939518 | 0.301% | 36.082% |
| Lost in 1 | 10049090 | 0.095% | 11.352% |
| Lost in 2 | 4319470 | 0.041% | 4.880% |
| Lost in 3 | 2105792 | 0.020% | 2.379% |
| Lost in 4 | 1335796 | 0.013% | 1.509% |
| Lost in 5 | 899333 | 0.008% | 1.016% |
| Lost in 6 | 526167 | 0.005% | 0.594% |
| Lost in 7 | 256412 | 0.002% | 0.290% |
| Lost in 8 | 129703 | 0.001% | 0.147% |
| Lost in 9 | 57346 | 0.001% | 0.065% |
| Lost in 10 | 20754 | 0.000% | 0.023% |
| Lost in 11 | 8396 | 0.000% | 0.009% |
| Lost in 12 | 3934 | 0.000% | 0.004% |
| Lost in 13 | 3072 | 0.000% | 0.003% |
| Lost in 14 | 310 | 0.000% | 0.000% |
| Lost in 15 | 68 | 0.000% | 0.000% |
| Draw | 3579512 | 0.034% | 4.044% |
| Won in 16 | 4 | 0.000% | 0.000% |
| Won in 15 | 402 | 0.000% | 0.000% |
| Won in 14 | 560 | 0.000% | 0.001% |
| Won in 13 | 2032 | 0.000% | 0.002% |
| Won in 12 | 6184 | 0.000% | 0.007% |
| Won in 11 | 10432 | 0.000% | 0.012% |
| Won in 10 | 30106 | 0.000% | 0.034% |
| Won in 9 | 74687 | 0.001% | 0.084% |
| Won in 8 | 156526 | 0.001% | 0.177% |
| Won in 7 | 316097 | 0.003% | 0.357% |
| Won in 6 | 605293 | 0.006% | 0.684% |
| Won in 5 | 934741 | 0.009% | 1.056% |
| Won in 4 | 1403513 | 0.013% | 1.586% |
| Won in 3 | 2662682 | 0.025% | 3.008% |
| Won in 2 | 5448822 | 0.051% | 6.155% |
| Won in 1 | 10598520 | 0.100% | 11.973% |
| Illegal | 4900352 | 0.046% | 5.536% |
Permanent page/Edit link for this entry found here
Shared workspace: Wednesday, October 6th, 2004
Continuous sharing of 'workspace' Things that could be visible when user chooses so:
- File buffer(s) user is currently editing.
- Others could comment or propose changes to buffer as it stands now.
- SubEthaEdit (http://www.codingmonkeys.de/subethaedit/) does this. I wish there were a GPL version of this, but it does seem kind of annoying to code.
- Web page(s) user is viewing.
- Others could comment or propose related pages to view.
- Game currently being played and moves/variations being considered.
- If one is playing on server, should have computer/team flag set so that opponent knows (s)he is not playing one human only.
- Others could comment on positions, moves/variations being considered and propose other moves/variations.
- Maybe shared 'search' tree that would be editable by anybody (and alterations marked by who did it).
- Other: edit this
Permanent page/Edit link for this entry found here
Google has found us: Saturday, September 18th, 2004
Google has now indexed these pages. Searching for "solving chess" (http://www.google.com/search?hl=en&lr=&ie=UTF-8&q=%22solving+chess%22&btnG=Search) it seems solving chess page is listed as 3rd (5th) entry! Searching for londerings (http://www.google.com/search?q=londerings&sourceid=mozilla-search&start=0&start=0&ie=utf-8&oe=utf-8) Main Page is obviously high (3/4). There are few pages where it could have picked it up. It doesn't have recent links from Wikipedia listed in index. It does show http://londerings.sourceforge.net/ page as updated and also lists http://sknkwrks.dyndns.org:1957/writewiki/wiki.pl?RecentChanges as 4th (6th) entry for Londerings. (the list at YpsiEyeball isn't really being updated like over at SwitchWiki (http://www.worldwidewiki.net/wiki/OneBigWikiAlphabeticalIndexL)
Why is solving chess page ranged so high in Google of 1,770 results? It does not have enough recent version of http://en.wikipedia.org/wiki/Talk:Computer_chess cached so link from there can't matter. Actually it doesn't list any links to it! It is linked from these pages though. Maybe page content is reason it's so hight, but how? Even more "surprising": it's also 3rd (4th) entry for solving chess (http://www.google.com/search?q=solving+chess&sourceid=mozilla-search&start=0&start=0&ie=utf-8&oe=utf-8) search without quotes from about 118,000 entries.
Searching for solve chess (http://www.google.com/search?q=solve+chess&hl=en&lr=&ie=UTF-8&start=10&sa=N) it ranks 14th among 148,000 pages. With quotes ("solve chess" (http://www.google.com/search?q=%22solve+chess%22&hl=en&lr=&ie=UTF-8&start=20&sa=N)) it ranks 21st among 665 pages.
I didn't except it to rank this high initially. I can just conclude that Google is quite good at ranking, if I was searching for "solving chess" I would like to see this entry on first page ;-) Some days ago I did go trough every page Google listed for that search term (and also for "solve chess") and didn't really find much anything. See Talk:Solving chess for entries found.
PS. Yes, I could have submitted these pages to Google, but wanted to see it happen 'naturally'.
Permanent page/Edit link for this entry found here
Changing chess rules: Monday, September 13th, 2004
First why these changes:
- eliminate draw by changing 2 common draw results into wins
- making tablebases for stalemate result is easy (same as mate), however don't see obvious way to make tablebases for repetitions
- remove ugly 50 move limit to allow perfect player to win (and less perfect also) in mathematically winnable position, but still force game to end
new scoring of results:
| how game ended | score |
|---|---|
| black mated | 3-0 |
| black out of time | 3-0 |
| black stalemated | 2-0 |
| position repeated by white | 1-0 |
| position repeated by black | 0-1 |
| white stalemated | 0-2 |
| white out of time | 0-3 |
| white mated | 0-3 |
Still need to experiment with more complex games than 2-3 piece games to see if this idea truly works.
After a bit more experimenting: when material and position is truly balanced, win might be hard: so still need 50 or similar rule:
- modified 50 move limit:
- if in 50 moves no capture or pawn movement: another can offer draw
- if declined and fails to win: 0-3 (lost on time)
- opponent gets time added suitably so (s)he doesn't run out of time unless really careless
- reduce time for side that needs to win so that (s)he either runs out of time or finishes game soon
- maybe also add option to accept later with result of 0-1 or 0-2? could be useful with fractional results and taking into account how many moves have been played since 50 move draw offer
- if this is not accepted by defender, then roles (and potential results from failing to win) switch
- change 50 move limit to 1000 move mate limit: 0-3 if not by this time
- maybe limit could be in general 100 or 200 moves and in special cases even 1000 moves
- if capture or pawn movement is made:
- nothing is reseted: you still need to mate in 1000 moves
- still 2-fold repetition is penalized, etc...
- if in 50 moves no capture or pawn movement: another can offer draw
Other options considered:
- forbid repetition and if unable to move due to being forced to repeat position: lost
- rejected because hard to win
- fork position
- in one branch if either side repeats position: white wins
- in second branch if either side repeats position: black wins
- whoever first wins, wins game
- rejected because sounds complex (though games end faster than with repetition==win for whoever made it)
- minor point: can sometimes allow draw ;-)
- good thing in this option: games are easiest to end because repetition by either side ends game
- repetition==draw: draw would probably still be common and would need some kind of 50-move rule or suitable replacement
- forbid repetition for each side separately and if unable to move due to being forced to repeat position: lost
- with king vs king for example this would end game in at most 63 moves at each side
- piece configuration history should be cleared when something is captured or promoted or pawn is moved
- in other words: can't make move that would make same piece configuration of pieces for side that is making move: for example if has bKa8 bBa7 has occurred, then black can't make move that would place its pieces again in this configuration
- so repetition and stalemate both would be considered as lost game: this looks best option so far
- need to experiment to see how viable this is
- with KRR pawn wall vs KRR pawn wall might still be quite long game
- solution: after certain number of moves opponent can select which piece is dropped from repetition checks: for example after 50 moves black drops white rook and white drops black rook from checks so now only need to repeat position with KR+pawns at each side
- claiming win because of repetition would be just like claiming draw in 3-fold repetition: if unnoticed, nothing happens, if opponent notices, (s)he wins
If I manage to find a way to generate tablebases for some of repetition option, then I guess that option is best one ;-)
Because:
- Then can conclusively analyse positions
- It might also be in practice easiest to win
- First point also allows to learn how to play them from analysing resulting tablebases
Some games:
8/8/8/8/8/k7/8/1K6 w - -
b1-a1 a3-b3 a1-b1 b3-c3 b1-c1 c3-d3 c1-d1 d3-e3 d1-e1 e3-f3 e1-f1 f3-g3 f1-g1 g3-h3 g1-h1 h3-h4 h1-h2 h4-g4 h2-g2 g4-f4 g2-f2 f4-e4 f2-e2 e4-d4 e2-d2 d4-c4 d2-c2 c4-b4 c2-b2 b4-a4 b2-a2 a4-a5 a2-a3 a5-b5 a3-b3 b5-c5 b3-c3 c5-d5 c3-d3 d5-e5 d3-e3 e5-f5 e3-f3 f5-g5 f3-g3 g5-h5 g3-h3 h5-h6 h3-h4 h6-g6 h4-g4 g6-f6 g4-f4 f6-e6 f4-e4 e6-d6 e4-d4 d6-c6 d4-c4 c6-b6 c4-b4 b6-a6 b4-a4 a6-a7 a4-a5 a7-b7 a5-b5 b7-c7 b5-c5 c7-d7 c5-d5 d7-e7 d5-e5 e7-f7 e5-f5 f7-g7 f5-g5 g7-h7 g5-h5 h7-h8 h5-h6 h8-g8 h6-g6 g8-f8 g6-f6 f8-e8 f6-e6 e8-d8 e6-d6 d8-c8 d6-c6 c8-b8 c6-b6 b8-a8 b6-a6 a8-b8 a6-b6
4k3/8/8/8/8/8/8/4KB2 w - -
stalemate if stubborn in avoiding repetition:
e1-e2 e8-e7 e2-e3 e7-e6 e3-e4 e6-d6 e4-d4 d6-c6 d4-c4 c6-b6 c4-b4 b6-c7 b4-c5 c7-d7 c5-d5 d7-e7 d5-e5 e7-f7 e5-f5 f7-g7 f5-g5 g7-h7 g5-h5 h7-g8 h5-g6 g8-f8 g6-f6 f8-e8 f6-e6 e8-d8 e6-d6 d8-c8 d6-c6 c8-b8 f1-a6 b8-a7 a6-b7 a7-b8 c6-b6
otherwise repetition:
e1-e2 e8-e7 e2-e3 e7-e6 e3-e4 e6-d6 e4-d4 d6-c6 d4-c4 c6-b6 c4-b4 b6-c7 b4-c5 c7-d7 c5-d5 d7-e7 d5-e5 e7-f7 e5-f5 f7-g7 f5-g5 g7-h7 g5-h5 h7-g8 h5-g6 g8-f8 g6-f6 f8-e8 f6-e6 e8-d8 e6-d6 d8-c8 d6-c6 c8-d8 c6-d6
Permanent page/Edit link for this entry found here
Idea sparking another idea: Thursday, September 9th, 2004
In Camera ideas Panorama section: this is what I was hoping would happen (in addition to fixes and edits to make it better): idea is added (http://londerings.novalis.org/wlog/index.php?title=Camera_ideas&diff=45&oldid=43) which then sparks another idea (http://londerings.novalis.org/wlog/index.php?title=Camera_ideas&diff=56&oldid=45) in other person
Permanent page/Edit link for this entry found here
Ideas for camera firmware: Wednesday, September 8th, 2004
Usually hardware has closed firmware. I have often wished that I had source code to firmware so I could fix bugs and/or add features I want. For cameras (especially Panasonic FZ10), here is 'dump' of my ideas.txt (needs editing):
- digital zoom in movie mode: digital zoom should work to extent that image size is reduced from maximum resolution
- maybe hardware support needed: sharp continuous mode: shoot images until you get sharp image or user is satisfied/bored (and display best candidate/jitter histogram so far)
- this has been partially implemented in software in Nikon Coolpix 3200 called as Best Shot Selector (BSS)
- only need to store best one, so should be no limit on how long can go on
- store first shot and last one: first one so that I don't miss situation regardless on how much jitter and last one for no jitter (or enough good)
- auto focus: make it work in darker by using longer exposures (slower, but works!)
- maybe when on tripod even use several second exposures and binary bracket until focus found
- assist lamp (maybe even use weak/strong flash as assist like rebel does?!)
- for manual focus show distance of current focus
- combine several shots using ISO50: less noise and more dynamic range than ISO200/ISO400 (mostly when 8s is not enough with ISO50)
- shoot several shots with different timing and combine for more dynamic range (this is there actually with exposure bracketing and post processing in computer)
- some Fujifilm cameras have SuperCCD censors where each photosite has 2 photodiodes with different sensitivity and thus can capture more dynamic range in one exposure
- combine shorter shots into longer exposure:
- handhold: show how much camera position has changed from initial so user can move it back to right position
- discard unsharp images and keep sharp ones
- have tolerance from 0% to whatever user wants (for example 10%): this amount of image at edge can be trimmed and only middle part is used when combining (easier to obtain shots that are sharp but a bit outside initial frame)
- tell user when enough sharp shots have been acquired for final image
- result: hand hold long sharp exposures! (this would of course work a lot better if photon counting was possible or enough sensitive sensor that acted at low light practically like photon counter)
- at IS400 or ISO50 or whatever: take 2 images: one with 1/30s and other with 1/4s (selectable): first for speed, second for light: later can select which one is better
- shoot several shots with different timing and combine for more dynamic range (this is there actually with exposure bracketing and post processing in computer)
- "use maximum zoom available at this distance" -button (and if less than max resolution selected: go for digital zoom after that)
- focus range setting and once focused "focus close/further" -'button'
- panorama/image-stitching support:
- many cameras have some support. For example Nikon Coolpix 3200 and Canon Powershot A85: you start taking images from left to right, and it shows you the right edge of the previous image, so you can do the line-up by eye.
- using motion tracking, show outline of last image taken on viewfinder, so user can line up next shot with last shot. This also could be used in daylight to automatically snap images at right moment for panorama while user slowly pans. This might even allow automatic multilevel panoramas: show in screen/viewfinder areas not yet covered. Actually this could be done in night also: camera just waits until movement on tripod has stabilized and then snaps image. In evening it snaps images until it gets sharp one.
Have you wished you could modify and improve firmware? Add here what you would have done if you had firmware for hardware item you have/had. (and/or modify above for camera related ideas)
Permanent page/Edit link for this entry found here
Solving Chess: Friday, September 3rd, 2004
According to Wikipedia (http://en.wikipedia.org/wiki/Chess) number of legal positions in chess is estimated to be between 1043 and 1050. Also 1040 positions has been mentioned. Lets assume 1043 positions and 1000 atoms for each position in parallel computer for analysing and storing position.
How big would that computer be? Avogadro's number number is approximately 6.022 × 1023 . Asteroid mass can be as big as [http://en.wikipedia.org/wiki/1_Ceres 9.445×1020 kg]. Lets assume that one Avogadro's number worth of atoms from Ceres has mass of 30g. This gives 9.445×1020 × 1000 × 6.022 × 1023 / 30 / 1043 = 1900 atoms for each position.
A bit related humor (http://www.enweirdenment.org/cgi-bin/topbot?list00317).
So if assumptions are true, then biggest asteroid should have enough material to solve chess.
Computer should be build in parallel into tree structure. Positions that are close to each other should also be physically close. For example positions with 10 pieces should be close to positions with 9 and 11 pieces. Inside those volumes positions where king and pawns are in similar positions should be close to each other.
Root of tree would be running main program and giving commands to branches which in turn give commands to their branches. If at each level there was 10 branches, then tree with 40 levels would cover all legal positions. Here we are assuming that each processor would handle > 1000 positions. This means that in 40 steps root node can give commands to 1040 nodes. Initial command would be to set score for mate and stalemate positions. Then send command to query all positions that are reachable from this position by legal moves. Then eval results: If there is winning move(s), then set our score to best of them and add 1 to distance to mate count. Otherwise if there are unknown results, then set our score to unknown. If all moves give known result, select best one for our score (and add 1 to distance as needed). Then report upward whether our score has changed. At each level going upwards would sum how many nodes in branches have changed. Root node would wait for all reports to arrive and then see if any node changed. If there are any changes, then repeat eval command. If no changes, then wait for user to query position. This would be then forwarded to appropriate branch and it would eventually return with score. Unknown score means repetition by draw.
Above however is likely not needed. It's brute force method for demonstration purposes. Ways things could be improved: likely need only small subset full tablebase of <=32 pieces. Maybe <15 piece tablebases would be enough. Search could then reach from starting positions into tablebases to solve starting position. This is how it's done in checkers where they have now solved The White Doctor opening (http://www.cs.ualberta.ca/~chinook/). With Crafty (http://en.wikipedia.org/wiki/Crafty) v19.16 searching one ply deeper at opening positions seems to require aproximately factor of 3 more nodes (factor of 9 for whole move: white+black). Improvements in search algorithms are likely going to reduce factor.
Another method would be to mathematically prove things. For example see mathematical Go (http://math.berkeley.edu/~berlek/cgt/go.html). In certain endgames (http://math.berkeley.edu/~berlek/cgt/gobook.html) this already gives sometimes better results than dan level players and completely outperforms brute force methods.
Maybe using math and/or search combined with tablebases even 1 kg of suitable material would be enough to solve chess.
Also see discussion page.
If you see any error here or have improvement to make or want to comment on this page, feel free to edit this page.
Oh, btw. Aloril and Kirill Kryukov (http://kd.lab.nig.ac.jp/3x3-chess/) have solved 3x3 chess completely.
Permanent page/Edit link for this entry found here
WikiBlogging: Thursday, September 2st, 2004
Combining Wiki and Blogging is not new idea as I discovered after googling for wiki+blog (http://www.google.com/search?q=wiki+blog).
http://www.spack.org/wiki/AdamShand seems to be closest to what I'm thinking.
However here I'm thinking more along lines of putting new ideas/news/etc.. as new entries and anybody can fix and/or improve them.
Ideas: these would have permanent page(s) that would be improved. If enough or significant changes have been made then there should be new entry on main page.
News: a bit like slashdot, except anybody can fix errors in news entry and add/modify ideas related to news item. These also would be moved to permanent page and if they remain active might eventually surface on front page like ideas.
Encyclopedic info should be eventually moved/copied into Wikipedia (http://en.wikipedia.org/).
About licenses: in addition to GNU FDL all stuff is licensed under GPL so any any potential code fragment can be used in GPL licensed programs.
Actual development of related programs should happen at londerings.sourceforge.net.
IRC channel: irc.worldforge.org #londerings
Daily database dumps of this site are available here (http://londerings.novalis.org/dumps/).
New idea seeds might first grow underground before I put them on front page.
Thanks to Novalis (http://novalis.org) for hosting this.
