Does Checkers have simpler rules than Go?

14 jkaufman 13 August 2013 02:09AM

I've seen various contenders for the title of simplest abstract game that's interesting enough that a professional community could reasonably play it full time. While Go probably has the best ratio of interest to complexity, Checkers and Dots and Boxes might be simpler while remaining sufficiently interesting. [1] But is Checkers actually simpler than Go? If so, how much? How would we decide this?

Initially you might approach this by writing out rules. There's an elegant set for Go and I wrote some for Checkers, but English is a very flexible language. Perhaps my rules are underspecified? Perhaps they're overly verbose? It's hard to say.

A more objective test is to write a computer program that implements the rules. It needs to determine whether moves are valid, and identify a winner. The shorter the computer program, the simpler the rules of the game. This only gives you an upper bound on the complexity, because someone could come along and write a shorter one, but in general we expect that shorter programs imply shorter possible programs.

To investigate this, I wrote ones for each of the three games. I wrote them quickly, and they're kind of terse, but they represent the rules as efficiently as I could figure out. The one for Go is based off Tromp's definition of the rules while the other two implement the rules as they are in my head. This probably gives an advantage to Go because those rules had a lot of care go into them, but I'm not sure how much of one.

The programs as written have some excess information, such as comments, vaguely friendly error messages, whitespace, and meaningful variable names. I took a jscompiler-like pass over them to remove as much of this as possible, and making them nearly unreadable in the process. Then I ran them through a lossless compressor, gzip, and computed their sizes:

  • Checkers: 648 bytes
  • Dots and Boxes: 505 bytes
  • Go: 596 bytes

(The programs are on github. If you have suggestions for simplifying them further, send me a pull request.)


[1] Go is the most interesting of the three, and has stood up to centuries of analysis and play, but Dots and Boxes is surprisingly complex (pdf) and there used to be professional Checkers players. (I'm having a remarkably hard time determining if there are still Checkers professionals.)

I also posted this on my blog.

Comments (46)

Internet Research (with tangent on intelligence analysis and collapse)

11 [deleted] 31 July 2013 04:58AM

Want to save time? Skip down to "I'm looking to compile a thread on Internet Research"!

Opinionated Preamble:

There is a lot of high level thinking on Less Wrong, which is great. It's done wonders to structure and optimize my own decisions. I think the political and futurology-related issues that Less Wrong cover can sometimes get out of sync with the reality and injustices of events in the immediate world. There are comprehensive treatments of how medical science is failing, or how academia cannot give unbiased results, and this is the milieu of programmers and philosophers in the middle-to-upper-class of the planet. I at least believe that this circle of awareness can be expanded, even if it's treading into mind-killing territory. If anything I want to give people a near-mode sense of the stakes aside from x-risk: all in all the x-risk scenarios I've seen Less Wrong fear the most, kill humanity somewhat instantly. A slower descent into violence and poverty is to me much more horrifying, because I might have to live in it and I don't know how. In a matter of fact, I have no idea of how to predict it.

This is one reason why I'm drawn to the Intelligence Operations performed by the military and crime units, among other things. Intelligence product delivery is about raw and immediate *fact*, and there is a lot of it. The problems featured in IntelOps are one of the few things rationality is good for - highly uncertain scenarios with one-off executions and messy or noisy feedback. Facts get lost in translation as messages are passed through, and of course the feeding and receiving fake facts are all a part of the job - but nevertheless, knowing *everything* *everywhere* is in the job description, and some form of rationality became a necessity.

It gets ugly. The demand for these kinds of skills often lie in industries that are highly competitive, violent, and illegal. I believe that once a close look is taken on how force and power is applied in practice then there isn't any pretending anymore that human evils are an accident.

Open Source Intelligence, or "OSINT", is the mining of data and facts from public information databases, news articles, codebases, journals. Although the amount of classified data dwarfs the unclassified, the size and scope of the unclassified is responsible for a majority of intelligence reports - and thus is involved in the great majority of executive decisions made by government entities. It's worth giving some thought as to how much that we know, that they do too. As illustrated in this expose, the processing of OSINT is a great big chunk of what modern intelligence is about aside from many other things. I think understanding how rationality as developed on Less Wrong can contribute to better IntelOps, and how IntelOps can feed the rationality community, would be awesome, but that's a post for another time.

--

The Show

Through my investigations into IntelOps I've noticed the emphasis on search. Good search.

I'm looking to compile a thread on Internet Research. I'm wondering if there is any wisdom on Less Wrong that can be taken advantage of here on how to become more effective searchers.  Here are some questions that could be answered specifically, but they are just guidelines - feel free to voice associated thoughts, we're exploring here.

  • Before actually going out and searching, what would be the most effective way of drafting and optimizing a collection plan? Are there any formal optimization models that inform our distribution of time and attention? Exploration vs exploitation comes to mind, but it would be worth formulating something specific. I heard that the multi-armed bandit problem is solved?
  • Do you have any links or resources regarding more effective search?
  • Do you have any experiences regarding internet research that you can share? Any patterns that you've noticed that have made you more effective at searching?
  • What are examples of closed-source information that are low-hanging fruit in terms of access (e.g. academic journals)? What are possible strategies for acquiring closed source data (e.g. enrolling in small courses at universities, e-mailing researchers, cohesion via the law/Freedom of Information Act, social engineering etc)?
  • I would like to hear from SEOs and software developers on what their interpretation of semantic web technologies and how they are going to affect end-users. I am somewhat unfamiliar with the semantic web, but from my understanding information that could not be indexed is now indexed; and new ontologies will emerge as this information is mined. What should an end-user expect and what opportunities will there be that didn't exist in the current generation of search?

That should be enough to get started. Below are some links that I have found useful with respect to Internet Research.

--

Meta-Search Engines or Assisted Search:

Summarizers:

Bots/Collectors/Automatic Filters:

Compilations and Directories:

Guides:

Practice:

I don't really care how you use this information, but I hope I've jogged some thinking of why it could be important.

Comments (43)

Leveling up...

12 RobertChange 29 July 2013 09:38PM

I just figured out how to use the local banking system and I will be able for the first time to pay my rent from my actual salary received in this country (as opposed to savings from my previous life). Also I always hated shopping for groceries and now I can do it without much pain, because I've found a way that works for me. As I reflect on this, an expression comes to my mind: "leveling up." I don't have the same problems any more which I used to have. I grow and face new challenges.

Did you, fellow rationalists and transhumanists, ever have that feeling? Any particular accomplishments, big or small, that made you feel you're advancing? No matter fast or slow, in big steps or tiny, but firmly forward!?

I'm thrilled to read your stories!

Comments (10)

Does anchoring on deadlines cause procrastination?

6 alex_zag_al 18 July 2013 07:12PM

The phenomenon of anchoring seems to predict that deadlines will cause you to start a project near the deadline.

In more detail:

Any number you consider as an answer to a question will become an anchor and draw your answer towards it. Since you consider a deadline as a time to finish a project, your decision about when you should actually finish the project will be drawn towards it.

That'll make you start the project later, even though you know consciously that planning to finish a project near the deadline is a bad idea.

It's analogous to an example from Kahneman's Thinking, Fast and Slow—people buy more cans when there's a sign telling them that they can only buy 10.

So, what I'm predicting is that anything that prevents anchoring will reduce procrastination when there's a deadline. Consciously deciding when you plan to finish by adjusting from a much earlier time, maybe?

EDIT: Brendon_Wong points out that "procrastination" really refers to putting things off, which has an emotional cause. I think he's right. What I'm talking about isn't really a procrastination, then, but bad planning.

Comments (23)

HIKE: A Group Dynamics Case Study

9 iconreforged 16 July 2013 07:14PM

I belong to a group at my university that organizes a backpacking trip for incoming freshmen in the two weeks before orientation week. This organization, which I will refer to as HIKE (not the real name), is particularly interesting in terms of group design. Why? It is approximately 30 years old, is run entirely by current students, and brings together a very large group of people and knits them into a largish community. Pretty much everyone involved  agrees that HIKE works very well. During my involvement (I was a participating freshman, and I have since become staff) I have continually wondered, why is this group so much more fun than any other group I've been a part of?

It's also particularly effective. Leading ~80 incoming freshmen, who have no current friends, and who know no one, and who don't generally have any backpacking experience, into the woods for two weeks, is no easy task. HIKE manages its own logistics, staff training, and organization, entirely with student volunteers who staff the trip, with little to no university interaction. (We get them to advertise our trip, and they generally permit us to continue to exist.) It takes some dedication to keep this rolling, and I have seen other campus groups completely fail to find that kind of dedication from their membership.

While it's not a rationalist group, it seems to have stumbled upon a cocktail of instrumentally rational practices. 

HIKE uses an interesting process of network homogenization. When staff members (who have generally been on several trips before) are assigned crews, staff members fill out "Who Do You Know?" forms, on which you rank how well you know other staff on a scale from 1 to 5. The people in charge of making groups, usually Project Directors, then group staffers based on how well you don't know other staff. You usually staff a trip with people that you haven't gotten to know very well, and then get to know them. Because of this process of strengthening the weakest bonds, HIKE is able to function as a relatively large social group, even across graduation classes and around existing cliques.

As far as actual interaction, HIKE involves a lot of face time with your crew of 10 freshmen and your co-staffers. There aren't really any breaks (with the exception of solos, see below) and you are hiking, eating, and chatting together for approximately 225 hours (15 waking hours in a day * 15 days). I had 13 hours and 40 minutes of class a week the Spring 2013 semester. HIKE is approximately 7+ weeks of class at that rate.

One of the more beloved HIKE traditions is the solo, where the hiking leaders pick a spot with plenty of isolated spaces, and the participants can choosee to spend ~24 hours alone and, optionally, fasting. It's a novel experience, and people like the time to rest and reflect in the middle of a very social, very intensive hiking trip.

My suspicion for why this all works is that HIKE very closely simulates a hunter-gatherer lifestyle. You travel in ~10 member groups, on foot, carrying your food, on mountain trails. You spend your every waking hour with the crew. The 2-3 hiking leaders are there to facilitate only (read: perform first aid if necessary, guide conversation, teach outdoor skills if necessary, and nudge the group if they get off track), and all decisions are made by consensus (which isn't an all-purpose decision making process, but is very egalitarian, and helps the group gel).

Maybe I'm just praising my friend-group, but I feel like I stumbled into a particularly strong group of people. We all feel very well-connected and we feel a lot of commitment to the program. My experience with other college groups has been that members are pulled apart by other commitments and a lack of familiarity with other members, and HIKE seems to avoid that with a critical mass of consecutive face time. We manage to have continuity of social norms across the years, but a great deal of flexibility (no one remembers what happened 4 years ago, and some traditions disappear and others cement themselves as ancient and hallowed despite being only two years old).

I'm interested in hearing any thoughts on this, and any relevant experience with other groups, ideas for testing cross-application, requests for further elaboration, etc.


 

 

Comments (3)

Less Wrong London New Arrival Integration Task Force

28 sixes_and_sevens 11 July 2013 04:53PM

After considering how many of us have arrived here within recent memory, the London Less Wrong community is explicitly offering itself as a resource for those moving to the city. We all know how awkward and daunting it can be to get settled somewhere new, and we'd like to help newcomers hit the ground running. It seems that our most effective recruitment strategy at the moment is "wait for existing Less Wrong readers to move here", so it's a worthwhile offer to make.

If any LessWrongers are moving to the Greater London area, let us know. Either message me via the site or join our Google Group. Tell us where/when you're moving, what your circumstances are, and what sort of things you like to do. We will try to proactively invite you to events and activities we think you'll enjoy, as well as providing you with useful local knowledge if you want it.

We will also try and make some time available for you if there's anything you need another person's help with. If assembling your Ikea bookshelf is a two-person job, we'll see if we can scrape together a couple of people for a couple of hours to help you put it together.  If you need help setting up your wireless router, we'll see if someone with the relevant skills is available to give you a hand.  We can't promise any specific type of help, but we're always happy to be asked.

Big cities can often feel quite impersonal, so if you're planning on moving here, or even just thinking about it, let us know, and we'll see what we can do to make it a little more welcoming.

Comments (6)

On-line conference for LW readers and meet up members

7 Yuu 07 July 2013 09:53AM

I would like to consolidate LW members in a new way. I believe we can organize an on-line gathering in some form, for example as a set of chat rooms to discuss different topics in the real time. This event can be announced in advance to help everyone to arrange plans. I hope the discussion can be more intense and productive than in chats that open for prolonged periods of time. And comparing to the lesswrong.com this event should give some feeling of a real conversation, which I can not get while posting articles and comments here.

If you have any additions, ideas and proposals please let me know.

Comments (8)

Help please! Making a good choice between two jobs

2 cjb230 10 July 2013 11:23AM

After about three months of unemployment, today I have been told I will receive two different job offers. Obviously I want to make a decision that maximises my utility, but there are some difficult-to-quantify factors involved. Can anyone suggest a useful or clarifying perspective on the choice? What questions should I be asking myself?

As background, I'm a 36-year old male techie based in the UK. What I would really like to do is build my own startup, or join a startup that I think has good prospects. However, having done that twice, and nearly bankrupted myself twice, I need to get a financial cushion under myself before trying again. For the sake of my CV, I think I need to stay in my next role for at least 18 months. After that, I hope to be able to try something entrepreneurial again, but I want to stay employable in technology as a financial safeguard. 

One job is in London, and will certainly pay more. I have many friends there, and a social network I can get back in to straight away. The pool of women I am interested in dating is much bigger there. The job itself will allow me to improve my skills, but probably not broaden them; there are very skilled people there that I can learn from. With this job, I fear being bored, and getting more and more specialised in a skill that is getting less popular.

The other job is in Glasgow. It will pay less, probably by about £15k. The cost of living difference, after tax, will probably be bigger than this - I expect I will have more money in my pocket with this job than with the London job. I only know two people living in Glasgow, so I will need to make new friends and get a new social life. Dating prospects are probably less good, but I don't know by how much. The job itself looks more interesting, and I can broaden my skills. The job market I am in will probably be more open to me after I take this job. With this job, I fear getting depressed due to isolation, and also the long-term effect of accepting a pay cut - if I worked in London again later, would I be able to negotiate my salary back up?

Cost aside, London is a better location. It has more of everything I am interested in (including a LW meetup group!). Location and pay aside, the job in Glasgow is better. I expect it will be more interesting, and will make it less likely that I'll be unemployed in the future.

I don't know how to weight these factors up properly. What mistakes in judgement do I need to avoid? What approaches can I take to make the decision easier to make correctly?

Comments (31)

[LINK] Westerners may be terrible experimental psychology subjects

14 David_Gerard 26 February 2013 12:46PM

WEIRD may be weirder than you think. We Aren't The World writes of psychological experiments on non-Westerners that give vastly disparate results from results that have been assumed to be hardwired, and the implications of this:

Henrich used a “game”—along the lines of the famous prisoner’s dilemma—to see whether isolated cultures shared with the West the same basic instinct for fairness. In doing so, Henrich expected to confirm one of the foundational assumptions underlying such experiments, and indeed underpinning the entire fields of economics and psychology: that humans all share the same cognitive machinery—the same evolved rational and psychological hardwiring.  The test that Henrich introduced to the Machiguenga was called the ultimatum game.

...

To begin with, the offers from the first player were much lower. In addition, when on the receiving end of the game, the Machiguenga rarely refused even the lowest possible amount. “It just seemed ridiculous to the Machiguenga that you would reject an offer of free money,” says Henrich. “They just didn’t understand why anyone would sacrifice money to punish someone who had the good luck of getting to play the other role in the game.”

...

At the heart of most of that research was the implicit assumption that the results revealed evolved psychological traits common to all humans, never mind that the test subjects were nearly always from the industrialized West.

Edit: The actual papers this article writes about are covered in this post by Ciphergoth from a few years ago.

Comments (52)

Need some psychology advice

7 Kenoubi 27 February 2013 05:03PM

I started going out with a fantastic girl a couple of weeks ago.  Everything is great, except that whenever I've sent her a text message or email requesting something and haven't received a response yet, I experience significant dysphoric anxiety, fearing that her response will be not just "no" but "no and I don't want to date you any more".  This is due to brain chemistry or personal history, take your pick—either seems like a possible explanation to me.  But there's certainly no evidence supporting the idea that this is likely to happen, nor is the anxiety helping me prevent it or helping me in any other way.

Does anyone have evidence-based advice, or pointers to same, on dealing with this kind of issue?  It is the only splotch on what have otherwise been the best two weeks of my life.

 

Comments (110)

View more: Prev | Next

Powered by Reddit Powered by Reddit